Problems & Puzzles: Problems

Problem 66. Every positive integer is the sum of 3 palindromes. Looking for another proof.

"La elegancia en matemáticas no es indispensable, pero se agradece". Ramón David Aznar.

On February 2016, Javier Cilleruelo and Florian Luca published a demonstration of the following theorem:

Let g 5. Then any positive integer can be written as a sum of three base g palindromes.

The proof, according to the experts, is correct. The proof is "algorithmic".

Perhaps the two best values of the proof are:

a) It improves the W. D. Banks previous result (2015), who demonstrated that "every positive integer can be written as a sum of at most 49 base 10 palindromes".

b) Being algorithmic, it provides a mean to compute at least one solution.

In another place, Cilleruelo wrote "El algoritmo que utilizamos es complejo pero elemental, en el sentido que no se utilizan matemáticas profundas... la casuística es tan compleja que hace que el artículo se alargue hasta las 39 páginas"

Yes, indeed.

For me, the proof from Cilleruelo & Luca is still not awful but ugly. Why?

In short, the demonstration divides the integers in "small integers" (6 or less digits) and "large integers" (7 or more digits). The large integers are divided in two types "normal large integers" and "special large integers". For the solution of the "normal large integers" there are 4 algorithms. For the solution of the "special large integers" there is a 5th algorithm. For the small integers there are more that 22 schemes of solution...

Q1. Is someone out there that could attempt to simplify the proof, that is to say, to reduce the quantity of algorithms and schemes to get one solution for every integer?

Q2. What if we change to the following statement: "Any positive integer can be written as an algebraic sum of three palindromes, base 10"? Is this statement easier to probe and compute than the original one from Cilleruelo & Luca?

Here we are trying to follow the lucky fate of the Kurchan's conjecture, but without using the "special palindromes" used there. See Conjecture 79.

Emmanuel Vantieghem wrote on March 03, 2017:

I cannot answer  Q1 and just give a partial answer to  Q2.
But, using Dmitri's proof of the theorem that every number is the difference of two special palindromes, I can prove in a simple way :
"Every number is the algebraic sum of four (normal) palindromes."
Let  s  be a special palindrome.  Say, s  = an n-digit palindrome p followed by  k zeros or s = p(0)k Then it is easily seen that s is the difference of two normal palindromes: s =p(0)k= (1)kp(1)k - (1)k(0)n(1)k, where n is the number of digits in p.
(example : 364546300 = 11364546311 - 11000000011).
Now, any number  m  can be written as  s1 - s2, two special palindromes.
Since  s1 = a1 - b1 (two palindromes)  and  s2 = a2 - b2 (also two palindromes), we have m = a1 - b1 - a2 + b2, QED.
Of course, if   m  is not divisible by 10, then Dmitri's theorem states that  m  is the difference of a normal palindrome and a special palindrome.  In this special case  m can be written as an algebraic sum of three normal palindromes.


Carlos Rivera applies the Dmitry's algorithm and the Emmanuel's ideas to the following two examples. Both examples come from the Cilleruelo and Luca paper:

Example #1 (p.12), m@10<>0

m=314159265358979323846 ( 21 digits) =
+6092587554049587359044409537859404557852906 ( 43 digits, NP)
-6092587554049587359044095378594045578529060 ( 43 digits, SP)
+6092587554049587359044409537859404557852906 ( 43 digits, NP)

Example #2 (p.14), m@10=0

m=2718281828459045235360 ( 22 digits) =
+69480601060910203130333031302019060106084960 ( 44 digits, SP)
-69480601060910203130330313020190601060849600 ( 44 digits, SP)
+(169480601060910203130333031302019060106084961-         100000000000000000000000000000000000000000001)

NP stands for Normal Palindrome; SP stands for Special Palindrome.


Records   |  Conjectures  |  Problems  |  Puzzles