Aliquot Sequences from the Trenches

First, there were perfect numbers. Then came amicable pairs. Those were followed by sociable numbers. This progression led some to question the fate of sequences in which each member was the sum of the aliquot parts of its predecessor, where the aliquot parts of n consist of the divisors of n excluding n itself. This is expressed mathematically by use of the sigma function: (n) equals the sum of all the divisors of the integer n. For each n_i of an aliquot sequence, its successor n_i+1 = (n_i) - n_i. The Catalan-Dickson Conjecture theorized that each of these sequences would either collapse to 1 or enter a cycle consisting of one or more numbers. However, the advent of computers has revealed empirically that this conjecture is almost certainly false. In particular, an aliquot sequence beginning with a randomly chosen even number would, in all probability, be expected to increase without bound. This is the assessment of Richard Guy and John Selfridge writing in 1974 and published the next year in the journal Mathematics of Computation. Nevertheless, these sequences continue to be of interest, and the conjecture is considered the best known iteration problem in number theory. Here are the principle drivers that serve to propel the sequences upward:

2 * 3
2² * 7
2³ * 3 * 5
2⁴ * 31
2⁵ * 3 * 7
2⁶ * 127

Escape from any of these occurs only under special circumstances (see analysis). One might intuitively think that once a sequence does lose its driver, it would then fall of its own weight, plunging all the way to 1 or ending up in a cycle. But this is rarely the case. After escape from a driver, the next step needed for possible termination would be aquisition of the downdriver (2 *). However, it is far more likely that an upward-propelling guide, driver or the digit '3' would be obtained. As a consequence, these sequences are subject to a natural upward trend.

MAJOR PROJECTS

The biggest project by far was the ambitious effort by Wolfgang Creyaufmüller to compute all sequences that begin with numbers less than 1,000,000 to at least 80 digits. This multi-year endeavor produced a steady stream of interesting results such as terminating sequences, confluences, and exceptionally long sequences. Its completion was announced on April 1, 2003, and the results are now available to the research community on his recently constructed download page.

Paul Zimmermann, the principle investigator of the Lehmer Five, computed each sequence in [1, 10^5] and extended those in [50,000, 10^5] to 80 digits. He made significant contributions to the GNU multiple precision arithmetic library, and his ECMNET Project has produced a series of ever more efficient versions of the elliptical curve factoring method.

Wieb Bosma did pioneering work in [10^4, 50,000], computing each member to at least 90 digits. His results for terminating sequences held up for a remarkably long period of time until Wolfgang Creyaufmüller broke the impasse by terminating 16302 on December 31, 2003. He is now working on extending sequences in [250000, 400000] to 100 digits.

Juan L. Varona and Manuel Benito worked intensively in [10^3, 10^4], computing each to 100 digits and beyond. On June 10, 2001, they terminated 3630, a result which reigned supreme for nearly four years in terms of the maximum size reached for a terminating sequence: 100 digits at index 1263 (5.64 x 10^99). At this site can also be found 3630finishes.pdf, a comprehensive introduction to the subject by multiple authors. In addition, they provide Advances in Aliquot Sequences which was published in the journal Mathematics of Computation.

Christophe Clavier, along with a high-powered team of associates took over work in the interval 1464 to 9852. The result was a remarkable series of driver escapes and downdriver aquisitions. However, they have been very unlucky in failing to obtain any new terminating sequences from their 32 downdriver runs that began in triple digits.

Wolfgang Creyaufmüller and I continued the efforts of Paul Zimmermann in [50,000, 100,000]. My computations were confined to those that were not being driven by one of the main six drivers at the 80-digit mark. The result was one terminating sequence (62832) and one new confluence (72288). Wolfgang followed by working on the remaining ones, and was successful in finding three new terminating sequences, in spite of each having been under the control of a driver at the 80-digit mark.

Wolfgang Creyaufmüller subsequently went to work extending Wieb Bosma's sequences in [10,000, 50,000] to at least 100 digits. Though termination is rare after the 90-digit mark has been reached, he succeeded in finding two new terminating sequences: the aforementioned 16302 and then 49218 near the end of the project.

Wolfgang Creyaufmüller completed a project to extend all sequences in [50,000, 100,000] to at least 100 digits. It produced many interesting results, such as driver escapes and long downdriver runs. However, for the first time, no additional terminating sequences were found.

Wolfgang Creyaufmüller extended the sequences in [100,000, 200,000] to 100 digits. This produced many interesting results, including eleven terminations, one side-sequence and several new confluences.

Recent News

Note: results from the frenetic activity in the Mersenne Forum have been provided to me by Frank Schickel

Don Leclair set multiple records by capturing the downdriver at 158 digits while simultaneously escaping from the 2^2 * 7 driver in 3906. It's the highest downdriver acquisition, highest driver escape and highest escape from a driver directly to the downdriver.

Dmitry Domanov became the new king of high terminating sequences by finishing off 921232 on April 12th after it had reached a maximum of 127 digits. Wolfgang Creyaufmüller had originally computed this to 103 digits at index 5326 where it was driven by 2^3 * 3^2 * 5. After advancing it to the 127-digit mark, Dmitry captured the downdriver at 126 digits, which lowered the height to 113. That was followed by the fifth longest downdriver run, producing a reduction in size from 113 to 33. The final index of 6358 makes it the second longest terminating sequence, behind 414288 which ended at index 6584.

Members of the Mersenne Forum have extended 4788 to a record height of 172 digits, where it has achieved stability, thus also a new record high in that category.

98616 terminated after reaching a height of 118 digits on November 18th, tying if for what was then second place with 163716 in the overall list. See below for details.

Christophe Clavier set what was then a new record for the highest escape from 2^2 * 7 directly to the downdrver at 124 digits in 4380. This surpassed the previous high of 116 set by Mersenne Forum members in 10212.

Paul Zimmermann set a new record for the highest acqusition of the downdriver at 145 digits in 660 in July of 2006.

Paul Zimmermann set a new record of 146 for the highest escape from the 2^5 * 3 * 7 driver in 552 during the Summer of 2005, greatly exceeding the previously known record of 107 in 271932.

Frank Schickel performed the hat trick of escapes from the rare 2^9 * 3 * 11 * 31 driver by negotiating escapes in all three sequences that had been under control of that driver. First, he set a new record with an escape in 604560 at 126 digits, greatly exceeding the previous high of 55 set by Wolfgang Creyaufmüller in 867690. That was followed by an escape in 479632 at 111 digits, and on October 16th he broke his own record with an escape in 363270 at 133 digits.

Paul Zimmermann set a new record of 150 for the highest escape from the 2^5 * 3^n * 7 (n>1) guide in 1134 at index 2308, surpassing the previous high of 135 set by Ignacio Santos in 199152 at index 4572.

Jonathan DeMarrais terminated 507924 after it had reached a maximum of 115 digits, equaling the size of his previous result in 151752 discussed below. Beginning where Wolfgang Creyaufmüller left off at 83 digits with the sequence driven by 2 * 3^2, escape came at 86 digits but the 2^3 * 3 driver then increased the size to 104. Lasting stability was finally achieved at the height of 114, followed by an exceptionally long downdriver run from 115 to 54 digits. The finish came with the prime 43 at index 3147.

Serge Batalov broke is own record for the longest single sequence by extending 552150 to 8190 lines. Picking up where Wolfgang Creyaufmüller left off at index 3964, he advanced the sequence to a length once the exclusive province of paired sequences.

Frank Schickel has reproduced the seminal article mentioned above in .pdf format. What Drives an Aliquot Sequence? by Richard Guy and J. L. Selfridge develops the driver concept and argues in favor of an infinitude of unbounded sequences. Consult the Mersenne Forum for information on obtaining a copy (or email me).

Serge Batalov achieved his third terminating sequence in 216810. Wolfgang Creyaufmüller had left off just when it had escaped from a long run of the 2 * 3 driver, where it emerged guided by 2^2 * 3 at 100 digits. Continuing from there, Serge captured the downdriver at 102 digits, and there was little resistance the subsequent plunge to completion.

Jonathan DeMarrais computed 151752 to the third highest terminating sequence by reaching a maximum of 115 digits. Beginning where Wolfgang Creyaufmüller left off at 100 digits with the sequence stable at index 1117, he quickly ran into trouble when the 2^3 * 3 * 5 driver was acquired. The situation improved when the '3' became raised above the exponent of 1, but that also served to accelerate the rise of the sequence up to 115 digits before escape finally came. The downdriver was obtained at the level, and then began a rare series of events hypothesized below in which a rapid collapse ensued with only small interruptions along the way. It ended at index 2025 with the prime 59.

Serge Batalov got his second terminating sequence in 134856 after it had reached a maximum height of 102 digits. His computations began where Wolfgang Creyaufmüller had left off at 100 digits at index 710.

After coming tantalizingly close with 48462 (see below), Frank Schickel finally achieved his first terminating sequence in 163716, and in so doing, made second place in the list of highest terminating sequences at 118 digits. His work began where Wolfgang Creyaufmüller had left off at 100 digits at index 655.

Serge Batalov set a new record for the longest single sequence by extending 195528 beyond the length of 1578, the previous record held by Christophe Clavier for over three years. Beginning where Wolfgang Creyaufmüller left off at index 3974 where 195528 was driven by 2^2 * 7 at 100 digits, Serge computed the sequence to an escape from that driver at 110 digits. The downdriver was then acquired at that level, initiating a drop to 34 digits. The sequence was subsequently driven back to the height of 101 by 2^4 * 31, and after reaching 115 digits, another long decline reduced the size twice to only 12 digits. Eventually, a return of the 2^2 * 7 driver occurred at 28 digits, sending the sequence to the height of 116, where escape was unfortunately to the 2 * 3 driver. It has now reached the index 7972 at 140 digits. 1578 is at index 7261, and also collapsed to the 2 * 3 driver.

Ignacio Santos set a new record for the highest escape from the 2^3 * 3 * 5 driver at 135 digits in 167148, exceeding the previous high of 129 in 162126.

Ignacio Santos acquired the downdriver at 141 digits in 199152, exceeding the previous record of 140 he had previously set in the very same sequence. The earlier downdriver run lasted only 14 lines, with subsequent computations increasing the size from 137 to 141.

Mikael Klasson set a new standard in 139314 for the longest downdriver run by surpassing the records recently set by Markus Tervooren described below. Size was reduced from 131 to 23 for a reduction of 108 digits, and the total length was 565 lines. After getting as low as 17 digits, the 2^2 * 7 driver was acquired at size 18, and when escape was finally achieved, the sequence had returned to triple digits.

Serge Batalov terminated 191430, thus becoming the first to terminate a six-digit sequence after it had reached triple digits. Beginning where Wolfgang Creyaufmüller had left off at index 1243 where the sequence was at what turned out to be its maximum height of 100, the downdriver was acquired at 99 digits at index 1267, leading to its ultimate termination. This broke a three-way tie at the previous maximum height of 99 for six-digit terminating sequences held by Wieb Bosma in 261306 and Wolfgang Creyaufmüller in 108072 and 133596.

Ignacio Santos obtained the downdriver in 199152 at a new record height of 140, surpassing the previous high of 134 set by Markus Tervooren in 162126. In addition, it was obtained while simultaneously losing the '3', breaking the previous record of 133 digits recently set by Mikael Klasson in 103920.

Markus Tervooren completed a remarkable downdriver run in 162126, breaking previous records by a substantial margin. The reduction is size was 101 and the length was 536, surpassing the previous records of 88 an 436 respectively, set by Christophe Clavier in 6822.

Max Dettweiler posting at mersenneforum.org set a new record for the highest escape from the 2^6 * 127 driver at 105 digits in 102264, edging out the previous record of 104 set by Wolfgang Creyaufmüller in 82728. Of special interest was that the escape was directly to the downdriver, exceeding the previous high of 76 digits for such a transition from this driver held by Wolfgang in 838476.

Dennis Langdeau set a new record for the highest escape from the 2^4 * 31 driver at 129 digits in 5778. The previous high was 119 in 6822.

Christophe Clavier broke the record for the highest escape from the 2^5 * 7 guide at 143 digits in 3366. The previous record was 119 digits in 1512.

Wieb Bosma posted a remarkable length result for 314718, and Frank Schickel reconstructed the sequence after spotting it on Wieb's web page. Subsequent analysis revealed that it had merged with 4788 (314718:i6466 = 4788:i6 = 60564) so that the combined 314718/4788 set a new record as the longest sequence pair, now at index 9009. That dropped 389508/34908 to second place at index 8032 and 483570/1920 to third among paired sequences at index 6669.

Frank Schickel has written a valuable new graphing program for aliquot sequences. Programmed in Delphi using Steema software, sequences in virtually any format can be loaded and then saved as a GIF graphic file. I've added a graphics page with especially interesting examples, most of which are discussed or mentioned on this page. Others include 76686 and the terminating 133596, both by Wolfgang Creyaufmüller.

Members of mersenneforum.org in the Aliquot-sequence section set what was then a new record of 116 digits for the highest escape from 2^2 * 7 directly to the downdriver in 10212 at index 1614. The previous record was 111 digits in 1734 at index 1484. 10metreh began by extending the work of Wieb Bosma and Wolfgang Creyaufmüller, and Andreas Schindel began the downdriver run, eventually ending at 82 digits. The 2 * 3 driver was acquired at the height of 97, sending the sequence to its current size of 138.

Older News

62850 set what was then a new record for the highest terminating sequence when it finished on September 3rd, 2008, exactly one week after aquiring the downdriver at 121 digits. See below for details.

Late in the morning of July 20th, 2008, 98790 ended in the prime 13. It was second in length (4443) and now third in maximum height (112) for terminating sequences. 446580 continues in first place in the category of longest terminating sequence at 4736.

Christophe Clavier broke multiple records with a downdriver run of historic dimensions in 6822: it was the longest at 436 lines and produced the biggest reduction in size of 88, falling from 129 to 41 digits. The previous records were 386 and 81 respectively, in 33960. In addition, it reached a new record height (137) for a sequence that would later aquire the downdriver. Christophe had earlier broken the record for the highest escape from the 2^3 * 5 guide at 133 digits in this sequence, surpassing the previous record of 119 set by Igor Schein in 7890.

Christophe Clavier escaped the 2 * 3 driver at a new record height of 139 in 1464, surpassing the previous record of 125 which he also set for 3876. The sequence is now guided by 2^4 * 3^2.

Frank Schickel obtained the downdriver in 144984 at 128 digits, then the fifth highest overall. Size was reduced to 95, where the downdriver was lost directly to the 2^3 * 5 guide. It achieved the milestone of 7000 lines and ended up driven by 2^5 * 3 * 7 at index 7010 and height 132.

Frank Schickel obtained the downdriver in 47728 at 122 digits, a new record height for sequences that began in the five-digit range. The previous high was 115 for 48462 and 82728. The downdriver was lost at the height of 112, and the sequence is now driven by 2^3 * 3^2 at 133 digits.

Christophe Clavier escaped the 2^3 * 3 driver at a new record height of 143 in 2484, surpassing the previous record of 142 which he also set for 1560.

11670 was the 22nd sequence to aquire the downdriver at a size of at least 110 digits, and became the first of these to terminate when it ended in the prime 193 on September 4, 2007. See below for details.

Wolfgang Creyaufmüller extended 144984 from its previous target height of 80 digits at index 1638 to a confluence with 391040 at index 5255: 144984:i5255 = 391040:i6 = 1031680. 391040 was thus reduced to side-sequence status. Wolfgang continued computations of 144984 to 101 digits, where it reached the index 6531, and thus replaced 8760 as the second longest single sequence. 144984 was later computed by Frank Schickel (see above).

Frank Schickel extended 48462 from where I left off to an escape from the 2^4 * 31 driver that had controlled the sequence since its aquisition at height 43. Escape came at 113 digits, the second highest for that driver. He then obtained the downdriver at the size of 115 digits, then a new record height for such aquisition in a sequence beginning in [10^4, 10^6]. The downdriver was lost at 103 digits but was reacquired at height 106 and then again at 108 digits, resulting in a reduction of size to 60. Numerous downdriver runs followed, eventually dropping the sequence twice to only 9 digits. Unfortunately, the recalcitrant 2^6 * 127 driver was acquired at 17 digits, sending the sequence to the height of 123.

Benoît Chevallier-Mames set what was then a new record for the highest aquisition of the downdriver: 133 digits in 9684. This surpassed the previous record of 132 digits set by Christophe Clavier at index 4359 in 1578. The downdriver was lost at size 113, but two more downdriver runs reduced the size all the way to 39. The 2^2 * 7 driver took over directly from there, and has driven the sequence to 135 digits.

Eric Nelson-Melby extended 34908 to index 5088 and height 124. In March of 2002, Wolfgang Creyaufmüller had found 389508 to be a side-sequence of 34908: 389508:i2919 = 34908:i7 = 113464. As a result, the combined sequence 389508/34908 (see graph) was at a then record index of 8032.

Stable Sequences in [10^4, 10^5]

The following sequences are currently "stable" in that they are not being propelled upward by a driver, guide, or by the presence of that pesky '3':

89190 c107 sz 114  Z/W
20076 c129 sz 130  B/C/S
38052 c128 sz 131  B/C/S

(B=Bosma, C=Creyaufmüller, W=Tom Womack, Z=Zimmermann, S=Stern

The current status of the 822 unresolved sequences that began with five digit numbers is partially given in this text file. Please check the master database for more recent results for certain sequences.

In July, I uploaded every sequence I've worked on since November of 2003 to the master database that had more lines than were already there. I'm currently working on the following list of 20 in the 5-digit range:

11408 14280 20076 21756 23142 29360 35196 38052 38880 41412 52374 55752 56928 63660 67920 72336 75798 81576 81600 85716.

Two are stable, and the others are one possible step from stabiliy. They are of the form 2^n * 3 (n even) or 2^3 * 5.

Sequences that reached triple digits before terminating

Highest driver escapes

My results

I've found fifteen terminating sequences and two new confluences:

757512 terminated on May 20th after reaching a maximum height of 110 digits. Originally computed by Wolfgang Creyaufmüller, he acquired the 2^5 * 3^2 * 7 guide at 69 digits, which was still in effect when he left off at index 571 at 82 digits. A Forum member obtained a one line escape four lines later, whereupon it snapped back to something even worse: the 2^5 * 3 * 7 driver. However, an escape from that came at 93 digits, and was left off guided by 2^5 * 3^2 * 5 at 100 digits. I began work on May 15, and stability was achieved just 10 lines later at 103 digits. It continued to run up all the way to 110 digits where the downdriver was obtained. That reduced the size to just 105, but another downdriver run went from 105 to 34. This rates tenth in size in the overall list of terminations.

On March 7th, 92898 terminated after having reached a maximum of 107 digits. Paul Zimmermann originally computed this to 80 digits where it was guided by 2^4 * 3 at index 1084. I extended it to index 2459 where it was driven by 2^2 * 7 at 92 digits. Wolfgang Creyaufmüller then advanced it to an escape from that driver, leaving off at 101 digits on August 28, 2005 where it was guided by 2^4 * 3 * 5. Continuing on August 30, 2005, I captured the downdriver at 107 digits on May 2nd, 2006, leaving off with the 2^2 * 7 driver at the height of 102. Encouraged by the recent success Mersenne Forum members were having escaping drivers in the 5-digit range, I began attempting the same on my own sequences that previously had downdriver runs beginning in triple digits. For 92898, that process began March 6th. Escape from 2^2 * 7 came after only 11 steps, with the downdriver soon recaptured, leading to termination the next day.

On November 18, 2009, 98616 terminated after reaching a maximum of 118 digits: 98616i2790=43. Paul Zimmermann originally computed this sequence to the target height of 80 digits where it was driven by 2 * 3^2. In April of 2003, Wolfgang Creyaufmüller escaped this driver at 90 digits, leaving off at the size of 99 where it was then driven by 2^3 * 3^2 * 5. In August of 2005, he added 14 more lines, increasing the size to 104. On February 26, 2008 I began working from there. After reaching 118 digits, the downdriver was obtained at 115, reducing the size to 99. The downdriver was acquired a second time at 115 digits, this time leading to a finish.

On September 3rd, 2008, 62850 broke the record for the highest terminating sequence one week after aquiring the downdriver at 121 digits. Paul Zimmermann originally computed this sequence to the target height of 80 digits where it was guided by 2^5 * 3 at index 740. I continued from there, and obtained the downdriver at 90 digits, resulting in a drop to the height of only 18. Eventually it rebounded to 94 digits, where I left off at index 2948 in March of 2003. Wolfgang Creyaufmüller advanced the sequence to 101 digits in February 2005, where it was driven by 2^3 * 3^2 at index 2978. I continued computations on July 15, 2006, with the downdriver obtained on August 27th of this year. That produced the second longest downdriver run, reducing the size by 82 digits. It finished at index 3973 in the prime 41.

On July 20th, 2008, 98790 terminated after reaching a height of 112: 98790i4443=13. Paul Zimmermann originally computed this sequence to the target height of 80 at index 3115 where it was guided by 2^5 * 3. I extended it to 99 digits where it was driven by 2^3 * 3^3 * 5 at index 3200 on October 2002. Wolfgang Creyaufmüller moved it past the 100-digit mark at index 3209 and size 103 in August of 2005. I restarted computations from there on July 7th, with the downdriver acquired on July 17th, leading to termination three days later.

In the evening of September 4, 2007, 11670 terminated after reaching a new record height (for terminating sequences) of 113. Wieb Bosma originally computed this sequence to 91 digits where it was guided by 2^6 * 3 * 5 at index 954. Wolfgang Creyaufmüller advanced it to a height of 101 at index 979 on November 2, 2003 where it was at the last line of a run by 2^5 * 3^2. I began working from there on December 25, 2005, eventually leaving off at 1024. 2^2 * 3 * C109 sz 110 on August 30, 2006. The addition of GGNFS to my factoring resources on May 6th of 2007 enabled the resumption of work on this sequence on August 23rd, and on that date it achieved stability for the first time in this century. The downdriver was acquired on August 30th at height 113, which eventually led to termination at index 3534 with the prime 193.

On May 5, 2007, 15960 terminated after reaching a new record height (for terminating sequences) of 109. Wieb Bosma originally computed this sequence to the target height of 90 digits at index 749, where it was driven by 2^3 * 3^3 * 5. Wolfgang Creyaufmüller extended it to 100 digits in November of 2003, achieving an escape from from that driver and leaving off at index 782 where it was guided by 2^2 * 3. On February 20, 2005 I began from there, working off and on over the next couple of years. Eventually, the downdriver was obtained at height 106 on May 3rd, and it terminated two days later at index 2033 and prime 41.

On September 16, 2006, 77880 was found to be a side-sequence of 21546: 77880:i1470 = 21546:i72 = 1373808. Paul Zimmermann originally computed this sequence to the target height of 80 at index 454 where it was being driven by 2^3 * 3 * 5. As part of a project to advance all sequences in [50,000, 100,000] to a height of at least 90, Wolfgang Creyaufmüller brought 77880 to a height of 93 at index 494 on May 27, 2003 where it was then driven by 2^2 * 7. Two years later, Wolfgang advanced the sequence to the new target height of 100 at index 541. His computations included an escape from 2^2 * 7 at 98 digits, and finished on May 29, 2005 under the control of 2^3 * 3^2. On September 15th of last year, I began work to further extend the sequence. It quickly escaped from that driver, and acquired the downdriver at its maximum height of 103. A precipitous decline quickly ensued, culminating in the merger with 21546 the next day. This is a new record for the greatest height reached by a side-sequence (prior to confluence). The previous record was held by 72288 and 109086, both of which reached a maximum of 90 digits.

Near midnight of May 29, 2006, 45984 ended in the prime 11 at index 1490 after reaching a new record height (for terminating sequences) of 107. Wieb Bosma originally computed this sequence to the target height of 90 digits, at index 499. My initial efforts reached an impasse on March 15, 2002 at index 589 and height 101. I added a few lines on October 15, 2004, leaving off at height 103 and index 598, stuck on a 100-digit composite. Things finally got going again on December 18, 2005. After reaching a maximum height of 107 digits at index 841, the downdriver was obtained on May 27, 2006 at 106 digits, which produced an exceptionally long drop to 54 digits. Only brief interruptions separated the succeeding downdriver runs which led to a successful conclusion.

17130 ended in the perfect number 8128 at index 3225 on August 26, 2005. Wieb Bosma originally computed this sequence to 98 digits at index 1498, where it was guided by 2^4 * 3^2. In December of 2003, Wolfgang Creyaufmüller continued computations, finding that it quickly lost the 3 and acquired the downdriver at height 99 which resulted in a decline to 80 digits. Eventually it came under control of 2^3 * 5, and Wolfgang left off at the target height of 100 digits at index 1827. On March 9th of 2005 I added a single line, and did not do anything more until August 23rd of that year. The sequence escaped from 2^3 * 5 at index 1836 and acquired the downdriver at height 101, which quickly led to its termination.

21024 terminated on April 30, 2005 after reaching a new record height (for terminating sequences) of 103 digits: 21024i2423=1429. Wieb Bosma originally computed 21024 to 98 digits at index 1011. In January of 2004, Wolfgang Creyaufmüller extended it to 101 digits at index 1023, leaving off at 2^4 * 3^2 * 131 * C97. On April 14th of 2005, I began working where Wolfgang left off. After reaching 103 digits, the downdriver was obtained on April 18th at a height of 102 digits, with termination achieved twelve days later.

56368 finished on April 5, 2005, breaking the record set by 3630 for terminating sequences by reaching 102 digits: 56368i3446=43. Paul Zimmermann initially computed this to a height of 80 digits at index 789 where it was under control of the 2^6 * 127 driver. Wolfgang Creyaufmüller extended it all the way to index 1931 after observing a quick escape from that driver at the 81-digit mark and a big drop to 36 digits. He left off on July 11, 2003 at the target height of 90 where it had become stable at 2^2 * 5. Two days later my efforts began, resulting in an advance to 100 digits on December 16, 2003 at index 1992 where it stalled at 2^2 * 3 * 41 * 53 * C95. After a gap of more than a year, I resumed work with a faster computer on January 7, 2005. After reaching 102 digits, the downdriver was obtained on March 31 which led to a disappointing drop of only 100 to 95 digits. A brief interlude with 2^4 * 31 was followed by another aquisition of the downdriver which was much more productive, culminating in the prime 43 being reached the next day.

62832:i1740 = 43 on June 28, 2002, reached a maximum of 100 digits. My computations began where Paul Zimmermann left off at 80 digits.

23910 terminated on April 21, 2004 after reaching a maximum of 100 digits by entering the amicable pair (1210, 1184): 23910i1891=1210. Computations began where Wolfgang Creyaufmüller left off at 100 digits. Wieb Bosma had originally computed this to 92 digits at index 1121.

105384 terminated on April 1, 2004 after reaching a maximum of 96 digits by entering the same amicable pair: 105384i2846=1210. This time my computations began where Juan L. Varona and Manuel Benito had left off at 80 digits.

72288 reached a height of 90 digits before merging with 11408 on July 17th, 2002: 72288:i1642 = 11408:i6 = 85808. Paul Zimmermann had initially computed this to 80 digits.

Could the Catalan-Dickson Conjecture be true?

There has been a dramatic reduction in the number of new terminating sequences as we moved from heights in the 80s, 90s, and now to the 100s. It took nearly four years after Juan L. Varona and Manuel Benito terminated 3630 before a new record was achieved (56368), and the former continues to be the highest a terminating sequence has reached in the select region below 10^4. In spite of our access to faster computers and improved software, only nine sequences have terminated after reaching a height greater than 110 digits. The long obstacle course that must be negotiated from such levels has proved daunting indeed.

Unresolved sequences in [1, 10^4] that began a downdriver run after reaching 100 digits

* This column refers to the maximum height each sequence had attained before initiation of a downdriver run.

A downdriver run is defined here to be a series of at least two consecutive iterations containing the downdriver, and is considered to have ended upon reaching two consecutive lines that both do not have the downdriver.

Note: The table for sequences beginning with five-digit numbers has grown too large, and has therefore been moved here.

Utilities for aliquot sequences

The programs in routines.zip perform various functions:

renumber.c adds lines from one file to another if a confluence exists between them. The added lines are renumbered.
num2elf.c converts the "numbers" type files of Ivo Duentsch to the .elf format.
elf2num.c is the reverse of num2elf.
cl2elf.c converts the files of Christophe Clavier to the .elf type.
elf2cl.c is the reverse of cl2elf.
merge.ub locates the first point of confluence between two files that have merged.
ck.ub runs a quick check of the soundness of a file.
check.ub does a thorough check of a file.
uu.bat is a routine for running UBASIC programs from the command line.
seq.c writes the last portion of an aliquot file to seq.txt. The number of each line is removed and replaced by its size, which is given at the end of the line. The purpose is to make it easier to follow the course of a sequence beyond a point specified by the user. Enter the sequence number as the first argument, followed by the starting line number as the second.

32-bit DOS executables: renumber.exe  cl2elf.exe  elf2cl.exe  num2elf.exe  elf2num.exe  seq.exe

Here is a second set of programs, contained in set2.zip

chk.c tests the soundness of an aliquot file, checking for each of the possible errors. Enter the sequence number and one of the standard files will be opened: elf, num or those of Christophe Clavier. Alternatively, enter the complete file name as the argument. If an error is is found, the details are displayed and the program exits. Therefore, it should be run again after repairing the faulty line to check for additional errors. This function can be utilized in a program by testing for an error code of 1 to determine if a file is unsound. It can thus be employed to test multiple files automatically.

alk.c is a new aliquot sequence compression function similar to that of Jesper Gerved, used extensively on this web site. Unfortunately, the latter is limited to sequences that reach a maximum of 144 digits, a level that has been frequently surpassed of late. Enter an argument in the same manner as chk.c: if only the sequence number is given, the program will be applied to one of the standard types, searching in the order .elf, Clavier then num. Alternatively, enter the full name of any file whose contents are of the standard type. A check is first made of the file's soundness, as the process will not succeed if any errors are present. After passing that test, the essential data is saved in a file with the extension .alk. To decompress, enter just the sequence number, and the .alk file will be detected with the original contents reconstructed as an .elf file. When both an .elf and .alk file exist for a given sequence and only the sequence number is entered as the argument, the situation is ambiguous. Here is how it's handled: a comparison is made between the last index of the two files. If the index of the .elf file is bigger, then it is assumed that compression is desired, and a new .alk file is created. This prevents lines added since the last compression from being wiped out by the outdated .alk file. In either case, the result is that both files are up to date. Though .alk files are bigger than the corresponding .alq's, the new ones become much smaller after zip compression is applied compared to zipped alq's.

appendat.c (append .dat file) facilitates distributed computing for Msieve's quadratic sieve. It appends the contents of the .dat file found in a given location (whose path is entered as the function's argument) to the one present in the current directory. A check is made to verify the corresponding composites are the same. For Yafu, use appendyf.c (see below).

convert.pl is Perl script that converts the output of Msieve's polynomial selection to the form used by GGNFS. This was written according to the detailed instructions gratefully provided by Jeff Gilchrist. The script calls for the project name as the argument. Therefore, to run GGNFS with Msieve creating the .poly file, use the following steps:

msieve -v -np -i <name>.n
convert.pl <name>
factmsieve.pl <name>.n

If the second core of a computer is available and not in use, then the speed of Yafu can be doubled. After beginning execution of that function, switch to another directory and execute Yafu again for the same composite. When the sum of the two relation sets reaches somewhat more than half of the required number, stop both, execute appendyf in the first directory using the address of the second as the argument and restart Yafu. If significantly more relations remain to be accumulated, go to the second directory, delete siqs.dat and run Yafu again there. After a little while, stop both and repeat as explained above. The same process can be used for Msieve, using appendat instead of appendyf. For two Yafu's, try the combining process when both reach 17,000 relations. For Msieve, look for the relation sums to reach 45% to 50% of the required number before switching to the combining phase.

Averages for downdriver runs
(These are based on the 2494 sequences below 251712)

Record downdriver runs

Record reductions in size from a downdriver run:

Highest downdriver aquisitions in [1, 10^4]

Highest downdriver aquisitions in [10^4, 10^6]

Clifford Stern
Santa Monica, California
ax810@lafn.org

This page last updated August 18, 2010.