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

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

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.

Formula

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

Example

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

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 *)

Prog

(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

Crossrefs

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

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

Sequence in context: A257317 A163376 A261913 * A261675 A028950 A094916

Adjacent sequences: A088598 A088599 A088600 * A088602 A088603 A088604

Keyword

base,easy,nonn

Author

Amarnath Murthy, Oct 13 2003

Extensions

More terms from David Wasserman, Aug 11 2005

Status

approved