Random Quote

Site Links

Welcome to p196.org!

The following is taken from an email from Vaughn Suite to Wade.


I did some work on checking the number of numbers that form palindromes without carries and with carries... This helps demonstrate the (im)probability of ever finding a palindrome as the number of digits increases.

I am enclosing a program (pcarry0.exe) which performs a single reverse and add on all numbers beginning with 1 digit numbers and reports those which form a palindrome. Strictly speaking, this program should operate in exponential time, each extra digit taking 10 times as long as the previous, [version 1 took 3 seconds to reach 3 digits, 31 seconds to 4 digits and 316 seconds to 5 digits on my k6-2], however there is some logical optimization which makes it faster than that, so this version took 8 seconds to 4 digits, 47 seconds to 5 digits, 474 seconds to 6 and 3340 to 7. The point is, it is still very slow.

Kruppa's data at http://home.cfl.rr.com/p196/kruppa.txt demonstrates those numbers which form a palindrome after a carry.

However, given the entire predictability of the numbers, there is no need for either a program to check whether each n digit number forms a palindrome.

For odd n >=3

A B...C D C'...B'A' will reverse and add to a palindrome of the same length if A+A', B+B', C+C' and D+D are less than 9 (no carries).

A B...C D C'...B'A' will reverse and add to a palindrom of length n+1 if A+A'=11, B+B' until C+C'=0 or 11, and D=0

For even n>=2

A B...C C'...B'A' will reverse and add to a palindrome of the same length if A+A', B+B' and C+C are less than 9 (no carries).

A B...C C'...B'A' will reverse and add to a palindrome of length n+1 if if A+A'=11, B+B' until C+C'=0 or 11.

You will see that there are 9*10^(n-1) possible n digit numbers. Of these, if n is odd, there are 225*55^((n-3)/2) numbers that form a palidrome after a single reverse and add without any carry , and 8*9^((n-3)/2) numbers that form a palindrome after a single reverse and add with a carry. If n is even, these figures are 45*55^((n-2)/2) and 8*9^((n-2)/2) respectively.

As n increases by 2, there are 100 times as many possible n digit numbers but only 55 times as many which form palindromes without carry, and 9 times as many which form palindromes with a carry.

Now, on your wish list page, you ask about the number of carries in numbers which do not form palindromes. But this is not as important as a someting actually in kruppa's data, but masked by how it is misrepresented.

Look again at the carry at the end of the first line. A two digit number 29 produces a 3 digit number, 121. The carry is not 011 as shown, but 11. The carry should be represented as the same length as the number being reversed and added.

Strip all the leading 0s from the list and the pattern becomes obvious. The carries in a number that produces a palindrome after reverse and add must be palindromic. ALL palindromes produced by a carry must have a carry in the first as well as last digit. Furthermore, the 2nd and 2nd-to-last carry must both be the same: 0 or 1, and so on for the 3rd and 3rd-to-last. If n is odd, then the middle carry must be 0; furthermore, any carry into the middle digit must be balanced by the value of the next digit, so the middle digit must be 0 so as not to affect the balance...


Now, it is so simple to prove from permutations/combinations that the above equations are correct. Using these equations, (pcarry1) shows the number of n digit numbers that form a palindrome after 1 reverse and add as n increases. Since it is a simple calculation, the answers appear instantaneously.

It is clear that there are quadrillions upon quadrillions of 120 million digit numbers that form a palindrome after a single reverse and add. How many exactly, you may ask. There are 9x10^119999999 different 120 million digit numbers. But the Windows calculator does not reach 10^325 for a 325 digit number. Nor does my OpenOffice.org Spreadsheet.

(pcarry2) uses (simple) advanced mathematics (as per pcarry1) to calculate the improbability of a 120 million digit number resolving into a palindrome.

Now, to distress ourselves even further by the magnitude of the task the palindrome quest poses, consider that by not forming a palindrome after 1 addition 196 is not one of the (225 + 8) 3 digit numbers that produce a palindrome after 1 reverse and add; and it produces 887 which is also not one. 1675 is not one of the (2475+8) 4 digit numbers which produces a palindrome after 1 add. And so on. The 120 million digit number yielded by the palindrome quest may not likely be one of the 10^104421760 (10 to the power of 104 million...) other 120 million digit numbers which actually yield a palindrome after reverse and add.

The improbability of the task is daunting!

Scientists count a 1 in 1000 chance as unlikely. This is why many modern scientists/mathematicians discount the probability of evolution having occurred.

[Quote] http://www.icr.org/pubs/imp/imp-073.htm Astro-physicists estimate that there are no more than 10^80 infinitesimal "particles" in the universe, and that the age of the universe in its present form is no greater than 10^18 seconds (30 billion years). Assuming each particle can participate in a thousand billion (10^12) different events every second (this is impossibly high, of course), then the greatest number of events that could ever happen (or trials that could ever be made) in all the universe throughout its entire history is only 10^80 x 10^18 x 10^12, or 10^110 (most authorities would make this figure much lower, about 10^50). Any event with a probability of less than one chance in 10^110, therefore, cannot occur. Its probability becomes zero, at least in our known universe.

Thus, the above-suggested ordered arrangement of 100 components has a zero probability. It could never happen by chance. Since every single living cell is infinitely more complex and ordered than this, it is impossible that even the simplest form of life could ever have originated by chance. Even the simplest replicating protein molecule that could be imagined has been shown by Golay1 to have a probability of one in 10^450. Salisbury2 calculates the probability of a typical DNA chain to be one in 10^600. [end quote]

The entire improbabilty of the 120 million digit set, or any other, eventually yielding a palindrome is striking.

We are not going anywhere.

The value of the comparison of software products, in my mind, is to see who can go nowhere fastest!!!

Unfortunately, with the exponential increase in time with linear increases in digit length, we must really plan to be here for the long haul.

But if it solves, it would be great, wouldn't it?


Vaughn Suite