|
%I #15 Aug 20 2017 23:18:05
%S 1,2,3,4,5,6,7,8,9,11,29,13,49,15,69,17,89,19,199,21,399,23,599,25,
%T 799,27,999,30,2999,3999,32,5999,34,7999,36,9999,38,29999,40,49999,42,
%U 69999,44,89999,46,199999,48,399999,499999,51,699999,53,899999,55,1999999,57
%N Lexicographically earliest injective sequence such that a(n) = A007953(a(a(n))), where A007953 = sum of digits (in base 10).
%C "Lexicographically earliest" means that the sequence is constructed by choosing a(n) to be the smallest positive integer not leading to a contradiction; "injective" means that a number may occur only once, and is thereafter excluded from the possible choices for subsequent terms.
%C Open problems: (1) Prove that a(n) > n for all n > 9.
%C (2) Prove that the subsequence of terms not ending in "9" is strictly increasing.
%C (3) Prove the given formula for a(n).
%C (4) Find an explicit formula for indices n where a(n) = m*10^k - 1.
%H M. F. Hasler, <a href="/A167152/b167152.txt">Table of n, a(n) for n=1..999</a>
%H E. Angelini, <a href="http://www.cetteadressecomportecinquantesignes.com/Digitsum.htm">a(n) is the digitsum of a(a(n))</a>, November 2009.
%H E. Angelini, <a href="/A167152/a167152.pdf">a(n) is the digitsum of a(a(n))</a> [Cached copy, with permission]
%F If n < 10 or n is in { a(1), ..., a(n-1) }, then a(n) = (n mod 9 + 1)*10^floor(n/9) - 1 (= n for n < 10).
%F Otherwise, a(n) = n+1 unless n+1 occurred earlier in the sequence (and therefore is of the form k*10^m - 1), in which case a(n) = n+2 (conjectured).
%o (PARI) /* This code is for illustration and "experimental verification"; several important simplifications could be made to compute a(n) efficiently. */
%o A167152(n, output=0, u=[])={ my(a=vector(n),k); for( i=1+#u,#a, if( setsearch( u,i )
%o ,/* this index has already appeared, so this a(n) must have that digit sum */
%o k= ((i % 9)+1)*10^(i\9)-1; /* this k is the smallest number with digit sum i; this should work "at once" and the loop below should not be needed */
%o while( A007953(k) != i | setsearch(u, k), k+=10^(i\9-1)*9 /*e.g. to 89 we add 9*/)
%o ,/* index has not yet appeared: choose smallest number not yet used and not leading to contradiction */
%o /* is it possible that a[i] = k < i ? Clearly a[i] = i iff i <= 9, else digsum(i)<i. */
%o k=1; while( setsearch(u,k) | (k<=i & A007953(if( k<i, a[k], i)) != k), k++);
%o )/*end if i in u */;
%o output & if( #output>1, write(output,i" "k),print1(k,", ")); u=setunion( u, Set(a[i]=k))
%o )/* end for i */; k}
%K nonn,base
%O 1,2
%A _Eric Angelini_ and _M. F. Hasler_, Nov 02 2009
%E Edited by _Charles R Greathouse IV_, Aug 02 2010
|
