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

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, 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, 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

Offset: 1

Author

Amarnath Murthy, Oct 13 2003

Keywords

• base
• easy
• nonn

Comments

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.

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

Presumably this sequence is unbounded (compare A109326). - N. J. A. Sloane, Sep 02 2015

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

In A109326 an explicit formula for a smaller (conjectured sharp) upper bound was already given earlier. - M. F. Hasler, Sep 09 2018

Examples

			a(10) = 2: f(10) = 10-9 = 1, f(1) = 1-1 = 0, two steps.
		

Links

• Giovanni Resta, Table of n, a(n) for n = 1..10000
• William D. Banks, Every natural number is the sum of forty-nine palindromes, arXiv:1508.04721 [math.NT], 2015 and INTEGERS 16 (2016) A3
• Javier Cilleruelo, Florian Luca and Lewis Baxter, Every positive integer is a sum of three palindromes, arXiv:1602.06208 [math.NT], 2016-2017.
• M. F. Hasler, Sum of palindromes, OEIS wiki, Sept. 2015
• Markus Sigg, On a conjecture of John Hoffman regarding sums of palindromic numbers, arXiv:1510.07507 [math.NT], 2015.

Crossrefs

Cf. A109326 gives index of first occurrence of n in this sequence ("greedy inverse").

Cf. A002113, A261132, A261422, A261423, A261424.

Programs

Maple

# From N. J. A. Sloane, Aug 28 2015
# P has list of palindromes
palfloor:=proc(n) global P; local i;
for i from 1 to nops(P) do
   if P[i]=n then return(n); fi;
   if P[i]>n then return(P[i-1]); fi;
od:
end;
GA:=proc(n) global P,palfloor; local a,i,k;
a:=1; k:=n;
for i from 1 to 30 do
  if k-palfloor(k)=0 then return(a);
  else k:=k-palfloor(k); a:=a+1; fi;
od; end;
[seq(GA(n),n=0..200)];

Mathematica

Length@ NestWhileList[f, #, # > 0 &] & /@ Range@ 105 - 1 (* Michael De Vlieger, Oct 26 2015 *)

PARI

ispal(n) = my(d=digits(n)); Vecrev(d)==d;
fp(n) = {while(!ispal(n), n--); n;}
a(n) = {nb = 0; while (n, n -= fp(n); nb++); nb;} \\ Michel Marcus, Aug 20 2015
/* The above fp() is extremely inefficient already for mid-sized numbers. The PARI function A261423 should be preferred.*/

PARI

A088601(n)=for(i=1,oo,(n-=A261423(n))||return(i)) \\ M. F. Hasler, Sep 09 2018

Python

def P(n):
    s = str(n); h = s[:(len(s)+1)//2]; return int(h + h[-1-len(s)%2::-1])
def A261423(n):
    s = str(n)
    if s == '1'+'0'*(len(s)-1) and n > 1: return n - 1
    Pn = P(n)
    return Pn if Pn <= n else P(n - 10**(len(s)//2))
def A088601(n): return 0 if n == 0 else 1 + A088601(n - A261423(n))
print([A088601(n) for n in range(1, 106)]) # Michael S. Branicky, Jul 12 2021

Formula

a(n) < log_2(log_10(n)) + 3. - M. F. Hasler, Sep 09 2018

Extensions

More terms from David Wasserman, Aug 11 2005