[seqfan] Re: Pairs in the right place

[Éric Angelini]

Many thanks, David. We agree on 99% of
the stuff.
I will check again my a(36) that causes me
troubles from the beginning (Maximilian will
check too).
Nice and clear mail of you — thank you!
à+
É.
Catapulté de mon aPhone


> Le 18 mai 2020 à 03:37, David Seal <david.j.seal at gwynmop.com> a écrit :
> 
> 
>> 
>> On 17 May 2020 at 01:02 Éric Angelini <bk263401 at skynet.be> wrote:
>> ...
>> 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,...
>> 
>> 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?
> 
> 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:
> 
> 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.
> 
> Finally, please don't take the above as implying any opinion about whether the sequence should go into the OEIS - my understanding of OEIS editorial policy is too limited for me to be able to form such an opinion!
> 
> David
> 
> --
> Seqfan Mailing list - http://list.seqfan.eu/