Welcome to p196.org!
From one of Jason's emails:
I am very curious. I remember I read somewhere that out of all the numbers under 5,000 or something like that, all numbers fell into one of 3 seeds (I assume one of 196, 879, or 1997 - from the numbers above in this email), and I couldn't believe it. I would have assumed there would be 100's of them. It was very intriguing that they all fell into 3. It makes it seem that there is something very special with those numbers - that all others which do not become palindromes fall into one of them - if they don't, they become palindromes! It could help provide data to prove, once and for all, that 196 will never solve out!
Personally, I would be sad to find a proof that 196 has no palindromic solution. I have spent a lot of time on that number, and.... Well.... You understand.
On the other hand, I would love to find something common to the numbers that have no palindromic solution!! That is why I decided that there needs to be a list of them somewhere. So that people can look at them, poke them with a stick, and just generally give them a bit of thought. Is there a commonality among them? We know that 196 is the smallest one, what is the largest one we know of? (Infinity doesn't count. I have already decided that Infinity itself must be a palindrome. :-) )
Jason, Istvan and I have talked about these numbers. The following are some of the notes that I compiled from the discussions, as well as the best probable approach to efficiently searching for the next larger Lychrel Number... The first half of the work below can be credited to Jason Doucette. Istvan is the one who explained it to me, but I believe that he was explaining what Jason had already done for efficiently searching in his Longest Delayed Palindrome work. I tried to rewrite it simply, so that people like me could understand it, with a little thought. I think most of the second step is Istvan's work and ideas. (It's difficult sometimes to remember who contributed what, and ensure that they are recognized!!) I doubt that I added very much to the discussion..... :-(
It would be easy enough to begin with a list of every number between two given points. Say, 0-1,000,000.
The first obvious step to me, would be to go through the list and delete any numbers that are already palindromes. This will eliminate a bunch of numbers right from the start.
One of the first things we must do is find and eliminate all of the numbers that will follow the same thread over the long run. For example, 196, 295, 394, 493, 592, 691 will all form 887 on the first iteration, and then everything after that will be identical for all 6 numbers. Right off the bat, we would have a lot of redundancy of computing time, if we didn't eliminate the numbers other than 196. The time savings would be SUBSTANTIAL!!
So we would perform 1 iteration of each of those numbers, find out that they all lead to 887, then delete 295, 394, 493, 592, and 691 from our list.
From this point of view, we have to examine the corresponding digit pairs, the first and the last, the second and the last minus one, the third and last minus 2 etc. Whenever these number pairs give the same sum, the reversal/addition procedure will produce the same result.
There are 18 outer digit pairs which will result in different sums.
1xx0
1xx1
1xx2
...
1xx8
1xx9
And the following eight:
2x...x9
3x...x9
4x...x9
5x...x9
6x...x9
7x...x9
8x...x9
9x...x9
Any other combination will result in a duplicate number after the first iteration.
Next, there are 19 inner digit pairs (because in this case we allow the first of the pair to be zero).
x0xx...xx1x
x0xx...xx2x
x0xx...xx3x
etc.
This will work for all of the even digit numbers. If the number being examined has an odd number of digits, we should multiply by ten, because of the digit in the middle:
xxx1xxx
...
xxx9xxx
As you can see, to calculate, for example, how many iterations are needed to check all those 7 digit numbers which differ in the digit pair sums, we should multiply these coefficients:
18 is for the outer pair of digits, 10 is for the middle digit, 19^2 is for the two inner pairs. You can see how much faster this search would be in the long run.
We can even construct a general formula to calculate the number of numbers to be checked:
18*19^((n-2) div 2)*10^(n mod 2)
n is the length of the number, and should be larger than 1. The 10^(n mod 2) part gives 10 for odd lengths, 1 for even lengths.
The following table may help to demonstrate:
NOTE: This is not complete. It is only an example of what would have to be done to check numbers between 3 and 17 digits.
| Number of Digits | Total Digits | Numbers to be Checked | Ratio | Every Nth to be Checked |
3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 SUM: |
900 9,000 90,000 900,000 9,000,000 90,000,000 900,000,000 9,000,000,000 90,000,000,000 900,000,000,000 9,000,000,000,000 90,000,000,000,000 900,000,000,000,000 9,000,000,000,000,000 90,000,000,000,000,000 99,999,999,999,999,900 |
180 342 3,420 6,498 64,980 123,462 1,234,620 2,345,778 23,457,780 44,569,782 445,697,820 846,825,858 8,468,258,580 16,089,691,302 160,896,913,020 186,819,193,422 |
20.000000% 3.800000% 3.800000% 0.722000% 0.722000% 0.137180% 0.137180% 0.026064% 0.026064% 0.004952% 0.004952% 0.000941% 0.000941% 0.000179% 0.000179% 0.000187% |
5 26 26 138 138 728 728 3,836 3,836 20,193 20,193 106,279 106,279 559,364 559,364 535,276 |
So, if we are only going search numbers between 3 and 17 digits, there are 186,819,193,422 numbers that should be checked in order to only check one consequence of each thread.
Second step: filtering out the independent Seed Numbers.
The next thing to do would be to begin the reverse/add process for each of the remaining numbers and eliminate the upstream numbers for each. For example, if we were going to 9 digits, 887 / 7,436 / 13,783 / 52,514 / 94,039 / 187,088 / 1,067,869 / 10,755,470 / 18,211,171 / 35,322,452 / 60,744,805 / 111,589,511 / 227,574,622 / 454,050,344 and 897,100,798 would all have to be removed from the list, since they are all in the 196 thread. At the same time, any numbers that lead to a palindrome, will be deleted. For example, 89, 187, 968, 1837, ... 8,813,200,023,188 would all be deleted, since 89 will become a palindrome in 24 iterations.
When you are finished, anything left on your list, should be a Seed Number......
I admit that this is not the only way to search for these numbers. It might not be the easiest to program. It might not be anywhere near the fastest way to find these numbers. But it is one way that seems sound.