Problems & Puzzles: Conjectures

Conjecture 79. Rodolfo Kurchan's Conjecture

Claudio Meller, in his always intersting site, posted the entry 1472 related to the following conjecture original from Rodolfo Kurchan:

"The most of the integers may be expressed as a sum of two palindromes. These few integers that do not fit the previous rule, may be expressed as a sum of one normal palindrome and another 'special palindrome' that accepts k zeros to the left of a central normal palindrome and ends in k zeros to the right of the central palindrome" (Original Version)

Examples:

a) Using two normal palindromes:
2017 = 1331 + 686
20149580973 = 19869096891 + 280484082

b) Using a normal palindrome and a special palindrome:
2001 = 1001 + 0001000
20201 = 11111 + 09090
2073 = 363 + 01710
91729 = 91619 + 0110

Claudio and Rodolfo asked for counterexamples:

Carlos Rivera found the earliest counterexample: 1200 can not be expressed as the conjecture is expressed, but needs two special palindromes: 1200 = 00100 + 001100.

After this, Claudio and Rodolfo asked if the new conjecture:

"Any integer may be expressed a sum of two palindromes, both normal or one normal and another special or two special palindromes" (Second version)

had a counterexample. This time a puzzler named "Mmonchi" found the earliest counterexample: 113001. He also sent 100 other counterexamples after 113001.

At this point Carlos Rivera observed that perhaps the 2nd Rodolfo's conjecture might be saved this way:

"Any integer may be expressed as an algebraic sum of two palindromes, both normal or one normal and another special or two special palindromes" (Third version)

because himself obtained the following solution 113001 = 0204020 - 91019

I have been told by Claudio Meller that Mmonchi has tested all the integers less than 10^5 and has verified that all of them satisfy this third version, but he can not test neither larger integers nor obtain a positive proof of the general validity of this 3rd version of the Rodolfo's conjecture

Q. Can you obtain a proof or a counterexample of the 3rd version of the Rodolfo's Conjecture?

Contributions came from Dmitry Kamenetsky, Emmanuel Vantieghem and Carlos Rivera

***

Dmitry wrote:

The conjecture is true. I will prove it by showing that an even stronger conjecture holds:

"Any integer may be expressed as a difference between two special palindromes."

My proof is by construction. Let a be the target n-digit integer that we want to obtain. Let a(i) be its i-th digit from the right. So a=sum_{i=0 to n-1) a(i)*10^i. We will now construct (2n+1)-digit integers c and b, such that c-b=a. c is a normal/special palindrome, while b is a special palindrome. We begin by setting b(0)=0, now we adjust the corresponding digit in c and replicate it on the side to make it symmetrical. So we have

b(0)=0
c(0)=a(0)+b(0)=a(0)
carry(0)=floor[(b(0)+c(0))/10]
c(2n)=c(0)
b(2n)=c(2n)
b(1)=b(2n)

We repeat the process. So for any i>0:

b(i)=b(2n+1-i)
c(i)=[a(i)+b(i)+carry(i-1)] mod 10
carry(i)=floor[(a(i)+b(i)+carry(i-1))/10]
c(2n-i)=c(i)
b(2n-i)=c(2n-i)
b(i+1)=b(2n-i)

64 = 40104 - 040040
123 = 3566653 - 03566530
1200 = 002333200 - 0002332000
2718 = 896999698 - 0896996980
113001 = 1114566654111 - 01114566541110
314159 = 9460255520649 - 09460255206490

***

Emmanuel wrote:

It was not possible to find a counterexample below 13*10^6 nor could I find a proof of the third version.
Nevertheless, I think the conjecture is true.

***

Carlos Rivera wrote:

In my humble opinion the exposition of the Dmitry's argument to demonstrate the Rodolfo's conjecture is very close, but  it is not yet, a rigorous and complete formal constructive proof, in his current state.

Additionally, as far as I understand it, the loop part of his argument never compute the central digit of "c".

Nevertheless I have made a code in Ubasic based in the Dmitry's argument lines and I have added one line to compute the central digit of "c" once the loop is done, and I have verified that it can be produced a solution to a=c-b for any integer "a" producing palindromes "b" & "c", being always "c" a special palindrome and being "b" a normal palindrome in some instances or a special palindrome in other instances.

My code in Ubasic was ran exhaustively from a=1 to a=10^8 without any wrong result.

Thus, the third version of the Rodolfo's conjecture should be considered totally valid, as soon as the complete and rigorous proof based in the constructive argument provided by Dmitry could be produced in the near future.

***

Last minute new!

Dmitry Kamenetsky has sent a new argument headed this way:

You were right my algorithm was not complete. I have corrected my algorithm and coded it up. It now computes all terms of c and I checked that it works. Please replace the old algorithm with this one (leave all the other text as is)...

But I have not been able to code and test it. As soon as I do it. I will publish right here.

***

On Jan 28, Dmitry sent a complete algorithm that computed the central term of c. Here is it:

a(n)=0   //for convenience
b(0)=0
c(0)=a(0)
carry(0)=0

for i=0 to n-1
{
b(2n-i)=c(i)
c(2n-i)=c(i)
b(i+1)=c(i)
s=a(i+1)+b(i+1)+carry(i)

c(i+1)=s mod 10
carry(i+1)=floor(s/10)

}

Carlos Rivera made a code in Ubasic to test this new algorithm and it was able to find always a correct result for a values from 1 to 10^8.

***

Emmanuel Vantieghem wrote:

...no doubt about the validity of this algorithm as proof for the conjecture. The conjecture is proved for 100%
***

Carlos Rivera wrote on Jan 1, 2017

Here is an algorithm that I have constructed as a variation of the Dmitry's one. It's intended for those that would like to compute C & B by a procedure "at hand", more than writing a program to be run in a PC.

 Illustration of the Dmitry Kamenetsky's algorithm to find a solutionfor A=C-B Being A any integer while C and B are specials palindromes A special palindrome is a palindrome nut that is followed for a string of k zeros to the right A digit dx is a digit with value d and carrying value x Example #1. Find C & B if A=123=C-B a) Initialization: Position: 14 13 12 11 10 9 8 7 6 5 4 3 2 1 A= 0 1 2 3 C= 00 b) Computation of the other digits of C, from position 2 to 5: Position: 14 13 12 11 10 9 8 7 6 5 4 3 2 1 A= 0 1 2 3 C= 6 60 50 30 00 30 = 3 + 00 50 = 2 + 30 60 = 1 + 50 6 = 0 + 60 c) Making palindromia just in the coloured cells of C Position: 14 13 12 11 10 9 8 7 6 5 4 3 2 1 A= 0 1 2 3 C= 3 5 6 6 60 50 30 00 d) Momentarily B=C Position: 14 13 12 11 10 9 8 7 6 5 4 3 2 1 A= 0 1 2 3 C= 3 5 6 6 60 50 30 00 B= 3 5 6 6 6 5 3 0 e) Eliminating digits in position 1 and 5 from C and B, respectively. Position: 14 13 12 11 10 9 8 7 6 5 4 3 2 1 A= 0 1 2 3 C= 3 5 6 6 60 50 30 00 B= 3 5 6 6 6 5 3 0 f) Verification C= 3566653 Normal palindrome B= 3566530 Special palindrome A=C-B 123 OK

 Example #2. Find C & B if A=56789=C-B a) Initialization: Position: 14 13 12 11 10 9 8 7 6 5 4 3 2 1 A= 0 5 6 7 8 9 C= 00 b) Computation of the other digits of C, from position 2 to 7: Position: 14 13 12 11 10 9 8 7 6 5 4 3 2 1 A= 0 5 6 7 8 9 C= 8 80 21 51 71 90 00 Same procedure than in Example #1 c) Making palindromia just in the coloured cells of C Position: 14 13 12 11 10 9 8 7 6 5 4 3 2 1 A= 0 5 6 7 8 9 C= 9 7 5 2 8 8 80 21 51 71 90 00 d) Momentarily B=C Position: 14 13 12 11 10 9 8 7 6 5 4 3 2 1 A= 0 5 6 7 8 9 C= 9 7 5 2 8 8 80 21 51 71 90 00 B= 9 7 5 2 8 8 8 2 5 7 9 0 e) Eliminating digits in position 1 and 7 from C and B, respectively. Position: 14 13 12 11 10 9 8 7 6 5 4 3 2 1 A= 0 5 6 7 8 9 C= 9 7 5 2 8 8 80 21 51 71 90 00 B= 9 7 5 2 8 8 8 2 5 7 9 0 f) Verification C= 97528882579 Normal palindrome B= 97528825790 Special palindrome A=C-B 56789 OK

 More examples without details Verification, A=C-B OK? A= 0 1 2 3 123 C= 3 5 6 6 60 50 30 00 3566653 B= 3 5 6 6 6 5 3 0 3566530 OK A= 0 5 6 7 8 9 56789 C= 9 7 5 2 8 8 80 21 51 71 90 00 97528882579 B= 9 7 5 2 8 8 8 2 5 7 9 0 97528825790 OK A= 0 6 4 64 C= 4 0 1 01 40 00 40104 B= 4 0 1 0 4 0 40040 OK A= 0 1 2 0 0 1200 C= 0 0 2 3 3 30 20 00 00 00 2333200 B= 0 0 2 3 3 3 2 0 0 0 2332000 OK Please notice in this example that B & C are special palindromes! A= 0 1 1 3 0 0 1 113001 C= 1 1 1 4 5 6 6 60 50 40 10 10 10 00 1114566654111 B= 1 1 1 4 5 6 6 6 5 4 1 1 1 0 1114566541110 OK

***

Carlos Rivera added on April 14, 2017 the following chronology about the development of the works on this Conjecture, now totally proved.

 Chronology of the developments about the quantity of palindromes needed to express an integer. No. Date Who What 1 19-ago-15 W. D. Banks Publishes that Every integers is the sum of 49 palindromes 2 19-feb-16 J. Cirelluelo & Florian Luca Publish that Every integers is the sum of 3 palindromes 3 01-ene-17 Claudio Meller/Rodolfo Kurchan Publish "Entry 1472". Conjecture of Rodolfo Kurchan: Every integer is the sum of 2 palindromes, one normal and one special. 4 03-ene-17 Carlos Rivera Contribution to Entry 1472: 1200 is the smallest counterexample to the original RK Conjecture. Perhaps the Conjecture might be saved this way: Every integer is the sum of 2 special palindromes (2nd version) 5 04-ene-17 Ramón David Aznar Contribution to Entry 1472: 113001 is the smallest counterexample to the second version of RK conjecture. 6 05-ene-17 Carlos Rivera Contribution to Entry 1472: Perhaps Every integer is the algebraic sum of 2 special palindromes (3rd version). Example: 113001 =0204020 -91019 7 21-ene-17 Carlos Rivera Publishes the "Conjecture 79" in his web site. Asking to prove the RK Conjecture. 3rd version. 8 25-ene-17 Dmitry Kamenetsky Contribution to Conjecture 79: Sends his first algorithmic proof. 9 26-ene-17 Carlos Rivera Contribution to Conjecture 79: Points out a fail in the DK proof 10 27-ene-17 Dmitry Kamenetsky Contribution to Conjecture 79: Sends his second algorithmic proof. 11 28-ene-17 Carlos Rivera Contribution to Conjecture 79: Points out a fail in the DK second proof 12 28-ene-17 Dmitry Kamenetsky Contribution to Conjecture 79: Sends his third algorithmic proof. No fail is detected this time. 13 25-feb-17 Carlos Rivera Publishes the "Problem 66" in his web site- Asking to improve the Cirelluelo & Luca proof. 14 03-mar-17 Emmanuel Vantieghem Contribution to Problem 66: He observes that any special palindrome may be expressed as a difference between two normal palindromes and combines this observation  with the DK proof to assert that "every integers is the algebraic sum of at the most three or four palindromes"

***

 Records   |  Conjectures  |  Problems  |  Puzzles