cp's OEIS Frontend

A088601 Number of steps to reach 0 when iterating A261424(x) = x - (the largest palindrome less than x), starting at n.

%I A088601 #56 Jul 13 2021 01:37:01
%S A088601 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 A088601 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 A088601 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 A088601 Number of steps to reach 0 when iterating A261424(x) = x - (the largest palindrome less than x), starting at n.
%C A088601 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 A088601 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 A088601 Presumably this sequence is unbounded (compare A109326). - _N. J. A. Sloane_, Sep 02 2015
%C A088601 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 A088601 In A109326 an explicit formula for a smaller (conjectured sharp) upper bound was already given earlier. - _M. F. Hasler_, Sep 09 2018
%H A088601 Giovanni Resta, <a href="/A088601/b088601.txt">Table of n, a(n) for n = 1..10000</a>
%H A088601 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 A088601 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 A088601 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 A088601 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 A088601 a(n) < log_2(log_10(n)) + 3. - _M. F. Hasler_, Sep 09 2018
%e A088601 a(10) = 2: f(10) = 10-9 = 1, f(1) = 1-1 = 0, two steps.
%p A088601 # From _N. J. A. Sloane_, Aug 28 2015
%p A088601 # P has list of palindromes
%p A088601 palfloor:=proc(n) global P; local i;
%p A088601 for i from 1 to nops(P) do
%p A088601    if P[i]=n then return(n); fi;
%p A088601    if P[i]>n then return(P[i-1]); fi;
%p A088601 od:
%p A088601 end;
%p A088601 GA:=proc(n) global P,palfloor; local a,i,k;
%p A088601 a:=1; k:=n;
%p A088601 for i from 1 to 30 do
%p A088601   if k-palfloor(k)=0 then return(a);
%p A088601   else k:=k-palfloor(k); a:=a+1; fi;
%p A088601 od; end;
%p A088601 [seq(GA(n),n=0..200)];
%t A088601 Length@ NestWhileList[f, #, # > 0 &] & /@ Range@ 105 - 1 (* _Michael De Vlieger_, Oct 26 2015 *)
%o A088601 (PARI) ispal(n) = my(d=digits(n)); Vecrev(d)==d;
%o A088601 fp(n) = {while(!ispal(n), n--); n;}
%o A088601 a(n) = {nb = 0; while (n, n -= fp(n); nb++); nb;} \\ _Michel Marcus_, Aug 20 2015
%o A088601 /* The above fp() is extremely inefficient already for mid-sized numbers. The PARI function A261423 should be preferred.*/
%o A088601 (PARI) A088601(n)=for(i=1,oo,(n-=A261423(n))||return(i)) \\ _M. F. Hasler_, Sep 09 2018
%o A088601 (Python)
%o A088601 def P(n):
%o A088601     s = str(n); h = s[:(len(s)+1)//2]; return int(h + h[-1-len(s)%2::-1])
%o A088601 def A261423(n):
%o A088601     s = str(n)
%o A088601     if s == '1'+'0'*(len(s)-1) and n > 1: return n - 1
%o A088601     Pn = P(n)
%o A088601     return Pn if Pn <= n else P(n - 10**(len(s)//2))
%o A088601 def A088601(n): return 0 if n == 0 else 1 + A088601(n - A261423(n))
%o A088601 print([A088601(n) for n in range(1, 106)]) # _Michael S. Branicky_, Jul 12 2021
%Y A088601 Cf. A109326 gives index of first occurrence of n in this sequence ("greedy inverse").
%Y A088601 Cf. A002113, A261132, A261422, A261423, A261424.
%K A088601 base,easy,nonn
%O A088601 1,10
%A A088601 _Amarnath Murthy_, Oct 13 2003
%E A088601 More terms from _David Wasserman_, Aug 11 2005