|
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 |
*** Carlos Rivera
added on April 14, 2017 the following chronology about the
development of the works on this Conjecture, now totally proved.
***
|
