login
A108718
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.
1
1, 21, 2, 11, 3, 4, 111, 1122, 5, 6, 7, 8, 9, 22, 23, 22222, 222222, 2222222, 22222222, 222222222, 24, 25, 26, 222, 27, 28, 29, 32, 33, 34, 35, 36, 37, 38, 39, 42, 43, 44, 45, 46, 47, 48, 49, 52, 53, 54, 55, 56, 57, 58, 59, 62, 63, 64, 65, 66, 67, 68, 69, 72, 2222, 73
OFFSET
1,2
COMMENTS
The sequence is finite - but what is the last term?
It is not yet known whether the sequence is well-defined with the current wording of its name. - M. F. Hasler, Dec 01 2015
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
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
LINKS
E. Angelini, Last term?, SeqFan list, Oct. 25, 2015.
EXAMPLE
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.
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.
This "1" indicates that the first integer of the sequence must have length one - which is the case.
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?]
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.
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).
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".
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
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
PROG
(PARI) A108718(n, show=1)={my(nxt(L)= my(d=digits(lu[L]++));
#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
CROSSREFS
Sequence in context: A040438 A040439 A174429 * A083122 A040440 A040431
KEYWORD
base,fini,nonn
AUTHOR
Eric Angelini, Jun 21 2005
EXTENSIONS
Typo in a(57) corrected by Hans Havermann, Oct 25 2015
STATUS
approved