The Results MONDAY, JUNE 17, 2002 UPDATE: I have not been able to run my program since Friday, August 4, 2000.At the time, I only had 8.34% of all the 15 digit numbers solved.I could not continue because the program was written in DOS underFlat Mode, which refuses to run under Windows 98 or greater.These operating systems no longer allow the computer to be (easily) rebootedinto a fully DOS compatible mode, which is not a Windows Shell. On Sunday, May 19, 2002, I finally reprogrammed my algorithm in Windowsto allow the search to continue. It is too bad that I have waited this long,because I would be far into the 17 digit numbers right now. After some initial beta-testing, I started the new programagain from scratch on Thursday, March 30, 2002. It has sincereached, and surpassed the numbers checked of my old DOS program.Note that it is only running part time on my AMD 1700+ XP processor. The records, including the World Record for Most Delayed Palindromic Number(highlighted in red),are listed in the below table. Click on any of the numbers to pop-up a calculationpage that proves its result. WEDNESDAY, APRIL 16, 2003 UPDATE: I am now into the 17 digit numbers. This is going to be an interesting set ofnumbers to look at, since after the result of the 16 digit numbers, there is onlyone iteration count below thecurrent (as of April 16, 2003)world record of 201 iterations(the 15 digit number 100,120,849,299,260)that has yet to solve out: 160.Any new information to be reported by the program will either be the 160 iterationresult, or a new world record. We can guess at what the 160 iteration result would be, by iterating thesmallest number to resolve in 161 iterations (the 16 digit number 6,000,000,039,361,479)a single time.Thus we can tell that the 17 digit number 15,741,639,339,361,485will solve out in 160 iterations.Its lowest first order consequence('consequences' are explained above on this page)is 14,200,033,399,975,995.Therefore we will expect to see a result for 160 iterations which is, at largest, this 17 digit number. TUESDAY, APRIL 29, 2003 UPDATE: I have incorporatedBenjamin Despres'reverse-and-add code into my algorithm for findingMost Delayed Palindromic Numbers, as his code is approximately three timesfaster than my reversal-addition code.The core exponential algorithm that determines which numbers to testremains unchanged. I have started the quest from scratch, again,to ensure that his code is operating perfectly with my code.I have already extensively tested his code with extreme casesto ensure its accuracy. The biggest problem that I had porting his codeinto my program is that his code was not designed to be re-run multiple times.He programmed the initialization portion of it for a one-shot deal.Initialization code is normally left unoptimized as it is onlyrun once, and therefore does not matter for performance. It onlyaffects the start up time of a program, and for a process that takesseveral months (his code was computing the 196 Palindrome Quest),it does not matter if the initialization code takes 1/1,000th of a secondor 1/10,000th of a second. I re-codedthe initialization section to re-initialize only the parts of memorythat has to be for optimal performance. WEDNESDAY, JUNE 2, 2003 UPDATE: My old code had solved 0.297% of all 17 digit numbers.My new program(with Benjamin Despres' reversal-addition code)finally surpassed this today.All results match prior results.A few hours later, my program also finally found a new world record since theold recordwas found solving the 15 digit numbers.My old program was within hours of solving this new record,and was delayed for almost two monthsdue to the restarting of the program withBenjamin Despres'reversal-addition code. WEDNESDAY, JUNE 2, 2003 UPDATE: This new world record beats the old world recordthat has stood for about 3 years(set by my program sometime between November 1999 to August 2000;the exact date was never recorded)which was the 15 digit number100,120,849,299,260which resolves into a 92 digit palindrome in 201 iterations. Also, later that day, at 7:28 PM, a record for 160 iterations was found:10,019,017,999,499,510.It is lower than the number that we expected could be the potential record(14,200,033,399,975,995),and it is on a different thread (series of numbers that are formed by the reversal-addition iteration),as the resultant palindrome is different from that ofthe record for 161 iterations.(Please note that on January 28, 2004, an even smaller number for 160 iterations was found,on yet another thread:10,000,000,730,931,027.) THURSDAY, JULY 10, 2003 UPDATE: WEDNESDAY, DECEMBER 15, 2004 UPDATE: At 10:44 AM, after exactly 500 days of processing from scratch, my program(with Benjamin Despres' reversal-addition code)finally resolved all 17 digit numbers.The majority of that time (444 days of those 500) was required for just the processing of the 17 digit numbers.Due to the optimizations in my algorithm, it does not iteratively check each number.My algorithm determines which numbers can be eliminated from the search and still maintain 100% accurate results.As a result, my program actually only checked 186,819,193,449 total numbers,instead of 99,999,999,999,999,999 numbers,to compute the results of all 17-digit numbers and smaller,which is a significant optimization.It would have taken over 700,000 years, on the same computer,to compute all these numbers without this optimization. MONDAY, MARCH 21, 2005 UPDATE: Vaughn Suite has corresponded with me regarding my quest over the past few weeks.He suggested performing a statistical analysis of the data, to determine the likelihoodof missing a record at any given iteration limit.Using such analysis, we can set the limit to match our preferred risk.If this shows the current limitation is overkill,then we will speed up the program by reducing the limit. Originally, I took a naive approach and simply set the limit to be 3 times that of the last record found.This was done only because, at a quick glance, it appeared to suffice.It appeared quite a bit less safe than Ian Peter's limitation of 200,000 digits(about 500,000 iterations, which varies slightly depending on the number checked).I should again note thatIan Peter's workhas exhaustively shown that numbers that do not resolve quicklyseemingly never resolve.This has been crucial in allowing us to use the below statistical analysis on my data. Vaughn Suite's analysis started with the most delayed palindromic number for each digit length, as follows(updated Sunday, September 25, 2005 upon completion of the 18-digit set):
You will note that this data is not immediately known from therecords I show on this page.My Most Delayed Palindromic Number queststores only the smallest number that resolves at each iteration depth.Therefore if a record is set in a smaller digit set,any other numbers that resolve in the same amount of iterations fromlarger digit sets will not be recorded, since they are larger numbers.These numbers are not recorded even if they are themost delayed palindromic number of that digit set, simply becausethis was not the purpose of the program. For example, in the 7 digit set, the most delayed palindromic number is 9,008,299 which resolves in 96 iterations.There are two (consequences not counted)8 digit numbersthat solve in 96 iterations:15,002,893and15,059,593,but they are not recorded.The most delayed palindromic number recorded for the 8 digit set is10,309,988 which solves in only 95 iterations.The two that resolve in 96 iterations are not smaller than the7 digit number,9,008,299,that resolves in 96 iterations, and my program saves only the smallest one. Vaughn Suite verified these maximum iteration depths for each digit sethimself for all digit sets up to 13 digits,and got the maximum depths for the 15 digit and 17 digit sets from this page,and the for the 14 digit and 16 digit setsfrom my notes onWade VanLandingham's site(under Other People's Notes).He noted that the values appeared to follow a linear trend,estimated the maximum iteration depth for the 18 digit setwould likely be 250 and suggested testing to 350 iterations,instead of multiplying the last previous record by three.After some discussion, we performed linear regression analysis,which yielded the following equation: Expected Maximum Iteration Depth = 14.416667 * Digit Length - 18.338235 The standard deviation was found to be 11.245233.We concluded that we could use normal distribution to describe the data.There is a 98.83% correlation between these iteration limits and the digit length of the set they represent.(If you are a statistician, and believe this is incorrect, pleasecontact me.)Armed with this information,we did further spreadsheet analysis to determine the probabilityof a number being missed for the 18 digit set,giving any iteration limit.We could also input the probability (risk) level we were prepared to accept,and the sheet would inform us of the iteration level required for such a risk. In retrospect, I was doing far more calculations than I needed to.Using a limitation of 708 iterations for the 18 digit set representsa missed record would have to be 41.51 standard deviations away from the mean.This is an astronomically small chance. I cannot even calculate the chanceswithin Excel due to the precision limitations of the program.(If someone hasMaple,Mathematicaor anotherComputer Algebra System,pleasecontact me,and perhaps we can compute the actual amount.)To give you an idea just how crazy this is, 68% of all numbers fall within 1 SD (standard deviation) of the mean,95% fall within 2 SD, 99.7% fall within 3 SD, 99.993% fall within 4 SD,99.99994% fall within 5 SD, 99.9999998% fall within 6 SD, 99.9999999997% fall within 7 SD, etc.In another perspective, if we wish to have a 1 in 1,000 chance of missing a record, we'd set the iterationlimit 3.09 SD away from the mean. To have a 1 in 1,000,000 (one million) chance of failure,we'd set the iteration limit 4.75 SD away from the mean.For 1 in 1,000,000,000 (one billion), set it 6.00 SD away.For 1 in 1,000,000,000,000 (one thousand billion), set it 7.04 away.For 1 in 1,000,000,000,000,000 (one million billion), set it 7.94 away.Imagine what the chances of failure would be going all the way to 41.51! Thus, the quest can now be sped up by using this information.After much discussion, I personally determinedthat a 1 in 10,000,000 chance of missing a record was reasonable.This is based on my personal conjecture that when a new world record is found,there are numerous other records found for iterations just below the world record.In other words, a world record has yet been found in which there exists no otherrecords for iteration depths almost as deep as the record.Therefore, in the unlikely (1 in 10,000,000 chance) eventthat we will miss a record, we will likely know that we missed it,due the likelihood of numerous other numbers resolving in iterationdepths very close to the limit.In this case, we can increase the iteration depth, and re-test the entire data set.Yes, it would be depressing to have to redo this work,but I believe in the 1 in 10,000,000 chance that this happens,it is worth the speed up in the program. For a 1 in 10,000,000 chance of missing a record, our formulas determined an iterationdepth of 299.63 is required, therefore I set the depth to 300 for the 18 digit set.The actual chance of missing a record for a depth of 300 iterations is 1 in 11,921,892,for those who are curious. I would like to extend a great thanks to Vaughn Suite for his help.Using this information, the Most Delayed Palindromic Number questhas been sped up by over 5.5 times. SUNDAY, SEPTEMBER 25, 2005 UPDATE: On Sunday, September 25, 2005, at 3:16 am,my program(with Benjamin Despres' reversal-addition code)completed the 18-digit number set.The most delayed palindromic 18 digit number solves in 232 iterations,as you can see by the above table labelled 'Largest Delay per Digit Set'.Using this information to update the statistical analysis,we arrive at the following new formula: Expected Maximum Iteration Depth = 14.255934 * Digit Length - 17.320261 The standard deviation was found to be 11.087996.There is a 98.96% correlation between these iteration limits and the digit length of the set they represent. Using this information, for a 1 in 10,000,000 chance of missing a record,the iteration limit should be set to 311.20. I have rounded this value up to 315for the 19-digit set. A limit of 315 iterations actually represents a1 in 66,981,399 chance of missing a record. Certain numbers do not resolve into a palindrome within the limit tested,and we believe such numbers will never solve, no matter how many iterations they are taken to.Such numbers are called Lychrel numbers.The percentage of Lychrels that occur increases with each new digit length tested:
![]() (Please note the above data is obtained from the sub-set of numbers my program tests.My program does not test every number, due to the optimizations explained earlier.So, while this graph is not 100% accurate, it is certainly very close. Most likely, itis accurate to well within the precision shown.)
|
Solved all 1 digit numbers | |||
Number | Iterations | Digits | Resultant Palindrome |
1 5 | 1 2 | 1 2 | 2 11 |
Solved all 2 digit numbers | |||
Number | Iterations | Digits | Resultant Palindrome |
59 69 79 89 | 3 4 6 24 | 4 4 5 13 | 1111 4884 44044 8813200023188 |
Solved all 3 digit numbers | |||
Number | Iterations | Digits | Resultant Palindrome |
166 188 193 829 167 849 177 999 739 989 869 187 | 5 7 8 10 11 14 15 16 17 19 22 23 | 5 6 6 8 8 10 10 10 10 11 13 13 | 45254 233332 233332 88555588 88555588 8836886388 8836886388 8939779398 5233333325 89540004598 8813200023188 8813200023188 |
Solved all 4 digit numbers | |||
Number | Iterations | Digits | Resultant Palindrome |
1,397 2,069 1,797 1,798 6,999 1,297 | 9 12 13 18 20 21 | 8 8 10 11 14 13 | 88555588 52788725 8836886388 89540004598 16668488486661 8813200023188 |
Solved all 5 digit numbers | |||
Number | Iterations | Digits | Resultant Palindrome |
10,797 10,853 10,921 10,971 13,297 10,548 13,293 17,793 20,889 80,359 13,697 10,794 15,891 70,759 70,269 10,677 10,833 10,911 | 25 26 27 28 29 30 31 32 33 37 38 39 40 47 52 53 54 55 | 16 16 16 16 18 17 17 17 17 22 22 22 22 26 28 28 28 28 | 1676404554046761 4455597447955544 4455597447955544 8802202552022088 893974888888479398 17858768886785871 17858768886785871 44035358885353044 44035358885353044 6839849878998789489386 6839849878998789489386 6832123695335963212386 6832123695335963212386 14525756544499444565752541 4668731596684224866951378664 4668731596684224866951378664 4668731596684224866951378664 4668731596684224866951378664 |
Solved all 6 digit numbers | |||
Number | Iterations | Digits | Resultant Palindrome |
700,269 106,977 108,933 600,259 131,996 600,279 141,996 600,579 147,996 178,992 190,890 600,589 150,296 | 34 35 36 45 46 50 51 57 58 59 60 63 64 | 22 22 22 26 26 28 28 31 31 31 31 33 33 | 6832123695335963212386 6832123695335963212386 6832123695335963212386 14525756544499444565752541 14525756544499444565752541 4668731596684224866951378664 4668731596684224866951378664 8834453324841674761484233544388 8834453324841674761484233544388 8834453324841674761484233544388 8834453324841674761484233544388 682049569465550121055564965940286 682049569465550121055564965940286 |
Solved all 7 digit numbers | |||
Number | Iterations | Digits | Resultant Palindrome |
1,009,227 1,007,619 1,009,246 1,008,628 1,007,377 1,001,699 1,009,150 1,058,921 1,050,995 1,003,569 1,036,974 1,490,991 3,009,179 1,008,595 1,064,912 1,998,999 7,008,429 1,000,689 1,005,744 1,007,601 7,008,899 9,008,299 | 41 42 43 44 48 49 56 61 62 65 66 67 68 69 70 75 77 78 79 80 82 96 | 23 22 23 23 28 27 28 32 33 32 32 32 35 35 35 32 38 39 39 38 38 48 | 68344497279697279444386 1556534287227824356551 45144454432023445444154 48852787646664678725884 8836746997299229927996476388 168977944479424974449779861 6842165664428668244665612486 18966336852467966976425863366981 682049569465550121055564965940286 14758724578598888889587542785741 14758724578598888889587542785741 14758724578598888889587542785741 46563056797844547874544879765036564 46563056797844547874544879765036564 46563056797844547874544879765036564 15521561387579888897578316512551 14674443960143265333356234106934447641 796589884324966945646549669423488985697 796589884324966945646549669423488985697 14674443960143265333356234106934447641 68586378655656964999946965655687368586 555458774083726674580862268085476627380477854555 |
Solved all 8 digit numbers | |||
Number | Iterations | Digits | Resultant Palindrome |
10,905,963 10,069,785 10,089,342 11,979,990 10,029,372 10,029,826 16,207,990 90,000,589 10,309,988 | 71 72 73 74 76 81 83 94 95 | 38 32 32 32 39 38 38 48 48 | 35695487976778433588533487767978459653 15521561387579888897578316512551 15521561387579888897578316512551 15521561387579888897578316512551 796589884324966945646549669423488985697 68586378655656964999946965655687368586 68586378655656964999946965655687368586 555458774083726674580862268085476627380477854555 555458774083726674580862268085476627380477854555 |
Solved all 9 digit numbers | |||
Number | Iterations | Digits | Resultant Palindrome |
100,389,898 100,055,896 110,909,992 160,009,490 800,067,199 151,033,997 100,093,573 103,249,931 107,025,910 180,005,498 100,239,862 140,669,390 | 84 85 86 87 88 89 90 91 92 93 97 98 | 45 41 40 40 46 46 46 46 46 48 52 52 | 584227988787668589199242991985866787889722485 88682199585544879735653797844558599128688 3525698275220268897227988620225728965253 3525698275220268897227988620225728965253 5852497685678899643696996963469988765867942585 5852497685678899643696996963469988765867942585 5852497685678899643696996963469988765867942585 5852497685678899643696996963469988765867942585 5852497685678899643696996963469988765867942585 555458774083726674580862268085476627380477854555 1345428953367763125675365555635765213677633598245431 1345428953367763125675365555635765213677633598245431 |
Solved all 10 digit numbers | |||
Number | Iterations | Digits | Resultant Palindrome |
1,090,001,921 7,007,009,909 1,009,049,407 9,000,046,899 1,050,027,948 1,304,199,693 5,020,089,949 1,005,499,526 | 99 100 101 103 104 105 108 109 | 46 49 49 49 49 49 53 53 | 6634544448788301675886446885761038878444454366 1543434266587555114779722279774115557856624343451 1543434266587555114779722279774115557856624343451 5831124885795990016569666669656100995975884211385 5831124885795990016569666669656100995975884211385 5831124885795990016569666669656100995975884211385 66330069478378985774345546664554347758987387496003366 66330069478378985774345546664554347758987387496003366 |
Solved all 11 digit numbers | |||
Number | Iterations | Digits | Resultant Palindrome |
10,000,505,448 10,000,922,347 10,000,696,511 10,701,592,943 10,018,999,583 10,000,442,119 10,000,761,554 10,084,899,970 10,006,198,250 18,060,009,890 11,400,245,996 16,002,897,892 18,317,699,990 37,000,488,999 10,050,289,485 90,000,626,389 10,000,853,648 13,003,696,093 10,050,859,271 10,287,799,930 10,000,973,037 10,600,713,933 10,942,399,911 60,000,180,709 11,009,599,796 16,000,097,392 10,031,199,494 10,306,095,991 10,087,799,570 | 102 106 107 110 111 112 113 114 115 116 117 118 119 122 123 130 131 132 133 134 135 136 137 144 145 146 147 148 149 | 49 50 56 53 56 56 56 56 56 56 56 56 56 58 58 65 65 65 65 65 71 71 71 66 66 66 66 66 66 | 5831124885795990016569666669656100995975884211385 15739929700341113302426977962420331114300792993751 13323895762789854121576789855898767512145898726759832331 23103742208899345951210026862001215954399880224730132 13656852665688105699133698688689633199650188656625865631 13656852665688105699133698688689633199650188656625865631 13656852665688105699133698688689633199650188656625865631 13656852665688105699133698688689633199650188656625865631 13656852665688105699133698688689633199650188656625865631 15997773553851169652456786055068765425696115835537779951 11144565886884377368565136533563156586377348868856544111 11144565886884377368565136533563156586377348868856544111 11144565886884377368565136533563156586377348868856544111 4618999883854436730489915000000005199840376344583889998164 4618999883854436730489915000000005199840376344583889998164 12346788678755866852059426528989698982562495025866855787688764321 12346788678755866852059426528989698982562495025866855787688764321 12346788678755866852059426528989698982562495025866855787688764321 12346788678755866852059426528989698982562495025866855787688764321 12346788678755866852059426528989698982562495025866855787688764321 12366212267356333541465465587987721212778978556456414533365376221266321 12366212267356333541465465587987721212778978556456414533365376221266321 12366212267356333541465465587987721212778978556456414533365376221266321 895549975467412444422685224544649946445422586224444214764579945598 895549975467412444422685224544649946445422586224444214764579945598 895549975467412444422685224544649946445422586224444214764579945598 895549975467412444422685224544649946445422586224444214764579945598 895549975467412444422685224544649946445422586224444214764579945598 895549975467412444422685224544649946445422586224444214764579945598 |
Solved all 12 digit numbers | |||
Number | Iterations | Digits | Resultant Palindrome |
100,900,509,906 100,000,055,859 104,000,146,950 180,005,998,298 300,000,185,539 100,001,987,765 | 120 121 124 129 142 143 | 58 58 58 65 66 66 | 4618999883854436730489915000000005199840376344583889998164 4618999883854436730489915000000005199840376344583889998164 4618999883854436730489915000000005199840376344583889998164 12346788678755866852059426528989698982562495025866855787688764321 895549975467412444422685224544649946445422586224444214764579945598 895549975467412444422685224544649946445422586224444214764579945598 |
Solved all 13 digit numbers | |||
Number | Iterations | Digits | Resultant Palindrome |
1,000,007,614,641 1,000,043,902,320 1,000,006,653,746 1,000,005,469,548 4,000,096,953,659 1,332,003,929,995 1,000,201,995,662 6,000,008,476,379 1,200,004,031,698 1,631,002,019,993 1,000,006,412,206 1,090,604,591,930 1,600,005,969,190 | 125 126 127 128 139 140 141 183 184 185 186 187 188 | 65 65 65 68 66 66 66 87 87 87 87 87 87 | 68236478976724413455368469647845654874696486355431442767987463286 68236478976724413455368469647845654874696486355431442767987463286 12346788678755866852059426528989698982562495025866855787688764321 46476268994355205755566889613764755746731698866555750255349986267464 895549975467412444422685224544649946445422586224444214764579945598 895549975467412444422685224544649946445422586224444214764579945598 895549975467412444422685224544649946445422586224444214764579945598 159788389444247969944047982661126897487188000881784798621166289740449969742444983887951 159788389444247969944047982661126897487188000881784798621166289740449969742444983887951 159788389444247969944047982661126897487188000881784798621166289740449969742444983887951 159788389444247969944047982661126897487188000881784798621166289740449969742444983887951 159788389444247969944047982661126897487188000881784798621166289740449969742444983887951 159788389444247969944047982661126897487188000881784798621166289740449969742444983887951 |
Solved all 14 digit numbers | |||
Number | Iterations | Digits | Resultant Palindrome |
10,090,899,969,901 40,000,004,480,279 14,104,229,999,995 | 138 181 182 | 70 87 87 | 2319937995996732122112578857767863993687677588752112212376995997399132 159788389444247969944047982661126897487188000881784798621166289740449969742444983887951 159788389444247969944047982661126897487188000881784798621166289740449969742444983887951 |
Solved all 15 digit numbers | |||
Number | Iterations | Digits | Resultant Palindrome |
100,000,109,584,608 100,000,098,743,648 100,004,789,906,151 100,079,239,995,161 100,389,619,999,030 200,000,729,975,309 107,045,067,996,994 105,420,999,199,982 101,000,269,830,970 104,000,047,066,970 700,000,001,839,569 100,000,050,469,737 101,000,789,812,993 100,907,098,999,571 100,017,449,991,820 890,000,023,937,399 100,009,989,989,199 101,507,024,989,944 107,405,139,999,943 100,057,569,996,821 103,500,369,729,970 900,000,076,152,049 100,000,439,071,028 120,000,046,510,993 103,000,015,331,997 100,617,081,999,573 100,009,029,910,821 107,000,020,928,910 100,000,090,745,299 102,000,149,322,944 130,000,074,931,591 100,120,849,299,260 | 150 151 152 153 154 155 156 157 158 159 163 164 165 166 167 169 170 171 172 173 174 178 179 180 189 190 191 192 198 199 200 201 | 80 73 80 73 73 77 77 83 77 83 78 78 77 77 77 80 76 76 82 82 80 87 87 87 87 87 87 87 92 92 92 92 | 14751782101782013776625853112452243335411453334225421135852667731028710128715741 3874338821379754365139707922389885874785889832297079315634579731288334783 14751782101782013776625853112452243335411453334225421135852667731028710128715741 3874338821379754365139707922389885874785889832297079315634579731288334783 3874338821379754365139707922389885874785889832297079315634579731288334783 58432004534377668812885984239766675854845857666793248958821886677343540023485 58432004534377668812885984239766675854845857666793248958821886677343540023485 66364653972239888685894387234687476484136863148467478643278349858688893227935646366 58432004534377668812885984239766675854845857666793248958821886677343540023485 66364653972239888685894387234687476484136863148467478643278349858688893227935646366 177454986735997675255356985559732595246642595237955589653552576799537689454771 177454986735997675255356985559732595246642595237955589653552576799537689454771 15951239866387982563456955855439974585458547993455855965436528978366893215951 15951239866387982563456955855439974585458547993455855965436528978366893215951 15951239866387982563456955855439974585458547993455855965436528978366893215951 36764456433123268897359635569438786398655689368783496553695379886232133465446763 1685279897987756678784477446325846776116776485236447744878766577897989725861 1685279897987756678784477446325846776116776485236447744878766577897989725861 4973663467878710242597852762388983882088668802883898832672587952420178787643663794 4973663467878710242597852762388983882088668802883898832672587952420178787643663794 36764456433123268897359635569438786398655689368783496553695379886232133465446763 159788389444247969944047982661126897487188000881784798621166289740449969742444983887951 159788389444247969944047982661126897487188000881784798621166289740449969742444983887951 159788389444247969944047982661126897487188000881784798621166289740449969742444983887951 129816518702696188228910113874486338915527747725519833684478311019822881696207815618921 129816518702696188228910113874486338915527747725519833684478311019822881696207815618921 129816518702696188228910113874486338915527747725519833684478311019822881696207815618921 129816518702696188228910113874486338915527747725519833684478311019822881696207815618921 16616723795884852455598564101455698426624444977944442662489655410146589555425848859732761661 16616723795884852455598564101455698426624444977944442662489655410146589555425848859732761661 16616723795884852455598564101455698426624444977944442662489655410146589555425848859732761661 16616723795884852455598564101455698426624444977944442662489655410146589555425848859732761661 |
Solved all 16 digit numbers | |||
Number | Iterations | Digits | Resultant Palindrome |
6,000,000,039,361,479 1,421,000,069,679,996 1,000,650,998,992,311 1,000,002,899,436,401 1,000,100,396,492,200 1,400,000,027,672,498 7,090,000,039,309,919 1,000,050,048,994,957 1,003,000,024,749,923 1,000,803,019,495,711 1,030,020,097,997,900 | 161 162 168 175 176 177 193 194 195 196 197 | 78 78 76 78 78 87 92 92 92 92 92 | 177454986735997675255356985559732595246642595237955589653552576799537689454771 177454986735997675255356985559732595246642595237955589653552576799537689454771 1685279897987756678784477446325846776116776485236447744878766577897989725861 169635646445469964587742217600000453348843354000006712247785469964544646536961 169635646445469964587742217600000453348843354000006712247785469964544646536961 159788389444247969944047982661126897487188000881784798621166289740449969742444983887951 16616723795884852455598564101455698426624444977944442662489655410146589555425848859732761661 16616723795884852455598564101455698426624444977944442662489655410146589555425848859732761661 16616723795884852455598564101455698426624444977944442662489655410146589555425848859732761661 16616723795884852455598564101455698426624444977944442662489655410146589555425848859732761661 16616723795884852455598564101455698426624444977944442662489655410146589555425848859732761661 |
Solved all 17 digit numbers | |||
Number | Iterations | Digits | Resultant Palindrome |
10,000,000,730,931,027 20,005,000,862,599,819 11,450,360,479,969,994 10,009,000,275,899,569 10,059,430,139,999,234 12,179,702,595,999,991 79,000,000,445,783,599 10,000,000,767,846,797 10,000,000,673,402,336 10,000,000,525,586,206 10,005,000,760,994,249 10,030,503,899,969,524 12,000,009,694,736,291 10,442,000,392,399,960 | 160 206 207 208 209 210 229 230 231 232 233 234 235 236 | 82 90 90 90 90 90 112 112 111 111 111 111 111 111 | 1454578665279976634446532368777548944388998834498457778632356444366799725668754541 795884875720569937749728766349898266325776598895677523662898943667827947739965027578488597 795884875720569937749728766349898266325776598895677523662898943667827947739965027578488597 795884875720569937749728766349898266325776598895677523662898943667827947739965027578488597 795884875720569937749728766349898266325776598895677523662898943667827947739965027578488597 795884875720569937749728766349898266325776598895677523662898943667827947739965027578488597 4577267267265113973218923972796414755643668659429704525555254079249568663465574146972793298123793115627627627754 4577267267265113973218923972796414755643668659429704525555254079249568663465574146972793298123793115627627627754 579922447678688885254995975774499665520124525649777656969656777946525421025566994477579599452588886876744229975 579922447678688885254995975774499665520124525649777656969656777946525421025566994477579599452588886876744229975 579922447678688885254995975774499665520124525649777656969656777946525421025566994477579599452588886876744229975 579922447678688885254995975774499665520124525649777656969656777946525421025566994477579599452588886876744229975 579922447678688885254995975774499665520124525649777656969656777946525421025566994477579599452588886876744229975 579922447678688885254995975774499665520124525649777656969656777946525421025566994477579599452588886876744229975 |
Solved all 18 digit numbers | |||
Number | Iterations | Digits | Resultant Palindrome |
195,030,047,999,791,993 100,000,078,999,111,766 100,710,000,333,399,973 100,000,002,973,751,552 100,000,277,999,334,202 110,300,361,999,869,090 300,000,000,128,545,799 104,300,000,514,769,945 100,700,000,509,609,622 120,906,490,499,909,290 900,040,000,881,499,569 100,072,100,489,999,238 121,506,542,999,979,993 106,096,507,979,997,951 100,980,800,839,699,830 600,000,000,606,339,049 170,500,000,303,619,996 | 202 203 204 205 211 212 213 214 215 216 218 219 220 221 222 227 228 | 105 105 90 90 107 107 101 101 101 101 103 103 103 103 103 112 112 | 889956674896587435857678447634488652657823489664135444531466984328756256884436744876758534785698476659988 889956674896587435857678447634488652657823489664135444531466984328756256884436744876758534785698476659988 795884875720569937749728766349898266325776598895677523662898943667827947739965027578488597 795884875720569937749728766349898266325776598895677523662898943667827947739965027578488597 16625459966833465379947700047533357850265135989944697679644998953156205875333574000774997356433866995452661 16625459966833465379947700047533357850265135989944697679644998953156205875333574000774997356433866995452661 14884695685311269599498656858759854685128966643652225634666982158645895785865689499596211358659648841 14884695685311269599498656858759854685128966643652225634666982158645895785865689499596211358659648841 14884695685311269599498656858759854685128966643652225634666982158645895785865689499596211358659648841 14884695685311269599498656858759854685128966643652225634666982158645895785865689499596211358659648841 1596569934458730179488896975455653647842016863898846488983686102487463565545796988849710378544399656951 1596569934458730179488896975455653647842016863898846488983686102487463565545796988849710378544399656951 1596569934458730179488896975455653647842016863898846488983686102487463565545796988849710378544399656951 1596569934458730179488896975455653647842016863898846488983686102487463565545796988849710378544399656951 1596569934458730179488896975455653647842016863898846488983686102487463565545796988849710378544399656951 4577267267265113973218923972796414755643668659429704525555254079249568663465574146972793298123793115627627627754 4577267267265113973218923972796414755643668659429704525555254079249568663465574146972793298123793115627627627754 |
As of Saturday, January 23, 2010, solved 55.011% of all 19 digit numbers | |||
Number | Iterations | Digits | Resultant Palindrome |
1,000,000,038,990,407,538 1,000,000,005,577,676,468 1,060,000,000,523,124,995 1,000,000,079,994,144,385 1,003,062,289,999,939,142 1,186,060,307,891,929,990 | 217 225 226 259 260 261 | 107 111 112 119 119 119 | 49627604840136499793982885796699976479895651785665644844656658715659897467999669758828939799463104840672694 579922447678688885254995975774499665520124525649777656969656777946525421025566994477579599452588886876744229975 4577267267265113973218923972796414755643668659429704525555254079249568663465574146972793298123793115627627627754 44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544 44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544 44562665878976437622437848976653870388884783662598425855963436955852489526638748888307835667984873422673467987856626544 |
Iterations up to 261 for which no number was found | |||
223, 224, 237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252, 253, 254, 255, 256, 257, 258. |
The intriguing part about these records is thatit takes an unreal amount of calculations to discover them,but it takes only a minute amount of calculations toprove that they terminate with a palindrome in the claimednumber of iterations.With a program, it would take less thanone second to prove that the above numbers do indeed solve out.I do not need a Guinness World Records Officialto be present during these calculations.You can take these numbers yourself,write up a quick program, and prove the results yourself.In fact, I have done so. Click on any of the numbers above, and youwill be shown a calculation page - computed in real-time (you can test this by entering your own unique number at the end of the URL) -proving that this number resolves into apalindrome in the displayed number of steps,showing you the calculations required to get there.
Please contact me if you would like more information,or if you know that I have stated incorrect informationon this page. To the best of my knowledge, it is correctat this time.
FRIDAY, OCTOBER 13, 2006 UPDATE: Vaughn Suite has completed the processing all 19 digit numbersusing a distributed network of 7 machines.He has found the following records: The 19 digit number 1,000,000,038,990,407,538 solves after 217 iterations, found on November 27, 2005. No longer delays were found. Note: You may notice that I have previously stated,in my November 30, 2005 update,that Vaughn had already foundthe 259 iteration record,1,000,000,079,994,144,385,on July 26, 2005.When Vaughn was processing the 18 digit set on his work desktop last year,he started processing the 19 digit set on his laptop.This processing discovered this 259 iteration record.When he distributed the work into 15 subsets,he had to restart the 19 digit set from scratch,to be able to join it together properly.This processing rediscovered this result on November 28, 2005. RETIREMENT: I retired for several reasons.One is that Vaughn is using his own implementationof the same exponentially faster algorithm that I pioneered,which means his code is as fast as mine,all else being equal. Also, Vaughn improved the speed of the reverse and add procedureusing his own assembly code (optimized for the Pentium III, Pentium 4 and Athlon XP processors).And, he did so specifically for such short iteration spans,unlike the 196 Palindrome Quest,which cannot benefit from cache as greatly,since it processes numbers much larger than available CPU cache.My reverse and add code is from Benjamin Despres,which was optimized for the 196 Palindrome Quest.As you can see fromWade's Software Comparison Page,Vaughn's code is the fastest for smaller numbers.However, even for the 196 Palindrome Quest,Vaughn's assembly code istwice as fast as Ben's.
The 19 digit number 9,000,000,000,255,353,839 solves after 224 iterations, found on February 26, 2006.
The 19 digit number 1,000,000,005,577,676,468 solves after 225 iterations, found on November 24, 2005.
The 19 digit number 1,060,000,000,523,124,995 solves after 226 iterations, found on March 9, 2006.
The 19 digit number 3,000,000,022,999,288,679 solves after 258 iterations, found on April 20, 2006.
The 19 digit number 1,000,000,079,994,144,385 solves after 259 iterations, found on November 28, 2005.
The 19 digit number 1,003,062,289,999,939,142 solves after 260 iterations, found on March 19, 2006.
The 19 digit number 1,186,060,307,891,929,990 solves after 261 iterations, found on January 2, 2006,which is the same world record that my program already solved on November 30, 2005.
Incidentally, at this time, I have only processed 9.782% of the 19 digit set.Why so little?My program has been running only part time, about one third of the time, on one machine.This lack of computer time is due to my retirement of this quest almost a year ago.I will eventually analyze my logs to find out when I stopped processing 24/7,and see how much CPU time I used since then until now.I should note my source code is available for anyserious requestto make use of it.
To Ben's credit, Ben created his code a long time ago, in mid 2002,before he was able to make use of some of the newer CPU instructions.In 2002, Ben's had the fastest known application,responsible for taking the 196 Palindrome Quest from29 million digits to 45 million digits.
Also, the largest factor in Vaughn's effort was that his application was distributedover seven machines. I only had one. I had access to seven CPUs,but they hadmore important thingsto spend their time on.Thus, I simply could not keep up with his much faster applicationon his incredible amount of CPU power he has available.It was a great effort, and I look forward to his analysis of the 20 digit set.
SUNDAY, FEBRUARY 3, 2008 UPDATE: Fifteen months after completing processing the 19 digit numbers,Vaughn Suite has completed processing all 20 digit numbers bydistributing the work into 15 subsets and using the Pentium 4 HTand 2 Athlon XP machines from the 19 digit processing and alsothree more powerful computers: an Athlon 64, an Athlon 64 X2,and a Core 2 Quad machine. The subsets were executed simultaneouslyon different machines, or in multiple threads on the machines withhyperthreading or multi-core capabilities(Pentium 4 HT, Athlon X2, Core-2 Quad). Of the 5,808,378,560,022 numbers checked, there were5,459,760,062,742 lychrels (94.00%), while 348,618,497,280 numbersresolved into palindromes. Cumulative processing time on all the machines was 131,146,531 seconds = 1517.9 days (4 years and 2 months), but processing startedJanuary 6, 2007 and finished January 22, 2008.There are 58,083,785,600,220 (10 times as many) 21 digit numbers tobe checked, so that processing of that entire set of numbers willtake much longer with the current machines. Vaughn reports that the Core-2 machine was most responsible forthe quick completion since it runs optimized reverse and addsoftware 1.7 times as fast as the next fastest processor (Athlon X2),twice as fast as the Athlon 64, 2.5 times as fast as the Athlon XPsand almost 6 times as fast as each Pentium 4 thread in Hyperthreading mode. The new records are for 223, 253, 254, 255, 256 & 257 iterations: No longer iteration delays were found, and no iterations between237 iterations and 252 were found. The following iteration recordshave not yet been discovered:237, 238, 239, 240, 241, 242, 243, 244, 245, 246, 247, 248, 249, 250, 251, 252.
The 20 digit number 10,000,000,039,513,841,287 solves after 223 iterations, found on September 20, 2007.
The 20 digit number 70,000,000,000,507,277,299 solves after 253 iterations, found on September 13, 2007.
The 20 digit number 10,200,000,000,708,183,947 solves after 254 iterations, found on March 28, 2007.
The 20 digit number 10,022,000,904,998,799,523 solves after 255 iterations, found on December 3, 2007.
The 20 digit number 10,000,000,039,395,795,416 solves after 256 iterations, found on September 20, 2007.
The 20 digit number 10,200,000,000,065,287,900 solves after 257 iterations, found on March 28, 2007.
AUGUST 12, 2016 UPDATE: From Michael Piepgras: Michael Piepgras found21 digit number500000060001199990549solves after251 iterations. Timestamp = 12 Aug 2016, 2:07pm (European Time)
"Another 16 threads on my PC are running on the 196-lychrel problem, also with my own code.
It took me 172 days to get to 306.850.000 digits with 741.368.180 iterations on the 196 number."
AUGUST 12, 2017 UPDATE: Exactly one year later! Michael Piepgras found21 digit number100000081000999940726solves after252 iterations. Timestamp = 12 Aug 2017, 10.15am
June 14, 2018 UPDATE: Marc Lapierre found:
21 digit number150000000000553509679solves after253 iterations.
21 digit number10000000029399959365solves after224 iterations.
21 digit number10000000039395795416solves after256 iterations.
Quoted from Rob van Nobelen:
"I have completed all 21 digit numbers and the longest sequence found was 256(which just maps to the 261 sequence of the 19 digit numbers).I am now onto the 23 digit numbers and have finally found a new record of 288 steps!...I skipped 22 (digit numbers) because generally the even length number don't seem to have the same chance of leading to a longer sequence.I am only about 2% through the 23 digit numbers so quite lucky to find a new record early on. I doubt there will be a higher one in the 23 digit range."
"The best result for 21 digits is 100800000429004749950 (256 steps) which just maps onto the same sequence as the 261 step maximum for 19 digits."
(Please note: this is the first "world record" that DOES NOT include the enumeration of all smaller numbers.
Specifically, the 22 digit set was skipped.
Even-numbered digit sets are unlikely to produce a result.
thus it is easier and requires less computation to find records in this manner.)"The 23 digit number is: 12000700000025339936491 which solves in 288 steps.
Found 26 April 2019 (6:57 am NZ time).
(Please note: these results are just random -- again, like the record above, not the KNOWN smallest.I have also removed the numbers from this note that were already discovered previously.We will need to clearly distinguish the difference between these records.It is very different to produce any record at all vs. the known lowest record, which is the entirety of my work.)
"Some of the missing entries for number of steps (there are thousands of these as you know so have just picked some random ones):
237: not found
238: 40000000000021391578709 (23 digits)
239: 15844005200010990299995 (23 digits)
240: 10080000010009595119352 (23 digits)
241: 13200130000005299908990 (23 digits)
242: not found
243: not found
244: not found
245: 90000000000010051667559 (23 digits)
246: 10004013000009999293778 (23 digits)
247: 12002200550029932991893 (23 digits)
248: 10500020000017719681951 (23 digits)
249: 10800494000001399940920 (23 digits)
250: 10080000400000911869790 (23 digits)
257: not found
OCTOBER 26, 2020 UPDATE: From Michael Piepgras: By the way on the 196-Problem I am actually at iteration 1.559.028.251 (645325000 digits) without finding a palindrome.
"As Mr. Rob van Nobelen finished them (21-digits) first and is now iterating the 23-digit numbers,I started to iterate the 25-digit numbers (which would take about 44 years running on 64 threads).On a second machine I am running the 22-digit numbers, which have been left out.
Michael Piepgras found25 digit number1070000000000387391437944solves after242 iterations.
NOVEMBER 5, 2020 UPDATE: Michael Piepgras found25 digit number1060000000000567176574962solves after237 iterations.
NOVEMBER 7, 2020 UPDATE: Michael Piepgras found 25 digit number1090000000000618133128985solves after244 iterations.
DECEMBER 4, 2020 UPDATE: Michael Piepgras found 25 digit number1060000000001215241774949solves after243 iterations.
Anton Stefanov has discovered the new World Record!
The23 digit number13968441660506503386020
solves after289 iterations
to form a 142 digit palindrome!
Timestamp = 16:47 (Moscow), 4 Jan 2021
JANUARY 11, 2021 UPDATE: Anton Stefanov found a second23 digit number16909736969870700090800that solves in the same 289 iterations
using a unique methodto produce x+1-step delayed palindromes from x-step delayed one.