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.

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

Offset: 1

Author

Hugo Pfoertner, Sep 26 2015

Keywords

• nonn
• base
• more

Comments

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.

Examples

			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.
		

Links

• 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.

Crossrefs

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