A109326 -id:A109326 - 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.

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

Amarnath Murthy, Oct 13 2003

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

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

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.

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

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

# 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)];

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

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.*/

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

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

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

More terms from David Wasserman, Aug 11 2005

A261912 Numbers with palindromic order 5.

Original entry on oeis.org

101073, 101082, 101100, 101155, 101199, 102192, 102299, 103275, 103293, 103366, 103399, 103502, 104332, 104342, 104352, 104362, 104372, 104382, 104392, 104499, 104602, 105432, 105442, 105452, 105462, 105472, 105482, 105492, 105493, 105544, 105577, 105599, 105702

Offset: 1

N. J. A. Sloane, Sep 10 2015

See A261913 for definition.
In the Friedman Problem of the Month page, there is a statement by John Hoffman which, if I have interpreted it correctly, asserts that this sequence has only a finite number of terms. However, Chai Wah Wu has extended the sequence out to 10^8, finding 481384 terms, the last one being a(481384) = 99998180. This sequence does not appear to be finite.
The first terms of this sequence are just beyond A109326(5). It can be expected that at least beyond A109326(6) = 1000101024 there will be examples where N-prevpal(N) and N-prevpal(prevpal(N)) are both of order 5; these numbers could be termed to be of order 6, and so on. - M. F. Hasler, Sep 13 2015

Chai Wah Wu, Table of n, a(n) for n = 1..2278
Erich Friedman, Problem of the Month (June 1999)
M. F. Hasler, Sum of palindromes, OEIS wiki, Sep 10 2015
Chai Wah Wu, Table of n, a(n) for n = 1..481384 (zipped file)

Cf. A002113, A261907, A261910, A261911, A261913, A262528.

More terms from Chai Wah Wu, Sep 11 2015 and Sep 12 2015

A262528 Maximum number of backward steps k needed to find a representation of an n-digit decimal number x as a sum of three base-10 palindromes of the form k-th largest base-10 palindrome <= x plus a number representable as sum of two base-10 palindromes from A260255.

Original entry on oeis.org

0, 1, 1, 3, 3, 11, 4, 10, 4, 23, 9, 15, 6, 23, 11

Offset: 1

Hugo Pfoertner, Sep 26 2015

The sequence terms are counterexamples to the second part of the claim stated in the answers to the Math Magic Problem of the Month (June 1999) that "all sufficiently large numbers seem to be the sum of 3 palindromes, one of which is the biggest or second biggest possible", which would mean all a(k)=2 for k "sufficiently large".
Since exhaustive search is currently (2015) considered as not feasible, a(16)>=16, a(17)>=7, a(18)>=25, a(19)>=14 are only lower bounds for the next sequence terms.
M. Sigg has shown that a(n)>=3 for n = 5 + 4 * j.

			a(1)=0 because all 1-digit numbers are palindromes,
a(2)=a(3)=1 because all 2-digit and all 3-digit numbers can be represented by the nearest smaller palindrome and a number <=10, e.g., 201=191+9+1.
a(4)=3, because for the number 2023 the largest palindrome leading to a difference representable as sum of two palindromes is 1881. 2023-2002=21 and 2023-1991=32 are not in A260255. 2023-1881=142=141+1 is in A260255. No other 4-digit number requires more than 3 backward steps.
a(6)=11 because for the 6-digit number 101199 none of the first 10 differences 101199-101101=98, 101199-10001=1198, 101199-99999=1200, 101199-99899=1300, 101199-99799=1400, 101199-99699=1500, 101199-99599=1600, 101199-99499=1700, 101199-99399=1800, 101199-99299=1900 is representable as sum of two palindromes (i.e., are in A035137), whereas the 11th palindrome 99199 leads to 101199-99199=2000=1991+9.
a(18)>=25 because for the number x=100000001814566071 only the 25th palindrome < x 99999997779999999 produces the first difference 4034566072 representable as sum of 2 palindromes.

Erich Friedman, Problem of the Month (June 1999)
Markus Sigg, On a conjecture of John Hoffman regarding sums of palindromic numbers, arXiv:1510.07507 [math.NT], 2015.

Cf. A002113, A035137, A088601, A109326, A260255, A261132, A261675.

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A261912 Numbers with palindromic order 5.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A262528 Maximum number of backward steps k needed to find a representation of an n-digit decimal number x as a sum of three base-10 palindromes of the form k-th largest base-10 palindrome <= x plus a number representable as sum of two base-10 palindromes from A260255.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs