|
%I #56 Jul 13 2021 01:37:01
%S 1,1,1,1,1,1,1,1,1,2,1,2,2,2,2,2,2,2,2,2,3,1,2,2,2,2,2,2,2,2,2,3,1,2,
%T 2,2,2,2,2,2,2,2,3,1,2,2,2,2,2,2,2,2,2,3,1,2,2,2,2,2,2,2,2,2,3,1,2,2,
%U 2,2,2,2,2,2,2,3,1,2,2,2,2,2,2,2,2,2,3,1,2,2,2,2,2,2,2,2,2,3,1,2,1,2,2,2,2
%N Number of steps to reach 0 when iterating A261424(x) = x - (the largest palindrome less than x), starting at n.
%C The sequence "minimum number of palindromes that sum up to n", A261675, coincides with this sequence up to a(301). But then a(302) = 3 since 302 = 292 + 9 + 1, whereas 302 = 111 + 191.
%C While it has been conjectured [proved by Cilleruelo & Luca, 2016 -Ed.] that every number can be represented as a sum of at most 3 palindromes, the terms of this sequence, which correspond to a greedy representation, can be larger than 3 (see A109326). For example, 1022 can be represented as 33 + 989, but a(1022) = 4, because the greedy decomposition gives 1022 = 1001 + 11 + 9 + 1. - _Giovanni Resta_, Aug 20 2015
%C Presumably this sequence is unbounded (compare A109326). - _N. J. A. Sloane_, Sep 02 2015
%C This sequence is unbounded. Let n(1) := 1. To construct n(j+1), take a natural number m with 10^m > n(j) and set n(j+1) := 10^(2m) + 1 + n(j). Then a(n(j)) = j. - _Markus Sigg_, Oct 26 2015
%C In A109326 an explicit formula for a smaller (conjectured sharp) upper bound was already given earlier. - _M. F. Hasler_, Sep 09 2018
%H Giovanni Resta, <a href="/A088601/b088601.txt">Table of n, a(n) for n = 1..10000</a>
%H William D. Banks, <a href="http://arxiv.org/abs/1508.04721">Every natural number is the sum of forty-nine palindromes</a>, arXiv:1508.04721 [math.NT], 2015 and <a href="https://www.emis.de/journals/INTEGERS/papers/q3/q3.Abstract.html">INTEGERS 16 (2016) A3</a>
%H Javier Cilleruelo, Florian Luca and Lewis Baxter, <a href="https://arxiv.org/abs/1602.06208">Every positive integer is a sum of three palindromes</a>, arXiv:1602.06208 [math.NT], 2016-2017.
%H M. F. Hasler, <a href="/wiki/User:M._F._Hasler/Work_in_progress/Sum_of_palindromes">Sum of palindromes</a>, OEIS wiki, Sept. 2015
%H Markus Sigg, <a href="http://arxiv.org/abs/1510.07507">On a conjecture of John Hoffman regarding sums of palindromic numbers</a>, arXiv:1510.07507 [math.NT], 2015.
%F a(n) < log_2(log_10(n)) + 3. - _M. F. Hasler_, Sep 09 2018
%e a(10) = 2: f(10) = 10-9 = 1, f(1) = 1-1 = 0, two steps.
%p # From _N. J. A. Sloane_, Aug 28 2015
%p # P has list of palindromes
%p palfloor:=proc(n) global P; local i;
%p for i from 1 to nops(P) do
%p if P[i]=n then return(n); fi;
%p if P[i]>n then return(P[i-1]); fi;
%p od:
%p end;
%p GA:=proc(n) global P,palfloor; local a,i,k;
%p a:=1; k:=n;
%p for i from 1 to 30 do
%p if k-palfloor(k)=0 then return(a);
%p else k:=k-palfloor(k); a:=a+1; fi;
%p od; end;
%p [seq(GA(n),n=0..200)];
%t Length@ NestWhileList[f, #, # > 0 &] & /@ Range@ 105 - 1 (* _Michael De Vlieger_, Oct 26 2015 *)
%o (PARI) ispal(n) = my(d=digits(n)); Vecrev(d)==d;
%o fp(n) = {while(!ispal(n), n--); n;}
%o a(n) = {nb = 0; while (n, n -= fp(n); nb++); nb;} \\ _Michel Marcus_, Aug 20 2015
%o /* The above fp() is extremely inefficient already for mid-sized numbers. The PARI function A261423 should be preferred.*/
%o (PARI) A088601(n)=for(i=1,oo,(n-=A261423(n))||return(i)) \\ _M. F. Hasler_, Sep 09 2018
%o (Python)
%o def P(n):
%o s = str(n); h = s[:(len(s)+1)//2]; return int(h + h[-1-len(s)%2::-1])
%o def A261423(n):
%o s = str(n)
%o if s == '1'+'0'*(len(s)-1) and n > 1: return n - 1
%o Pn = P(n)
%o return Pn if Pn <= n else P(n - 10**(len(s)//2))
%o def A088601(n): return 0 if n == 0 else 1 + A088601(n - A261423(n))
%o print([A088601(n) for n in range(1, 106)]) # _Michael S. Branicky_, Jul 12 2021
%Y Cf. A109326 gives index of first occurrence of n in this sequence ("greedy inverse").
%Y Cf. A002113, A261132, A261422, A261423, A261424.
%K base,easy,nonn
%O 1,10
%A _Amarnath Murthy_, Oct 13 2003
%E More terms from _David Wasserman_, Aug 11 2005
|
