|
|
A088601
|
|
Number of steps to reach 0 when iterating A261424(x) = x - (the largest palindrome less than x), starting at n.
|
|
9
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
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
|
|
|
FORMULA
|
|
|
EXAMPLE
|
a(10) = 2: f(10) = 10-9 = 1, f(1) = 1-1 = 0, two steps.
|
|
MAPLE
|
# 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.*/
(Python)
def P(n):
s = str(n); h = s[:(len(s)+1)//2]; return int(h + h[-1-len(s)%2::-1])
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))
|
|
CROSSREFS
|
Cf. A109326 gives index of first occurrence of n in this sequence ("greedy inverse").
|
|
KEYWORD
|
base,easy,nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|