A108718 - OEIS

%I #71 Jan 02 2023 12:30:46

%S 1,21,2,11,3,4,111,1122,5,6,7,8,9,22,23,22222,222222,2222222,22222222,

%T 222222222,24,25,26,222,27,28,29,32,33,34,35,36,37,38,39,42,43,44,45,

%U 46,47,48,49,52,53,54,55,56,57,58,59,62,63,64,65,66,67,68,69,72,2222,73

%N Longest sequence of distinct integers such that the length of the n-th term is given by the n-th digit of the sequence itself.

%C The sequence is finite - but what is the last term?

%C It is not yet known whether the sequence is well-defined with the current wording of its name. - _M. F. Hasler_, Dec 01 2015

%C The digit '0' may not occur. The digit '1' may occur only 9 times since there are only 9 single-digit numbers that may occur. The digit '2' may occur only 63 times since among the 9^2 two-nonzero-digit numbers, {12, 13,..., 19, 31, 41, ..., 91 and 82, 92, 93} are excluded during the construction of the sequence, cf. Example. - _M. F. Hasler_, Nov 09 2015

%C There are less than 740 4-digit terms, because there can be no more than 1103 5-digit terms and this effectively reduces the number of 4-digit terms to no more than 528 which reduces the number of 3-digit terms to 229. - _Hans Havermann_, Nov 09 2015

%H E. Angelini, <a href="http://list.seqfan.eu/oldermail/seqfan/2015-October/015499.html">Last term?</a>, SeqFan list, Oct. 25, 2015.

%e The first terms of the sequence have lengths (i.e., number of digits) 1, 2, 1, 2, 1, 1, 3, ... which coincide with the initial digits of the sequence.

%e The sequence starts with a(1) = 1, since 0 is not allowed (not even as a digit of a term) because an integer cannot have 0 digits.

%e This "1" indicates that the first integer of the sequence must have length one - which is the case.

%e The next term cannot be "1" again, because all terms of the sequence must be distinct, nor "2", ..., "19" (which would be self-contradictory because the first digit of the second term specifies the length of this term), nor "20" (no zeros in the sequence). Therefore, a(2) = 21, the smallest unused and not self-contradictory integer so far. [Comment from _N. J. A. Sloane_, Dec 01 2015: Don't we also have to show that no larger number would give a longer final sequence?]

%e The next integer of the sequence is a(3) = 2, the length of this term being ruled by the second digit of "21", and so on.

%e The 8th integer of the sequence is "1122" and not "1111" because "1111" would block the sequence very fast: the sequence can have only nine digits "1" altogether and "1111" would force the presence of eleven integers of length one, which is impossible if they must be different one from another).

%e The same can be said for the number of digits "2" in the sequence: their number is finite and must be watched with care when building the sequence if one wants the latter to be "the longest one".

%e For example, at the point where the term a(27) = 29 occurs, one could still expect that its digit 2 will correspond to a term a(n) = 82, but some terms later it becomes clear that already the 5-digit number to which the 2nd digit of 25 referred to will contain the last digit 2: even without knowing that 82 and 92 are not allowed, the 6-digit number to which the 2nd digit of 26 refers, would exhaust the remaining possible 2s, so that it becomes clear at that point that 82 and 92 (which would come much later) can never occur, and therefore the maximum number of digits 2 is 64 and is already reached with the 5-digit number 22'223. - _M. F. Hasler_, Jan 29 2020

%e In the same way, once all the digits 2 are used, the number of digits 3 (= number of 3-digit terms) would not exceed 7^3 (7 = #{3, 4, ..., 9}). - _Carole Dubois_, Jan 28 2020

%o (PARI) A108718(n, show=1)={my(nxt(L)= my(d=digits(lu[L]++));

%o   #d>L&&return; for(i=1, #d, if(d[i]<md, my(P=10^(#d-i)); lu[L]+=P*(md-d[i])-lu[L]%P+P\9*md; for(j=i, #d, d[j]=md)); dr[d[i]]--||md++); lu[L]); dr=vector(9, k, 9^k); md=1; lu=vector(9, n, 10^n\90)*10; d=[nxt(1)]; dr[2]-=18; dr[3]-=499; dr[4]-=5821; a=if(n>1, show&&print1(1); 21, 1); dr[1]--; dr[2]--; for(n=3, n, show&&print1(", "a); d=concat(d, digits(a)); if(!a=nxt(d[n]), error("no ", d[n], " digit number left but ", sum(j=n, #d, d[j]==d[n]), " more needed."))); a} \\ Correct for some 1000 terms, beyond dr[5..9] also require adjustment. - _M. F. Hasler_, Nov 09 2015

%K base,fini,nonn

%O 1,2

%A _Eric Angelini_, Jun 21 2005

%E Typo in a(57) corrected by _Hans Havermann_, Oct 25 2015