Pairs in the right place
In the hereunder sequence S any pair of two adjacent digits (don't mind spaces and commas) will form a 2-digit number k in position k. This is the lexicographically earliest sequence of distinct positive integers with this property.
S = 1,
2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 14, 16, 18, 32, 123, 21, 23, 29, 43, 234, 34, 38,
54, 143, 45, 41, 49, 61, 65, 456, 56, 76, 111, 656, 71, 671, 67, 676, 78, 91, 183,
85, 418, 99, 129, 496, 999, 94, 96, 112, 113, 83, 89, 114, 115, 411, 116, 117, 118,
321, 121,...
Could someone be so kind to check and extend S, if this is worth entering the OEIS?
Example: the pair (1,2) is in position 12, the pair (2,3) is in position 23, the pair (3,4) is in position 34, the pair (4,5) is in position 45, the pair (5,6) is in position 56, the pair (6,7) is in position 67, the pair (7,8) is in position 78, the pair (8,9) is in position 89, the pair (9,1) is in position 91, etc.
Could someone be so kind to check and extend S, if this is worth entering the OEIS?
Best,
É.
______________
Next morning update:
Maximilian H. was quick to find a silly mistake of mine at a(37), underlined. Here is the new start (extension and submission will be done later today):
S = 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 14, 16, 18, 32, 123, 21, 23, 29, 43, 234, 34, 38, 54, 143, 45, 41, 49, 61, 65, 456, 56, 76, 111, 656, 71, 67, 121, 676, 78, 91, 183, 85, 418, 99, 129, 496, 999, 94, 96, 112, 113, 83, 89, 114, 116, 117, 118, 321, 121,...
Merci Maximilian (and David S.)!
______________
Next morning update:
David S. found another mistake towards the end of S, as the pair (6,9) is not possible with the curent development:
418, 99, 129, 496, 999,
David fixed everything in a SeqFan mail this morning (the definitive S is below, in a courier new bold font):
[David]:
I have checked that sequence, and unfortunately it fails to have the property. Specifically, divide it into sets of 10 digits:
1,2,3,4,5,6,7,8,9,1
1,12,14,16,18,3
2,123,21,23,29,
43,234,34,38,5
4,143,45,41,49,
61,65,456,56,7
6,111,656,71,6
71,67,676,78,9
1,183,85,418,9
9,129,496,999,
94,96,112,113,
83,89,114,115,
411,116,117,1
18,321,121,...
Remove the commas and separate the digits with spaces, then mark the digit pairs that can appear in the sequence by replacing the space between them with a hyphen:
1 2 3 4 5 6 7 8 9 1
1-1-2 1-4 1-6 1-8 3
2-1 2-3 2 1 2 3 2-9
4 3-2 3-4 3 4 3-8 5
4-1 4-3 4-5 4 1 4-9
6 1 6 5-4 5-6 5 6 7
6-1 1 1 6-5 6-7 1 6
7-1 6 7 6 7-6 7-8 9
1 1 8-3 8-5 4 1 8-9
9-1 2 9-4 9-6*9 9-9
9 4 9 6 1 1 2 1 1*3
8 3 8 9 1 1 4 1 1*5
4 1 1 1 1 6 1 1*7 1
1 8 3 2 1 1 2 1 ...
The digit pairs that I have marked with asterisks fail to have the property: 69 does not occur at position 69, 13 does not occur at position 13, 15 does not occur at position 15 and 17 does not occur at position 17.
I have attempted to calculate the sequence myself. If my calculation is correct, the first 48 terms of the sequence are:
S = 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 14, 16, 18, 32, 123, 21, 23, 29, 43, 234, 34, 38, 54, 143, 45, 41, 49, 61, 65, 456, 56, 76, 111, 656, 769, 67, 69, 676, 78, 91, 183, 85, 418, 99, 129, 496, 999, ...
It first differs from your sequence at a(36), where you have 71 and I have 769. A similar check to the above produces:
1 2 3 4 5 6 7 8 9 1
1-1-2 1-4 1-6 1-8 3
2-1 2-3 2 1 2 3 2-9
4 3-2 3-4 3 4 3-8 5
4-1 4-3 4-5 4 1 4-9
6 1 6 5-4 5-6 5 6 7
6-1 1 1 6-5 6-7 6-9
6 7 6 9 6 7-6 7-8 9
1 1 8-3 8-5 4 1 8-9
9-1 2 9-4 9-6 9 9-9
...
and all the digit pairs are allowed ones.
Note that as I've got the first 100 digits and therefore know whether each digit pair is allowed and that no further digits will be determined until we reach it, extending the sequence further can be done with the straightforward greedy algorithm, i.e. work through all the possible 1-digit extensions that only use the thirty allowed digit pairs:
11,12,14,16,18,
21,23,29,
32,34,38,
41,43,45,49,
54,56,
61,65,67,69,
76,78,
83,85,89,
91,94,96,99
then through the 2-digit extensions using them, then through the 3-digit extensions using them, etc, until we reach one that hasn't appeared before. This process cannot run into a dead end, since every digit has at least one possible successor (indeed, at least two), so there are an infinite number of possible extensions, and only a finite number of them can have appeared before.
E.g. the next term can be calculated using the fact that the sequence currently ends with a digit 9. The 1-digit extensions are 1, 2, 6 and 9, all of which have appeared before, then the 2-digit extensions are 11, 12, 14, 16, 18, 21, 23, 29, 61, 65, 67, 69, 91, 94, 96, 99, all of which up to and including 91 have appeared before. But 94 hasn't appeared before, so the next term is 94.
Then for the following term, the sequence ends with a digit 4. The 1-digit extensions are 1, 3, 5 and 9, all of which have appeared before, then the 2-digit extensions are 11, 12, 14, 16, 18, 32, 34, 38, 54, 56, 91, 94, 96, 99, all of which up to and including 94 have appeared before. But 96 hasn't appeared before, so the next term is 96.
And for the term after that, the sequence now contains every one of the nine allowed 1-digit numbers and every possible 2-digit extension starting from any final digit (i.e. the thirty 2-digit numbers that are allowed digit pairs). So from now on, we only need to look at 3-digit extensions and higher, and the ones that have appeared before are 111, 123, 129, 143, 183, 234, 418, 456, 496, 656, 676, 769, 999. Starting from the current ending digit 6, the possible 3-digit extensions start 111 (already used), 112 (unused), so the next term is 112.
And for the term after that, the current ending digit is 2 and the possible 3-digit extensions start 111 (already used), 112 (already used), 114 (unused), so the next term is 114. Then the current ending digit is 4 and the possible 3-digit extensions start 111 (already used), 112 (already used), 114 (already used), 116 (unused), so the next term is 116. Then the current ending digit is 6 and the possible 3-digit extensions start 111 (already used), 112 (already used), 114 (already used), 116 (already used), 118 (unused), so the next term is 118. Then the current ending digit is 8, and the possible 3-digit extensions start 321 (unused), so the next term is 321. And so on...
The net result is that I'm certain that the 48 terms of the sequence I've calculated do have the property and can be extended indefinitely without running into a contradiction. The point I'm not quite so certain about is that the sequence I've calculated is lexicographically smaller than any other sequence with the property - the calculation was done with spreadsheet assistance to follow through on consequences of decisions I made and highlight contradictions, but enough of the reasoning to say that lexicographically smaller choices don't work was exposed to possible human error on my part that I can't be completely certain I didn't make a mistake in it. (...)
___________________
Manty thanks for the help, David!
______________
Next morning update:
Maximilian H. was quick to find a silly mistake of mine at a(37), underlined. Here is the new start (extension and submission will be done later today):
S = 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 14, 16, 18, 32, 123, 21, 23, 29, 43, 234, 34, 38, 54, 143, 45, 41, 49, 61, 65, 456, 56, 76, 111, 656, 71, 67, 121, 676, 78, 91, 183, 85, 418, 99, 129, 496, 999, 94, 96, 112, 113, 83, 89, 114, 116, 117, 118, 321, 121,...
Merci Maximilian (and David S.)!
______________
Next morning update:
David S. found another mistake towards the end of S, as the pair (6,9) is not possible with the curent development:
418, 99, 129, 496, 999,
David fixed everything in a SeqFan mail this morning (the definitive S is below, in a courier new bold font):
[David]:
I have checked that sequence, and unfortunately it fails to have the property. Specifically, divide it into sets of 10 digits:
1,2,3,4,5,6,7,8,9,1
1,12,14,16,18,3
2,123,21,23,29,
43,234,34,38,5
4,143,45,41,49,
61,65,456,56,7
6,111,656,71,6
71,67,676,78,9
1,183,85,418,9
9,129,496,999,
94,96,112,113,
83,89,114,115,
411,116,117,1
18,321,121,...
Remove the commas and separate the digits with spaces, then mark the digit pairs that can appear in the sequence by replacing the space between them with a hyphen:
1 2 3 4 5 6 7 8 9 1
1-1-2 1-4 1-6 1-8 3
2-1 2-3 2 1 2 3 2-9
4 3-2 3-4 3 4 3-8 5
4-1 4-3 4-5 4 1 4-9
6 1 6 5-4 5-6 5 6 7
6-1 1 1 6-5 6-7 1 6
7-1 6 7 6 7-6 7-8 9
1 1 8-3 8-5 4 1 8-9
9-1 2 9-4 9-6*9 9-9
9 4 9 6 1 1 2 1 1*3
8 3 8 9 1 1 4 1 1*5
4 1 1 1 1 6 1 1*7 1
1 8 3 2 1 1 2 1 ...
The digit pairs that I have marked with asterisks fail to have the property: 69 does not occur at position 69, 13 does not occur at position 13, 15 does not occur at position 15 and 17 does not occur at position 17.
I have attempted to calculate the sequence myself. If my calculation is correct, the first 48 terms of the sequence are:
S = 1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 12, 14, 16, 18, 32, 123, 21, 23, 29, 43, 234, 34, 38, 54, 143, 45, 41, 49, 61, 65, 456, 56, 76, 111, 656, 769, 67, 69, 676, 78, 91, 183, 85, 418, 99, 129, 496, 999, ...
It first differs from your sequence at a(36), where you have 71 and I have 769. A similar check to the above produces:
1 2 3 4 5 6 7 8 9 1
1-1-2 1-4 1-6 1-8 3
2-1 2-3 2 1 2 3 2-9
4 3-2 3-4 3 4 3-8 5
4-1 4-3 4-5 4 1 4-9
6 1 6 5-4 5-6 5 6 7
6-1 1 1 6-5 6-7 6-9
6 7 6 9 6 7-6 7-8 9
1 1 8-3 8-5 4 1 8-9
9-1 2 9-4 9-6 9 9-9
...
and all the digit pairs are allowed ones.
Note that as I've got the first 100 digits and therefore know whether each digit pair is allowed and that no further digits will be determined until we reach it, extending the sequence further can be done with the straightforward greedy algorithm, i.e. work through all the possible 1-digit extensions that only use the thirty allowed digit pairs:
11,12,14,16,18,
21,23,29,
32,34,38,
41,43,45,49,
54,56,
61,65,67,69,
76,78,
83,85,89,
91,94,96,99
then through the 2-digit extensions using them, then through the 3-digit extensions using them, etc, until we reach one that hasn't appeared before. This process cannot run into a dead end, since every digit has at least one possible successor (indeed, at least two), so there are an infinite number of possible extensions, and only a finite number of them can have appeared before.
E.g. the next term can be calculated using the fact that the sequence currently ends with a digit 9. The 1-digit extensions are 1, 2, 6 and 9, all of which have appeared before, then the 2-digit extensions are 11, 12, 14, 16, 18, 21, 23, 29, 61, 65, 67, 69, 91, 94, 96, 99, all of which up to and including 91 have appeared before. But 94 hasn't appeared before, so the next term is 94.
Then for the following term, the sequence ends with a digit 4. The 1-digit extensions are 1, 3, 5 and 9, all of which have appeared before, then the 2-digit extensions are 11, 12, 14, 16, 18, 32, 34, 38, 54, 56, 91, 94, 96, 99, all of which up to and including 94 have appeared before. But 96 hasn't appeared before, so the next term is 96.
And for the term after that, the sequence now contains every one of the nine allowed 1-digit numbers and every possible 2-digit extension starting from any final digit (i.e. the thirty 2-digit numbers that are allowed digit pairs). So from now on, we only need to look at 3-digit extensions and higher, and the ones that have appeared before are 111, 123, 129, 143, 183, 234, 418, 456, 496, 656, 676, 769, 999. Starting from the current ending digit 6, the possible 3-digit extensions start 111 (already used), 112 (unused), so the next term is 112.
And for the term after that, the current ending digit is 2 and the possible 3-digit extensions start 111 (already used), 112 (already used), 114 (unused), so the next term is 114. Then the current ending digit is 4 and the possible 3-digit extensions start 111 (already used), 112 (already used), 114 (already used), 116 (unused), so the next term is 116. Then the current ending digit is 6 and the possible 3-digit extensions start 111 (already used), 112 (already used), 114 (already used), 116 (already used), 118 (unused), so the next term is 118. Then the current ending digit is 8, and the possible 3-digit extensions start 321 (unused), so the next term is 321. And so on...
The net result is that I'm certain that the 48 terms of the sequence I've calculated do have the property and can be extended indefinitely without running into a contradiction. The point I'm not quite so certain about is that the sequence I've calculated is lexicographically smaller than any other sequence with the property - the calculation was done with spreadsheet assistance to follow through on consequences of decisions I made and highlight contradictions, but enough of the reasoning to say that lexicographically smaller choices don't work was exposed to possible human error on my part that I can't be completely certain I didn't make a mistake in it. (...)
___________________
Manty thanks for the help, David!
Commentaires
Enregistrer un commentaire