login
Minimal number of palindromes in base 10 that add to n.
12

%I #28 Nov 12 2018 16:50:28

%S 1,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,

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

%U 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

%N Minimal number of palindromes in base 10 that add to n.

%C This sequence coincides with A088601 for n <= 301, but differs at n=302.

%C Although A088601 and this sequence agree for a large number of terms, because of their importance they warrant separate entries.

%C Cilleruelo and Luca prove that a(n) <= 3 (in fact they prove this for any fixed base g>=5). - _Danny Rorabaugh_, Feb 26 2016

%H N. J. A. Sloane, <a href="/A261675/b261675.txt">Table of n, a(n) for n = 0..10000</a>

%H Javier Cilleruelo and Florian Luca, <a href="http://arxiv.org/abs/1602.06208">Every positive integer is a sum of three palindromes</a>, arXiv preprint arXiv:1602.06208 [math.NT], 2016.

%H William D. Banks, Every natural number is the sum of forty-nine palindromes, INTEGERS <a href="http://www.integers-ejcnt.org/vol16.html">17</a> (2016), 9 pp.

%H James Grime and Brady Haran, <a href="https://www.youtube.com/watch?v=OKhacWQ2fCs">Every Number is the Sum of Three Palindromes</a> (2018), Numberphile video

%o (PARI) ispal(n)=my(d=digits(n)); d==Vecrev(d);

%o a(n)=my(L=n\2,d,e); if(ispal(n), return(1)); d=[1]; while((e=fromdigits(d))<=L, if(ispal(n-e), return(2)); my(k=#d,i=(k+1)\2); while(i&&d[i]==9, d[i]=0; d[k+1-i]=0; i--); if(i, d[i]++; d[k+1-i]=d[i], d=vector(#d+1); d[1]=d[#d]=1)); 3; \\ _Charles R Greathouse IV_, Nov 12 2018

%Y Cf. A002113, A035137, A088601, A260255, A261422.

%K nonn,base

%O 0,11

%A _N. J. A. Sloane_, Sep 02 2015