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."
Indeed,
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)
-(16092587554049587359044095378594045578529061-100000000000000000000000000000000000000000001)
Example #2 (p.14),
m@10=0
m=2718281828459045235360 ( 22 digits) =
+69480601060910203130333031302019060106084960 ( 44 digits, SP)
-69480601060910203130330313020190601060849600 ( 44 digits, SP)
=
+(169480601060910203130333031302019060106084961-
100000000000000000000000000000000000000000001)
-(1169480601060910203130330313020190601060849611-1100000000000000000000000000000000000000000011)
NP stands for Normal Palindrome; SP stands for Special
Palindrome.
***
|