I look into a bit and find that someone has written a 40 page proof showing this to be true. I don't much care for academic papers. There might be reasons why they are written like they are, but providing a clear explanation does not seem to be one of them. Besides, I should be able to throw together a program to test this out. How hard can it be?
My basic idea was to make the biggest palindrome that was smaller than the given number, subtract it, and then repeat one more time to get the third number. If the last number is a palindrome, great, we're done. If not, go back to the previous step and find the next smaller palindrome. Repeat until the third number is a palindrome, or if it is smaller than the result. In that case, go back to the first step and find the next smaller palindrome.
I wrote the program to try this and immediately ran into a problem. Take a number like 1234567. You can make a palindrome that will take care of the bulk of the sum by simply using the first 3 digits as the last 3 in reverse order, like this: 1234321. This works fine until you get something like 1234111. Now you can still get a big chunk making 3 digit numbers from the first three and the last three digits and then using the smaller one to generate a palindrome, in this case it would be 1114111. That's a little better, but what about something like 1234000? Now we need to reduce the low order digit of first four digits, i.e. the center digit. Now we get 1233321.
Take the first half of the digits in the number and make a palindrome. If it is larger than the original number, decrement the center digit. If there are an even number of digits, use the digit just to the left of center.
I wrote the program to try this and immediately ran into a problem. Take a number like 1234567. You can make a palindrome that will take care of the bulk of the sum by simply using the first 3 digits as the last 3 in reverse order, like this: 1234321. This works fine until you get something like 1234111. Now you can still get a big chunk making 3 digit numbers from the first three and the last three digits and then using the smaller one to generate a palindrome, in this case it would be 1114111. That's a little better, but what about something like 1234000? Now we need to reduce the low order digit of first four digits, i.e. the center digit. Now we get 1233321.
Take the first half of the digits in the number and make a palindrome. If it is larger than the original number, decrement the center digit. If there are an even number of digits, use the digit just to the left of center.
If the first half of the number is a one followed by zeroes (i.e. ten raised to some power, like 100 or 1000) and you subtract 1, then your number is going to have one fewer digits and if you follow our previous rule for constructing a new palindrome, it will have 2 fewer digits, so we need to make some adjustments.
Since we are losing a digit, any number we create using our prefix will be smaller than our starting number, so we may as well make the most of it and just make it all 9's:
Start with 10004xxxx
Our new palindrome will be 99999999
For some reason, probably because I wasn't sleeping all that well, I had a very hard time figuring out this business of making the next smaller palindrome. In the last couple of weeks, my mind is back in gear and I got it all sorted out.
The program runs fine. Starting from 0, it can find a three number sum for any integer. So far it has gotten up to the hundreds of millions. I was kind of hoping that by watching the output of this program, a mystic crystal revelation would appear and I would grok the essence of palindromic splendor. That hasn't happened.
The program has been running for 20 odd minutes and it has been counting the number of digits in the third palindrome and these are the results so far:
Have not found any 3rd palindromes with a length greater than 5
So it's a trivial problem, doesn't seem to have any special significance, but it kept me entertained for a bit. Numberphile did a video about this. I gave up watching about half way through because I wasn't going to go through all their gyrations. I suspect the idea in the paper is that you can derive the three numbers without having to test your results, but from what I've seen their method requires a great deal more work than mine.
3 comments:
Reminds me of when the highschool math teacher would call on you to do HIS job
presumably the article unpacked by numberphile asserts that EVERY number of any length has three palindromes that will sum to it, and that the three can be found using their more complex algorithm.
Your code identifies a solution for every number tested so far. Practical engineering approach. What if there is a counterexample out there in the realm of numbers, say 30 to 40 digits long?
drharris - Yes, I haven't groked just what is going on, but after watching this program run for a while, it doesn't seem likely that it will ever encounter a number it won't be able to decompose. I suppose there could be one, but it seems unlikely. I might write some tests to see which numbers require the most work to decompose, then something might be revealed.
Post a Comment