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)

Here are some examples. I've added leading zeros for clarity:

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 solution
for 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

 

***

 

 


 

 

 

 

 

 

Records   |  Conjectures  |  Problems  |  Puzzles