This page presents a list of 'the repeated factorisation of concatenated primefactors (in ascending order) of the composite numbers from 1 to 100'. I know, this description, quite a mouthful. An easy example clarifies the procedure in the twinkling of an eye. Let me take the at first sight dull composite number 14. This startnumber 14 has two factors 2 and 7. Now paste these two factors together (from smallest to greatest) and you'll end up with the new number 27. Repeat the procedure with number 27.27 = 3 x 3 x 3. Concatenation of these three factors gives the number 333.
So step 3 becomes 333 = 3 x 3 x 37. Step 4 : 3337 = 47 x 71 Step 5 : 4771 = 13 x 367 Step 6 : 13367 = Prime ! Thus the expansion stops after six steps.
This approach is best described as breaking the number into its prime constituents. These latter then reassemble in ascending order quite willingly thereby forming ever greater numbers until miraculously a prime number is created which of course refuses to break down. The chain-reaction stops.
It's a way to make composite number as interesting as prime numbers. Many composite numbers become prime in less than 6 steps but quite a few need many more steps. The following list shows the steps for composite numbers up to 100. Number 77 has the same expansion as number 49 because 49 equals 7 x 7 which is 77 ! and need therefore one step less to become prime. We haven't reached its 'home' prime number yet... Can you help ?
It may become a very tedious job as the number of primes thins out. The chance that a randomly formed larger number is prime gets smaller and smaller. Yet there are infinite primes. Eventually it must happen !
Read also James G. Merickel's Wikipedia article about our Home Prime.
On [ April 24, 1999 ] Jeffrey Heleen (email) passed me the following information :
" On your webpage I see that your results match mine. I originally thought of the problem around 1990 and using only a '386 computer' created the same table up to 1000. I wrote an article published in the "Journal of Recreational Mathematics" a few years ago titled 'Family Numbers' describing my efforts. Family Numbers: Constructing Primes by Prime Factor Splicing, JRM Vol. 28 #2, 1996-97, pp. 116-119. I notice that for a start number of 49 that it has been taken up to the 55th step, the same place I was stopped. I was using the UBASIC program ECMX, modified slightly, to do the search. I made it up over 1130 curves before stopping. At present, the numbers smaller than 1000 which do not yet have endprimes are: 49, 146, 234, 242, 284, 300, 312, 320, 322, 326, 328, 336, 352, 360, 363, 372, 407, 412, 414, 460, 495, 548, 556, 558, 576, 592, 596, 642, 663, 665, 670, 693, 712, 714, 715, 744, 749, 762, 768, 782, 796, 800, 845, 847, 858, 861, 864, 866, 867, 896, 908, 925, 964, 969, 973, 978, 984 and 992. Some numbers are left out as they can be categorised to smaller starting numbers, for instance 77 and 711 belonging to initial number 49. Included are only the initial starting numbers although in the article chart all numbers are referenced. Some of these I have taken quite far but not found a solution. I know there are limits using the ECM method. I have heard of the Number Field Sieve method but don't know much about it or where to get it. Perhaps with that program some progress can be made. I just found your page and thought it interesting. It surprised me to find others had worked on this problem, (I had thought it original to me). I like all the material you've presented, it gives lots of food for thought. I'm sure I'll be spending some time here. :) ..."
Some numbers are left out as they can be categorised to smaller starting numbers, for instance 77 and 711 belonging to initial number 49. Included are only the initial starting numbers although in the article chart all numbers are referenced. Some of these I have taken quite far but not found a solution. I know there are limits using the ECM method. I have heard of the Number Field Sieve method but don't know much about it or where to get it. Perhaps with that program some progress can be made. I just found your page and thought it interesting. It surprised me to find others had worked on this problem, (I had thought it original to me). I like all the material you've presented, it gives lots of food for thought. I'm sure I'll be spending some time here. :) ..."
On [ May 12, 1999 ] Jeffrey Heleen (email) sent me a first update of his work.
"... Now that I have somewhat more computing power than before (300 MHz vs. 25 MHz) I've started on the unsolved numbers less than 1000 once again. To date, of the numbers I previously sent you that were unsolved, I have found endprimes for three of them. Namely 360, 372 and 412. (PS. They are striked out in this list). I have uncracked composite numbers for all those less than that and am still working on the rest of the list. Attached is a text file created in Notepad of the uncracked numbers. (PS. Available on simple demand). Hopefully someone else out there may be able to take them further. I'll keep you posted as things develop."
On [ August 14, 1999 ] Jeffrey Heleen (email) sent me a second update of his work.
" Ok, as it now stands the unsolved numbers on the last list I gave you (smaller than 1000) that have been solved are: 360, 372, 412, 558, 642, 693, 744, 796, 800, 847, 864, 867, 908 and 984. Endprimes have been found for these."
On [ November 8, 1999 ] Paul Leyland (email) made a breakthrough by cracking the c105 composite number from step 56 of HP(49) or step 55 of HP(77). (Repeated Factorisation of Concatenated Primefactors of the Composite Numbers)
The factors are p41 * p65, or 21034137982005155236145561292210835084361and 20679893341907378249919955987757483932846633610599367336113869677 He obtained these two prime factors by running his MPQS program for only a week ! The very same day - but alas(!) some 6 hours later - these results were already confirmed when a second contender Eric Prestemon send me also the same factors p41 and p65. Eric Prestemon used Paul Zimmermann's GMP-ECM software.
21034137982005155236145561292210835084361and 20679893341907378249919955987757483932846633610599367336113869677
He obtained these two prime factors by running his MPQS program for only a week ! The very same day - but alas(!) some 6 hours later - these results were already confirmed when a second contender Eric Prestemon send me also the same factors p41 and p65. Eric Prestemon used Paul Zimmermann's GMP-ECM software.
go directly to table entry
On [ June 14, 2000 ] Paul Leyland (email) made a new breakthrough by cracking the c137 composite number from step 74 of HP(49) - or step 73 of HP(77) - using ECM.
" After almost six months of computation on a PII-300, Paul Leyland can reveal that this number factors as p46 * p91. It was found after ~ 5000 curves at B1=3M and3350 curves at B1=11M. The two factors are respectively 3804796914905629947782783176497447433056300673and 297575514989250201776144220639738150129498705/ 0078840501836673559420025718611870754546792073 "
The two factors are respectively 3804796914905629947782783176497447433056300673and 297575514989250201776144220639738150129498705/ 0078840501836673559420025718611870754546792073 "
On [ August 6, 2000 ] Igor Schein (email) sent me some results of his investigationof numbers greater than 1000.
" I've been looking at sequences for some N>1000. Here's one which finishes after 54 steps: N = 2092. 2 * 2 * 523 101 * 223 ... and the home prime is formed from concatenating these last factors : 4007 * 9923 * 47303 * 636171471679 * 49567980853079631127541759358497387 * 11979321332839520964445116714814558542751169 I'm also looking at some sequences in bases other than base 10. For example, base 2: (100 = 4) -> (1010 = 10) -> (10101 = 21) -> (11111 = 31) The longest terminating sequence in base 2 I found so far is the one starting at N = 1345, which terminates after 130 steps. There are 2 values of N <= 3500 for which the sequence is longer than 130, but I haven't been able to terminate them yet."
I'm also looking at some sequences in bases other than base 10. For example, base 2:
The longest terminating sequence in base 2 I found so far is the one starting at N = 1345, which terminates after 130 steps. There are 2 values of N <= 3500 for which the sequence is longer than 130, but I haven't been able to terminate them yet."
On [ November 25, 2000 ] Sander Hoogendoorn (email) informed me he started collectingthese Home Primes for numbers greater than 100. His database can now be consulted at the following address
He reached already up to 312 and will whenever he has the time update his pages on a regular basis. A great initiative indeed, Sander, for which we are all very grateful!
On [ April 5, 2002 ] Alex Kruppa (email) & Paul Leyland (email) are delighted to announce that they have factored HP49(80).c138 ( p69 * p70 ) with the general number field sieve. The prime factors are
224690133218881151252602753388830692415125120972614888557571233246513 (69 digits) and 3344456987746930138631822411149806794710441073001296631385753707501227 (70 digits).
"Between us we had run enough ECM curves to be fairly sure that no factor would have fewer than 45 digits. The result above shows why ECM was not successful. We both searched for polynomials and each found about a dozen reasonable candidates. The best polynomial was found by Alex and was –117571849151668295576809408045 + –483923124317877121410587521 * X 139472015921577159080103 * X^2 50167688067225969677 * X^3 1181017574467178 * X^4 355927036920 * X^5 with root 18403894182248001767571928 mod N. Alex used Jens Franke's lattice siever; Paul used the CWI implementation of the line siever. The factor bases used primes up to 3M and 10M on the rational and algebraic sides, and large primes up to 500M and 1000M respectively. Elapsed time for sieving was around three weeks on a variety of machines; cpu time used was around 2 cpu years though we don't have accurate figures available at present. At the end of the sieving phase, Alex had produced 49,256,164 unique relations (88% of the total) and Paul 6,811,163 (12%). There were duplicates in the combined relations and we finished the factorization with 53,687,196 unique relations. The filtering, linear algebra and square root phases were performed at Microsoft Research Cambridge because of the very heavy memory requirements of the first two phases. The first filtering step took about 1.4 gigabytes of active memory and was run on a machine with 2GB of RAM. The filtering stages resulted in a matrix with 2,540,557 rows and 2,535,422 columns with a total weight of 119,862,073 set bits. The linear algebra was performed with CWI's implementation of parallel block Lanczos running on all 32 PIII-1000 cpus of MSRC's cluster. It took close to 54 hours elapsed time, but only 14 hours cpu time per processor, to find 127 dependencies. Each process used abut 40MB of memory, for a total of almost 1.3GB. The factorization given above was found on the first dependency by the square root phase, which took 7.5 hours computation on a PIII-500 machine. We have not yet found the home prime. The next stage is composite, and we have already reduced it to p1 * p7 * p16 * c136. Further ECM runs are in progress and we'll let youknow if we find more factors."
We both searched for polynomials and each found about a dozen reasonable candidates. The best polynomial was found by Alex and was
–117571849151668295576809408045 + –483923124317877121410587521 * X 139472015921577159080103 * X^2 50167688067225969677 * X^3 1181017574467178 * X^4 355927036920 * X^5
with root 18403894182248001767571928 mod N.
Alex used Jens Franke's lattice siever; Paul used the CWI implementation of the line siever. The factor bases used primes up to 3M and 10M on the rational and algebraic sides, and large primes up to 500M and 1000M respectively. Elapsed time for sieving was around three weeks on a variety of machines; cpu time used was around 2 cpu years though we don't have accurate figures available at present.
At the end of the sieving phase, Alex had produced 49,256,164 unique relations (88% of the total) and Paul 6,811,163 (12%). There were duplicates in the combined relations and we finished the factorization with 53,687,196 unique relations.
The filtering, linear algebra and square root phases were performed at Microsoft Research Cambridge because of the very heavy memory requirements of the first two phases. The first filtering step took about 1.4 gigabytes of active memory and was run on a machine with 2GB of RAM. The filtering stages resulted in a matrix with 2,540,557 rows and 2,535,422 columns with a total weight of 119,862,073 set bits. The linear algebra was performed with CWI's implementation of parallel block Lanczos running on all 32 PIII-1000 cpus of MSRC's cluster. It took close to 54 hours elapsed time, but only 14 hours cpu time per processor, to find 127 dependencies. Each process used abut 40MB of memory, for a total of almost 1.3GB.
The factorization given above was found on the first dependency by the square root phase, which took 7.5 hours computation on a PIII-500 machine.
We have not yet found the home prime. The next stage is composite, and we have already reduced it to p1 * p7 * p16 * c136. Further ECM runs are in progress and we'll let youknow if we find more factors."
Alex and Paul, that is top level programming, congratulations!
On [ May 16, 2002 ] Alex Kruppa (email) & Paul Leyland (email) have factored HP49(81).c136 ( p51 * p85 ) using the general number field sieve. The prime factors are
448583441180516821621320259546896223296373907144113 (51 digits) and 3541865184678001629601182607226312880348900246844/848900227068283166325369629573991313 (85 digits).
"We factored the c136 with GNFS using parameters very similar to those used for theprevious c138 and took a closely similar amount of processing power so I won't repeatall the details I gave last time. On this occasion, Alex found the polynomial and performedabout 95% of the sieving. I did the filtering, linear algebra and square root phases. Forsome reason, this factorization caused us many more problems than the previous oneand several bugs or inadequacies in our software came to light. One such problem forced usto do the linear algebra twice, on two slightly different matrixes, and delayed our findingthe factors by several days. Alex would like to thank the Research Unit for System Architecture of the Departmentof Computer Sciences at the Technische Universität München for the use of their computersin the sieving phase. I used two servers at Microsoft Research Ltd, Cambridge for my smallcontribution to the sieving and for the square root phase; the linear algebra was performedon the 32-cpu cluster at MSR Cambridge. HP49(82) is composite, with three small prime factors, one of moderate size (all foundby Alex) and a composite co-factor which will be much easier to factor than its twopredecessors. The current factorization is p1 * p3 * p9 * p30 * c118. We will be workingon the c118 in the near future. Regards, Paul & Alex"
Alex would like to thank the Research Unit for System Architecture of the Departmentof Computer Sciences at the Technische Universität München for the use of their computersin the sieving phase. I used two servers at Microsoft Research Ltd, Cambridge for my smallcontribution to the sieving and for the square root phase; the linear algebra was performedon the 32-cpu cluster at MSR Cambridge.
HP49(82) is composite, with three small prime factors, one of moderate size (all foundby Alex) and a composite co-factor which will be much easier to factor than its twopredecessors. The current factorization is p1 * p3 * p9 * p30 * c118. We will be workingon the c118 in the near future. Regards, Paul & Alex"
Alex and Paul, you both are quite a math-fertile team. Well done again!
On [ May 22, 2002 ] Alex Kruppa (email) & Paul Leyland (email) have also factored HP49(82) and HP49(83)
"We (Alex and myself) would like to report that although we've performed the next two stages in the search for the home prime, HP(49) continues to be elusive. In our previous mail, we reported that HP49(82) contained a c118. We factored that with GNFS. Alex did all the sieving this time and preliminary filtering; I did the remaining filtering, linear algebra and square root phases to discover the p55 * p64 factorization. Sieving took a few days on Alex's machines (credit as before) and the phases I did took about a day in total --- about 40% of the time was spent in the square root program because the first two dependencies gave the trivial factorization and we found the true factors on the third. The next step, HP49(83) was much easier. Several small and medium factors were found by ECM, leaving a c83 cofactor which fell to MPQS in a couple of hours or so. The following step seems to be much harder. It is a c167 which contains no very small factors. We've begun testing with ECM and if anything turns up we will let you know. If ECM doesn't find anything this number will be *very* hard."
In our previous mail, we reported that HP49(82) contained a c118. We factored that with GNFS. Alex did all the sieving this time and preliminary filtering; I did the remaining filtering, linear algebra and square root phases to discover the p55 * p64 factorization. Sieving took a few days on Alex's machines (credit as before) and the phases I did took about a day in total --- about 40% of the time was spent in the square root program because the first two dependencies gave the trivial factorization and we found the true factors on the third.
The next step, HP49(83) was much easier. Several small and medium factors were found by ECM, leaving a c83 cofactor which fell to MPQS in a couple of hours or so.
The following step seems to be much harder. It is a c167 which contains no very small factors. We've begun testing with ECM and if anything turns up we will let you know. If ECM doesn't find anything this number will be *very* hard."
On [ May 25, 2002 ] Alex Kruppa (email) factored HP49(84) using ECM into p53 * p114 The prime factors are
81477382431617858607629654669086224895030590860856949 (53 digits) and 164853464798393151511356156289762200575122773801949600629/560294634580313680599127053982894889995189794735466895119 (114 digits).
"Luck has prevailed. ECM found a 53 digit factor of the c167 of the 84^{th} step of the HP49 sequence and thus completed this factorization. The next step is composite, as of now its factorization is known to be p1 * p2 * p5 * p6 * p16 * c140. ECM may yet find another factor, but even if not, the c140 will be feasible by GNFS. The quest for this elusive Home Prime continues... This is also the fourth largest factor ever found by GMP-ECM and the largest one in the current year so far." GMP-ECM 4c, by P. Zimmermann (Inria), 16 Dec 1999, with contributions from T. Granlund, P. Leyland, C. Curry, A. Stuebinger, G. Woltman, JC. Meyrignac, A. Yamasaki, and the invaluable help from P.L. Montgomery. Input number is 134318287965559312522053506677236571899578936128385172670/ 615409359178147914132583891425336357638349050223174034385/ 38106689190395089953894891189281091736983632645331931 (167 digits) Using B1=11000000, B2=3890888820, polynomial x^60, sigma=219538831 Step 1 took 562640ms for 143669942 muls, 3 gcdexts Step 2 took 255220ms for 63722040 muls, 118193 gcdexts ********** Factor found in step 2: 81477382431617858607629654669086224895030590860856949 Found probable prime factor of 53 digits: 81477382431617858607629654669086224895030590860856949 Report your potential champion to Richard Brent <rpb@comlab.ox.ac.uk> (see Large Factors Found by ECM ) Probable prime cofactor 164853464798393151511356156289762200575122773801949600629/ 560294634580313680599127053982894889995189794735466895119 (114 digits)
"Luck has prevailed. ECM found a 53 digit factor of the c167 of the 84^{th} step of the HP49 sequence and thus completed this factorization. The next step is composite, as of now its factorization is known to be p1 * p2 * p5 * p6 * p16 * c140. ECM may yet find another factor, but even if not, the c140 will be feasible by GNFS. The quest for this elusive Home Prime continues...
This is also the fourth largest factor ever found by GMP-ECM and the largest one in the current year so far."
GMP-ECM 4c, by P. Zimmermann (Inria), 16 Dec 1999, with contributions from T. Granlund, P. Leyland, C. Curry, A. Stuebinger, G. Woltman, JC. Meyrignac, A. Yamasaki, and the invaluable help from P.L. Montgomery. Input number is 134318287965559312522053506677236571899578936128385172670/ 615409359178147914132583891425336357638349050223174034385/ 38106689190395089953894891189281091736983632645331931 (167 digits) Using B1=11000000, B2=3890888820, polynomial x^60, sigma=219538831 Step 1 took 562640ms for 143669942 muls, 3 gcdexts Step 2 took 255220ms for 63722040 muls, 118193 gcdexts ********** Factor found in step 2: 81477382431617858607629654669086224895030590860856949 Found probable prime factor of 53 digits: 81477382431617858607629654669086224895030590860856949 Report your potential champion to Richard Brent <rpb@comlab.ox.ac.uk> (see Large Factors Found by ECM ) Probable prime cofactor 164853464798393151511356156289762200575122773801949600629/ 560294634580313680599127053982894889995189794735466895119 (114 digits)
On [ July 1, 2002 ] Alex Kruppa (email) & Paul Leyland (email) factored HP49(85).c140 using GNFS into p68 * p73 The prime factors are
11825523118615173197502446002728268259724026363566923708566001149123 (68 digits) and 2056156715909184026132747632727779809352896881830754843064666748922417153 (73 digits).
" Alex Kruppa and I have taken the search for HP49 through several more stages. The sticking point was the 140-digit cofactor of HP49(85). We spent a lot of fruitless effort with ECM before turning to GNFS again. As before, Alex found the polyomial and performed over 90% of the sieving, whereas I did the filtering, linear algebra and square-root phases. We found this factorization substantially harder than previous ones in the series. The linear algebra took 65 hours on a 25-cpu cluster; each square root took several hours on a single PIII-500 and the factorization wasn't found until the fourth dependency. The factorization finished on Saturday 29^{th} June. The result, p68 * p73, shows why ECM was unsuccessful. The next two stages were relatively easy and were factored by a fairly small amount of ECM over the weekend. Stage 88 is now being attempted with ECM. We found a few small prime factors and a c155 cofactor."
" Alex Kruppa and I have taken the search for HP49 through several more stages. The sticking point was the 140-digit cofactor of HP49(85). We spent a lot of fruitless effort with ECM before turning to GNFS again. As before, Alex found the polyomial and performed over 90% of the sieving, whereas I did the filtering, linear algebra and square-root phases. We found this factorization substantially harder than previous ones in the series. The linear algebra took 65 hours on a 25-cpu cluster; each square root took several hours on a single PIII-500 and the factorization wasn't found until the fourth dependency. The factorization finished on Saturday 29^{th} June. The result, p68 * p73, shows why ECM was unsuccessful.
The next two stages were relatively easy and were factored by a fairly small amount of ECM over the weekend. Stage 88 is now being attempted with ECM. We found a few small prime factors and a c155 cofactor."
On [ July 22, 2002 ] Alex Kruppa (email) & Paul Leyland (email) factored HP49(90).c176 using only ECM into p38 * p66 * p94 Alex found the p38 factor and Paul found the p44 factor. The prime factors are
52260221223007872743384258441159930329 (38 digits) and 66076192121556175190138089562410746399109073 (44 digits).
" We are continuing to work on the c152. If ECM doesn't find a relatively small factor, we should be able to finish it with GNFS though with some difficulty. We're wondering if we may have to go beyond 100 steps..."
On [ July 24, 2002 ] Alex Kruppa (email) & Paul Leyland (email) factored the remaining HP49(94).c152 using GMP-ECM. Alex got lucky again and found a p51 factor, the 101 digit cofactor being prime. The prime factor is
681195332272435073462164213069789780765696608423481 (51 digits)
" The next step of the sequence HP49(95) is composite, so far the factors 3 * 7 * 26141 * 300119 * 1811141 * 1072782128567282855315039 * c153 are known. The c153 may yet yield another ~35 digits factor, and we will do more ECM before we consider a GNFS factorization, which would seem feasible if somewhat taxing."
go directly to table entries 90-95
On [ January 20, 2003 ] Alex Kruppa (email) & Paul Leyland (email) factored HP49(95).c153 into p68 * p85 starting with a search for GNFS polynomials
" Alex and I have completed two more stages of the search for HP49. When we last mailed you, we were stuck at HP49(95) which had a 153-digit composite cofactor. We first saw the factors of this integer on Saturday 18th January 2003, after a computation that was started back in early September 2002 with a search for GNFS polynomials. Sieving began in mid-November and ended on 28th December. The filtering phase took a week or so, the linear algebra 5.5 days on 30 cpus of the cluster at Microsoft Research, and the square root phase a few hours on a single workstation. We now know that HP49(95) equals 3 * 7 * 26141 * 300119 * 1811141 * 1072782128567282855315039 * 25381603104475027190830989059811875365234972412236/253418807674044481 * 73122383885452606722686858220222364416902310830906/44547260008735024402747827401799039 The last two factors have 68 and 85 digits. ECM successfully factored the next iteration. HP49(96) = 17 * 937 * 2999 * 15011194746557 * 33716362272572345351978861258895209 * 15411267935624560746503422154192060735654946200813/ 37305715946120222833565553933109196280811860424054/ 1265521091783630320332376356814622960926093 where the last factor has 143 digits. The next stage is composite, and we have a partial factorization by ECM: 19 * 569 * 683 * 7450039 * 865252586740571 * 2971814878235479924213 * c151 We are fortunate in that the 151-digit cofactor is within range of GNFS if we can't find any more ECM factors. "
We first saw the factors of this integer on Saturday 18th January 2003, after a computation that was started back in early September 2002 with a search for GNFS polynomials. Sieving began in mid-November and ended on 28th December. The filtering phase took a week or so, the linear algebra 5.5 days on 30 cpus of the cluster at Microsoft Research, and the square root phase a few hours on a single workstation.
We now know that HP49(95) equals 3 * 7 * 26141 * 300119 * 1811141 * 1072782128567282855315039 * 25381603104475027190830989059811875365234972412236/253418807674044481 * 73122383885452606722686858220222364416902310830906/44547260008735024402747827401799039
The last two factors have 68 and 85 digits.
ECM successfully factored the next iteration. HP49(96) = 17 * 937 * 2999 * 15011194746557 * 33716362272572345351978861258895209 * 15411267935624560746503422154192060735654946200813/ 37305715946120222833565553933109196280811860424054/ 1265521091783630320332376356814622960926093 where the last factor has 143 digits.
The next stage is composite, and we have a partial factorization by ECM: 19 * 569 * 683 * 7450039 * 865252586740571 * 2971814878235479924213 * c151
We are fortunate in that the 151-digit cofactor is within range of GNFS if we can't find any more ECM factors. "
go directly to table entries 95-97
On [ July 16, 2003 ] Alex Kruppa (email) & Paul Leyland (email) factored HP49(97).c151 into p55 * p96
" Dear Patrick, we have expanded the HP49 sequence to the 100^{th} step, but still had no luck in discovering the endprime. The difficult part was the factorization of the 151-digit composite cofactor of HP49(97). After we had done enough ECM to be fairly sure that no factors of less than 50 decimal digits remained, we decided to complete this step with a GNFS factorization. Polynomial selection was done with Thorsten Kleinjung's program and most of the sieving was done by Alex with the Bahr/Franke/Kleinjung lattice siever which produced 76M relations using approximately half an Athlon GHz-year. The CWI line siever produced an additional 2M relations by sieving over small b-values for about one cpu week. Duplicate removal, pruning and clique removal was done at the TU München, leaving 18M relations which were then sent to Paul at MS Research, Cambridge, and merged to form a (4.47M)^2 matrix. The matrix took a week to solve on the MSRC cluster and the factors appeared on the first dependency on Monday, 14th of July. The factors are: p55 = 1771052383785311834993979061208604132871538232335055323 p96 = 7160047222541505864838433131582635928178039748055681941 \ 13667109128698119199668739510916110374031 As it turns out, the smaller factor arguably could have been discovered with ECM, however the expected amount of cpu time for ECM to find it would not have been much lower than what we spent on GNFS and, unlike GNFS, would not have guaranteed to actually produce anything. The 98^{th} and 99^{th} step of HP49 factored easily using ECM: HP49(98) = c203 = 3 * 3 * 3 * 3 * 17 * 173 * 313 * 1104769163 * 366751448517289166567507 * p162 HP49(99) = c208 = 107 * 22861 * 3700198301407 * 581535317003127481 * p171 The 100^{th} step, however, appears to be not so easy. This far it is known that HP49(100) = c210 = 3 * 37 * 2789 * c204 We have done enough ECM to be confident that no factors of less than 35 digits remain in the cofactor. Since a number of this size is far out of reach for GNFS with today's technology, we will have to put all our hopes in ECM. If that should fail to factor or at least substantially reduce the size of this cofactor, then this 100^{th} step will mark the end of the HP49 sequence expansion for a long time to come. "
The difficult part was the factorization of the 151-digit composite cofactor of HP49(97). After we had done enough ECM to be fairly sure that no factors of less than 50 decimal digits remained, we decided to complete this step with a GNFS factorization.
Polynomial selection was done with Thorsten Kleinjung's program and most of the sieving was done by Alex with the Bahr/Franke/Kleinjung lattice siever which produced 76M relations using approximately half an Athlon GHz-year. The CWI line siever produced an additional 2M relations by sieving over small b-values for about one cpu week.
Duplicate removal, pruning and clique removal was done at the TU München, leaving 18M relations which were then sent to Paul at MS Research, Cambridge, and merged to form a (4.47M)^2 matrix. The matrix took a week to solve on the MSRC cluster and the factors appeared on the first dependency on Monday, 14th of July.
The factors are:
p55 = 1771052383785311834993979061208604132871538232335055323 p96 = 7160047222541505864838433131582635928178039748055681941 \ 13667109128698119199668739510916110374031
As it turns out, the smaller factor arguably could have been discovered with ECM, however the expected amount of cpu time for ECM to find it would not have been much lower than what we spent on GNFS and, unlike GNFS, would not have guaranteed to actually produce anything.
The 98^{th} and 99^{th} step of HP49 factored easily using ECM:
HP49(98) = c203 = 3 * 3 * 3 * 3 * 17 * 173 * 313 * 1104769163 * 366751448517289166567507 * p162
HP49(99) = c208 = 107 * 22861 * 3700198301407 * 581535317003127481 * p171
The 100^{th} step, however, appears to be not so easy. This far it is known that
HP49(100) = c210 = 3 * 37 * 2789 * c204
We have done enough ECM to be confident that no factors of less than 35 digits remain in the cofactor. Since a number of this size is far out of reach for GNFS with today's technology, we will have to put all our hopes in ECM. If that should fail to factor or at least substantially reduce the size of this cofactor, then this 100^{th} step will mark the end of the HP49 sequence expansion for a long time to come. "
go directly to table entries 97-100
On [ January 3, 2004 ] Alex Kruppa (email) & Paul Leyland (email) wrote the following
" Dear Patrick, we're giving up. We have done 5500 curves at B1=11M, and 9000 curves at B1=44M, but have been unable to find a factor of the c204 of HP49(100). Our resources don't allow us to try ECM much further, so unfortunately we have to give up HP49 at this point - after twenty steps and almost two years since we started working on it. Thank you for keeping track of of the project record, and to all who'd like to take a shot at this composite, we'd like to wish good luck! Alex Kruppa and Paul Leyland "
we're giving up. We have done 5500 curves at B1=11M, and 9000 curves at B1=44M, but have been unable to find a factor of the c204 of HP49(100). Our resources don't allow us to try ECM much further, so unfortunately we have to give up HP49 at this point - after twenty steps and almost two years since we started working on it. Thank you for keeping track of of the project record, and to all who'd like to take a shot at this composite, we'd like to wish good luck!
Alex Kruppa and Paul Leyland "
The decimal expansion of this c204 is 3463691455176168325615805184363381478770628934576796221959292066545246725876130493435583943733963381/ 9458578377526978567521063669642509477685973330594799604806149924956619714721293451242798811342022676/ 2897
On [ February 9, 2010 ] Paul Leyland (email) forwarded the following results from Nicolas Daminelli
" Nicolas Daminelli factored the c204 from HP49 yesterday. His very nice result is below. [ go to table entry ] > Subject: HP49(100) = prp62*prp143. Please review. > Date: Mon, 8 Feb 2010 19:25:03 -0800 (PST) > > All, > Since a lot of effort was put into factoring HP49(100), I thought I > would let you know that I got a lucky ECM for it at B1=260M. > Could someone please double-check this result for primality and input > correctness? > > GMP-ECM 6.2.3 [powered by GMP 4.3.1] [ECM] > Input number is > 3463691455176168325615805184363381478770628934576796221959292066545246725876130493435583943733963381/ > 9458578377526978567521063669642509477685973330594799604806149924956619714721293451242798811342022676/ > 2897 (204 digits) > Using B1=260000000, B2=3178559884516, polynomial Dickson(30), > sigma=1765817006 > Step 1 took 1320152ms > Step 2 took 379725ms > ********** Factor found in step 2: > 13055369049845151421562673963068310715129211918218895785368571 > Found probable prime factor of 62 digits: > 13055369049845151421562673963068310715129211918218895785368571 > Probable prime cofactor > 2653078164203447671850231332797009603029004755483654727809454779301905374228983373655278628689069551/ > 1249799288531238767159656593259713779239907 has 143 digits > Report your potential champion to Richard Brent (email) > (see http://wwwmaths.anu.edu.au/~brent/ftp/champs.txt) > > Cheers, > Nicolas I'm working on extending the chain. For instance, the next value HP49(101) appears to be 3 * 3 * 179 * p209 [ go to table entry ] The one after that HP49(102) is 3 * 7 * 12473 * 69442311247884384744096581 * 5504559912367454438295149601552867774551041 * 3313820999622709417530127238213785731734022602460004639101646954950942392321815618600363064109247466/ 1686802611798393277995398615210685360809 [ go to table entry ] The next stage HP49(103) has a c193. It was dealt with 8-) 29 * 8627 * 89345257 * 8067774497 * 96513008244398921562099305449602682965323 * 91479820611369205267924863199536513832217953 * 233168124361466902944146099855900103168298336973117660251047536278410398151410570271601591803427840895029573 [ go to table entry ] The one after that HP49(104) is 23818343988967755319 * 54777437615079105991 * c178 and, of course, the c178 is having some ECM done on it. [ go to table entry ] The decimal expansion of this c178 is 2288848748830723756709840158262687862277624865467675188746398067991005709059160227428299787778938917/ 125184983761148626168860248112075875959985895793291153197651933268308457583237 Paul "
> Subject: HP49(100) = prp62*prp143. Please review. > Date: Mon, 8 Feb 2010 19:25:03 -0800 (PST) > > All, > Since a lot of effort was put into factoring HP49(100), I thought I > would let you know that I got a lucky ECM for it at B1=260M. > Could someone please double-check this result for primality and input > correctness? > > GMP-ECM 6.2.3 [powered by GMP 4.3.1] [ECM] > Input number is > 3463691455176168325615805184363381478770628934576796221959292066545246725876130493435583943733963381/ > 9458578377526978567521063669642509477685973330594799604806149924956619714721293451242798811342022676/ > 2897 (204 digits) > Using B1=260000000, B2=3178559884516, polynomial Dickson(30), > sigma=1765817006 > Step 1 took 1320152ms > Step 2 took 379725ms > ********** Factor found in step 2: > 13055369049845151421562673963068310715129211918218895785368571 > Found probable prime factor of 62 digits: > 13055369049845151421562673963068310715129211918218895785368571 > Probable prime cofactor > 2653078164203447671850231332797009603029004755483654727809454779301905374228983373655278628689069551/ > 1249799288531238767159656593259713779239907 has 143 digits > Report your potential champion to Richard Brent (email) > (see http://wwwmaths.anu.edu.au/~brent/ftp/champs.txt) > > Cheers, > Nicolas
I'm working on extending the chain. For instance, the next value HP49(101) appears to be
3 * 3 * 179 * p209 [ go to table entry ]
The one after that HP49(102) is
3 * 7 * 12473 * 69442311247884384744096581 * 5504559912367454438295149601552867774551041 * 3313820999622709417530127238213785731734022602460004639101646954950942392321815618600363064109247466/ 1686802611798393277995398615210685360809 [ go to table entry ]
The next stage HP49(103) has a c193. It was dealt with 8-)
29 * 8627 * 89345257 * 8067774497 * 96513008244398921562099305449602682965323 * 91479820611369205267924863199536513832217953 * 233168124361466902944146099855900103168298336973117660251047536278410398151410570271601591803427840895029573 [ go to table entry ]
The one after that HP49(104) is 23818343988967755319 * 54777437615079105991 * c178 and, of course, the c178 is having some ECM done on it. [ go to table entry ]
The decimal expansion of this c178 is 2288848748830723756709840158262687862277624865467675188746398067991005709059160227428299787778938917/ 125184983761148626168860248112075875959985895793291153197651933268308457583237 Paul "
go directly to table entries 100-103
Nicolas Daminelli (email) and Paul Leyland (email) factored HP49(104).c178 = p88 * p90. [ January 11, 2011 ] [ go to table entry ]
" Hi Patrick, After a *large* amount of work Nicolas Daminelli and I can report further progress on HP(49). Eleven months ago we reported the complete factorizations of HP49(100) through HP49(103) and the partial factorization of HP49(104) into two small primes and a 178-digit composite. We have now split that c178 with the general number field sieve; the factors are prp88 factor: 44834403720805672946171216333384339757993452434913200790674799323428\ 10228530227200671373 prp90 factor: 51051169612601980880823648155455991928883186163936778023298602714308\ 8905987751279464964569 [ go to table entry ] So, HP49(105) is 23818343988967755319547774376150791059914483440372080567294617121633\ 33843397579934524349132007906747993234281022853022720067137351051169\ 61260198088082364815545599192888318616393677802329860271430889059877\ 51279464964569 with the easy factorization: 7 * 11 * 79 * 197 * 499 * 4091 * 15121 * 64389786040953919965710874344888197677736518233910043151126969109698\ 54529140544736144679860920889446959040344022226855890207568273687210\ 41445591222744297916341457480713464115193376230466835244912640871 [ go to table entry ] Likewise, HP49(106) is 71179197499409115121643897860409539199657108743448881976777365182339\ 10043151126969109698545291405447361446798609208894469590403440222268\ 55890207568273687210414455912227442979163414574807134641151933762304\ 66835244912640871 with the partial factorization 43 * 991 * 4810307 * c210 [ go to table entry ] Nicolas and I will continue to try to factor the remaining composite. Best wishes, Paul "
After a *large* amount of work Nicolas Daminelli and I can report further progress on HP(49). Eleven months ago we reported the complete factorizations of HP49(100) through HP49(103) and the partial factorization of HP49(104) into two small primes and a 178-digit composite. We have now split that c178 with the general number field sieve; the factors are prp88 factor: 44834403720805672946171216333384339757993452434913200790674799323428\ 10228530227200671373 prp90 factor: 51051169612601980880823648155455991928883186163936778023298602714308\ 8905987751279464964569 [ go to table entry ]
So, HP49(105) is 23818343988967755319547774376150791059914483440372080567294617121633\ 33843397579934524349132007906747993234281022853022720067137351051169\ 61260198088082364815545599192888318616393677802329860271430889059877\ 51279464964569 with the easy factorization:
7 * 11 * 79 * 197 * 499 * 4091 * 15121 * 64389786040953919965710874344888197677736518233910043151126969109698\ 54529140544736144679860920889446959040344022226855890207568273687210\ 41445591222744297916341457480713464115193376230466835244912640871 [ go to table entry ]
Likewise, HP49(106) is 71179197499409115121643897860409539199657108743448881976777365182339\ 10043151126969109698545291405447361446798609208894469590403440222268\ 55890207568273687210414455912227442979163414574807134641151933762304\ 66835244912640871
with the partial factorization 43 * 991 * 4810307 * c210 [ go to table entry ]
Nicolas and I will continue to try to factor the remaining composite.
Best wishes, Paul "
go directly to table entries 104-105
David Cleaver factored HP49(106).c210 = p60 * p151. [ March 15, 2011 ] [ go to table entry ]
" Hi Patrick, I wanted to let you know that I have factored HP49(106) c210 with gmp-ecm. The parameters used to find this factorization were B1=3e9 and lucky sigma=2191726882. This split the c210 into p60*p151, with: p60 = 190452757734166693416188232333259334611734162845489390418059 p151 = 18232697103041058392848310072109296903722975431973052755627\ 465217854545763653919927047996513309176643018205699833490198368212\ 97297023820367595810298059 [ go to table entry ] This leads us to HP49(107): 439914810307190452757734166693416188232333259334611734162845489390\ 418059182326971030410583928483100721092969037229754319730527556274\ 652178545457636539199270479965133091766430182056998334901983682129\ 7297023820367595810298059 Which has a factorization of: 1753 * 390120509 * c211 I have managed to use gmp-ecm to break the HP49(107) c211 down into p32*p41*c139, with: p32 = 93072922824766566567768442402519 (B1=1e6, sigma = 4276099043 or 2869501145) p41 = 37311795374684221788102577672620935022701 (B1=43e6, sigma = 2362621067) I then used ggnfs and msieve to break the HP49(107) c139 into p48*p91, with: p48 = 776608774003332977699738989914377031406165943489 p91 = 238515217510615583066827682091457775058209547751328924950233\ 3328800859279231550379002369437 [ go to table entry ] This leads us to HP49(108): 175339012050993072922824766566567768442402519373117953746842217881\ 025776726209350227017766087740033329776997389899143770314061659434\ 892385152175106155830668276820914577750582095477513289249502333328\ 800859279231550379002369437 Which has a factorization of: 3 * 67 * 173 * 7043 * 3449252363 * 350737390831 * 50181679161380508176090501 * c170 I then used gmp-ecm to break the c170 into p33*c137, with p33 = 426702672788176702435652976517619 (B1=1e6, sigma = 343265977) I am currently working on the c137. Best Wishes, -David C. [ March 18, 2011 ] Hello Patrick, I wanted to let you know that I have factored the c137 from HP49(108) with ggnfs and msieve into p56*p82, with: p56 = 16940220143895123609020488909230648807347076448219872853 p82 = 163148117268223088893371751081490490332227703164667871910769\ 4729251345099067292373 [ go to table entry ] This brings us to HP49(109): 367173704334492523633507373908315018167916138050817609050142670267\ 278817670243565297651761916940220143895123609020488909230648807347\ 076448219872853163148117268223088893371751081490490332227703164667\ 8719107694729251345099067292373 With partial factorization: 3 * 13 * 461 * 9919193 * c218 The decimal expansion of this c218 is: 205887366265114089846147577123320653125800725081307919448400281943\ 987418697225435524701265304377790514135358007620424041194122984702\ 926363070110507466952409055377392799800423695957762440386203758986\ 71169513641669439559 Work is continuing on the c218. Thanks for your time. [ go to table entry ] -David C."
I wanted to let you know that I have factored HP49(106) c210 with gmp-ecm. The parameters used to find this factorization were B1=3e9 and lucky sigma=2191726882. This split the c210 into p60*p151, with: p60 = 190452757734166693416188232333259334611734162845489390418059 p151 = 18232697103041058392848310072109296903722975431973052755627\ 465217854545763653919927047996513309176643018205699833490198368212\ 97297023820367595810298059 [ go to table entry ]
This leads us to HP49(107): 439914810307190452757734166693416188232333259334611734162845489390\ 418059182326971030410583928483100721092969037229754319730527556274\ 652178545457636539199270479965133091766430182056998334901983682129\ 7297023820367595810298059 Which has a factorization of: 1753 * 390120509 * c211
I have managed to use gmp-ecm to break the HP49(107) c211 down into p32*p41*c139, with: p32 = 93072922824766566567768442402519 (B1=1e6, sigma = 4276099043 or 2869501145) p41 = 37311795374684221788102577672620935022701 (B1=43e6, sigma = 2362621067)
I then used ggnfs and msieve to break the HP49(107) c139 into p48*p91, with: p48 = 776608774003332977699738989914377031406165943489 p91 = 238515217510615583066827682091457775058209547751328924950233\ 3328800859279231550379002369437 [ go to table entry ]
This leads us to HP49(108): 175339012050993072922824766566567768442402519373117953746842217881\ 025776726209350227017766087740033329776997389899143770314061659434\ 892385152175106155830668276820914577750582095477513289249502333328\ 800859279231550379002369437
Which has a factorization of: 3 * 67 * 173 * 7043 * 3449252363 * 350737390831 * 50181679161380508176090501 * c170
I then used gmp-ecm to break the c170 into p33*c137, with p33 = 426702672788176702435652976517619 (B1=1e6, sigma = 343265977)
I am currently working on the c137.
Best Wishes, -David C.
[ March 18, 2011 ]
Hello Patrick,
I wanted to let you know that I have factored the c137 from HP49(108) with ggnfs and msieve into p56*p82, with: p56 = 16940220143895123609020488909230648807347076448219872853 p82 = 163148117268223088893371751081490490332227703164667871910769\ 4729251345099067292373 [ go to table entry ]
This brings us to HP49(109): 367173704334492523633507373908315018167916138050817609050142670267\ 278817670243565297651761916940220143895123609020488909230648807347\ 076448219872853163148117268223088893371751081490490332227703164667\ 8719107694729251345099067292373
With partial factorization: 3 * 13 * 461 * 9919193 * c218
The decimal expansion of this c218 is: 205887366265114089846147577123320653125800725081307919448400281943\ 987418697225435524701265304377790514135358007620424041194122984702\ 926363070110507466952409055377392799800423695957762440386203758986\ 71169513641669439559
Work is continuing on the c218. Thanks for your time. [ go to table entry ]
-David C."
go directly to table entries 106-109
David Cleaver factored HP49(109).c218 = p53 * p166. [ April 20, 2011 ] [ go to table entry ]
" Hello Patrick, I have made a little more progress on HP49. I have factored HP49(109).c218 with gmp-ecm. The parameters used to find this factorization were B1=3e9 and lucky sigma=2191180896. This broke the c218 into p53 * p166, with: p53 = 10218004525815126545868469943487168366937255818391163 p166 = 20149469081262686435623240342745108022916072191842974708192\ 355391999307609311781113754713832186190659994372136928622288341440\ 04507405010566482975467510026391893737893 [ go to table entry ] This brings us to HP49(110): 313461991919310218004525815126545868469943487168366937255818391163\ 201494690812626864356232403427451080229160721918429747081923553919\ 993076093117811137547138321861906599943721369286222883414400450740\ 5010566482975467510026391893737893 Which had an easy factorization of: 3 * 7 * 619 * 23642578733 * c218 Upon seeing another c218, I thought this would take a while, but after a little bit of work with gmp-ecm, I found a p17 and p21, which brought us to c218 = p17 * p18 * c181 p17 = 10567889515208903 p21 = 138613953787999806719 [ go to table entry ] I am continuing to work on HP49(110).c181. Its decimal expansion is: 696281547241055004524787014448111167755504896151096804844368096365\ 759227064152650920222099941253589429607814503738760057809654611250\ 7652368908194481257411644162747345175089477132247 -David C."
I have made a little more progress on HP49. I have factored HP49(109).c218 with gmp-ecm. The parameters used to find this factorization were B1=3e9 and lucky sigma=2191180896. This broke the c218 into p53 * p166, with: p53 = 10218004525815126545868469943487168366937255818391163 p166 = 20149469081262686435623240342745108022916072191842974708192\ 355391999307609311781113754713832186190659994372136928622288341440\ 04507405010566482975467510026391893737893 [ go to table entry ]
This brings us to HP49(110): 313461991919310218004525815126545868469943487168366937255818391163\ 201494690812626864356232403427451080229160721918429747081923553919\ 993076093117811137547138321861906599943721369286222883414400450740\ 5010566482975467510026391893737893
Which had an easy factorization of: 3 * 7 * 619 * 23642578733 * c218
Upon seeing another c218, I thought this would take a while, but after a little bit of work with gmp-ecm, I found a p17 and p21, which brought us to c218 = p17 * p18 * c181 p17 = 10567889515208903 p21 = 138613953787999806719 [ go to table entry ]
I am continuing to work on HP49(110).c181. Its decimal expansion is: 696281547241055004524787014448111167755504896151096804844368096365\ 759227064152650920222099941253589429607814503738760057809654611250\ 7652368908194481257411644162747345175089477132247
go directly to table entries 109-110
David Cleaver factored HP49(110).c181 = p79 * p103. [ September 03, 2012 ] [ go to table entry ]
" Hello Patrick, I have quite a few developments in the HP49 saga to report to you. I spent about six to eight months trying to factor the HP49(110).c181 via ecm. However, that never proved fruitful. Then earlier in the year I started factoring the c181 via the General Number Field Sieve using ggnfs and msieve to do the factorization. I started gathering relations on 2012/05/17 and finished gathering relations on 2012/08/11. On that day a 22M^2 matrix was built and linear algebra ran on it until 2012/08/30. 1.5 hours later, the square root step found the factors on the first dependency. The c181 split into p79 * p103, with: p79 = 13242639228855682038275386963913139191902992119830964965826611351\ 44957500774771 p103 = 5257875980823060025161989259479167407618986741511789127217197204\ 189147347509304829105884519047315609357 [ go to table entry ] From here I have started using an excellent factoring utility called yafu, which can very quickly find small factors and can even keep working until it fully factors a number. In order to factor a number, it checks for small factors, it tries the Fermat method, Pollard rho, p-1, ecm, the quadratic sieve, and it can try factoring via the number field sieve. Some of the functionality depends on external binaries, each of which are easy to find online. I typically use yafu to find small factors of these numbers, and then I will manually run gmp-ecm to try to find larger factors. *** The above factorization leads us to HP49(111), which is a c236: 37619236425787331056788951520890313861395378799980671913242639228855682\ 03827538696391313919190299211983096496582661135144957500774771525787598\ 08230600251619892594791674076189867415117891272171972041891473475093048\ 29105884519047315609357 Which had an easy factorization of: 3 * 7 * 3119 * 30168011 * 859257036259 * p212, with: p212 = 2215672318292438329341551789093919668756597710700506491362229289\ 49716840718670030689861282126551415737410604184248168739079523813765870\ 35978526994468873432733002148738098978790716880067275297057598545539637\ 098807 [ go to table entry ] *** This leads us to HP49(112), which is a c238: 37311930168011859257036259221567231829243832934155178909391966875659771\ 07005064913622292894971684071867003068986128212655141573741060418424816\ 87390795238137658703597852699446887343273300214873809897879071688006727\ 5297057598545539637098807 Which partially factored into: 131 * 2721660787 * 364148211209 * 4332696358733373457 * c196 I was able to factor HP49(112).c196 with gmp-ecm with B1=110e6 and lucky sigma=426853020. This gives us the split c196 = p46 * p151, with: p46 = 2871080232471495934021653967701541108613371057 p151 = 2310258942683190562148481349981529646166666457710725946445425378\ 87492749301442403975219925042828842113740517603022067825908798556477692\ 9828767588285591 [ go to table entry ] *** This leads us to HP49(113), which is a c241: 13127216607873641482112094332696358733373457287108023247149593402165396\ 77015411086133710572310258942683190562148481349981529646166666457710725\ 94644542537887492749301442403975219925042828842113740517603022067825908\ 7985564776929828767588285591 Which partially factored into: 3 * 13 * 23 * 521845650935569 * 868711762772471 * 319988447520300554621 * 28389161986882946018325701897 * c159 I was able to factor HP49(113).c159 with gmp-ecm with B1=110e6 and lucky sigma=1608282488. This gives us the split c159 = p46 * p113, with: p46 = 4476784590773507504219451975358661227634604289 p113 = 7937968436512120054007404759114714054246049623545813848950867773\ 8334605570121814426485117922308620342259219122429 [ go to table entry ] *** This leads us to HP49(114), which is a c244: 31323521845650935569868711762772471319988447520300554621283891619868829\ 46018325701897447678459077350750421945197535866122763460428979379684365\ 12120054007404759114714054246049623545813848950867773833460557012181442\ 6485117922308620342259219122429 Which pretty quickly factored into: 19 * 983 * 2663 * 78607 * 9934389995249 * 21656051585046364524395089 * 45811515442003960460099942651 * p164, with: p164 = 8128977805895626607033264670100486500595772941131584619352172246\ 20002330247018292473999585316046931850891592168404345391443470839102446\ 76679456195607708735639313427 [ go to table entry ] *** This leads us to HP49(115), which is a c246: 19983266378607993438999524921656051585046364524395089458115154420039604\ 60099942651812897780589562660703326467010048650059577294113158461935217\ 22462000233024701829247399958531604693185089159216840434539144347083910\ 244676679456195607708735639313427 Which pretty quickly factored into: 3 * 3 * 3 * 339257 * 256784956591 * 36693424661311252997 * 12089711795346540523800293 * p183, with: p183 = 1915138220008002714613864800803463985954766228490424773556933617\ 71517488657715528360851816690277903228983539095849848639342470604943315\ 995243199368402520964016310098028081653466011863 [ go to table entry ] *** This leads us to HP49(116), which is a c250: 33333925725678495659136693424661311252997120897117953465405238002931915\ 13822000800271461386480080346398595476622849042477355693361771517488657\ 71552836085181669027790322898353909584984863934247060494331599524319936\ 8402520964016310098028081653466011863 Which took a short while to factor into: 227 * 52386283 * 39852303700003 * 34918470225660868578167 * 71390396918591830182237959705744641 * p169, with: p169 = 2821594399022506045260907988881750768134579956275599251807250458\ 64578242838340892740600945894595344446356435593917588135425058734571590\ 0852529152005426789424094520021323 [ go to table entry ] *** This leads us to HP49(117), which is a c252: 22752386283398523037000033491847022566086857816771390396918591830182237\ 95970574464128215943990225060452609079888817507681345799562755992518072\ 50458645782428383408927406009458945953444463564355939175881354250587345\ 715900852529152005426789424094520021323 Which has the partial factorization: 3 * 23 * 99525233 * 12143755081 * 2844434001269627828783 * c210 The decimal expansion of HP49(117).c210 is: 95917046558938390327954019204739154761431263890783122604947504259838592\ 10155458387786445163000407451624133752306936169505691875284896202298903\ 67061416022719796052116843953349582116196928958606632045980053799913 [ go to table entry ] I am continuing to work on HP49(117).c210. The search continues! -David C."
I have quite a few developments in the HP49 saga to report to you. I spent about six to eight months trying to factor the HP49(110).c181 via ecm. However, that never proved fruitful. Then earlier in the year I started factoring the c181 via the General Number Field Sieve using ggnfs and msieve to do the factorization. I started gathering relations on 2012/05/17 and finished gathering relations on 2012/08/11. On that day a 22M^2 matrix was built and linear algebra ran on it until 2012/08/30. 1.5 hours later, the square root step found the factors on the first dependency. The c181 split into p79 * p103, with: p79 = 13242639228855682038275386963913139191902992119830964965826611351\ 44957500774771 p103 = 5257875980823060025161989259479167407618986741511789127217197204\ 189147347509304829105884519047315609357 [ go to table entry ]
From here I have started using an excellent factoring utility called yafu, which can very quickly find small factors and can even keep working until it fully factors a number. In order to factor a number, it checks for small factors, it tries the Fermat method, Pollard rho, p-1, ecm, the quadratic sieve, and it can try factoring via the number field sieve. Some of the functionality depends on external binaries, each of which are easy to find online. I typically use yafu to find small factors of these numbers, and then I will manually run gmp-ecm to try to find larger factors.
*** The above factorization leads us to HP49(111), which is a c236: 37619236425787331056788951520890313861395378799980671913242639228855682\ 03827538696391313919190299211983096496582661135144957500774771525787598\ 08230600251619892594791674076189867415117891272171972041891473475093048\ 29105884519047315609357
Which had an easy factorization of: 3 * 7 * 3119 * 30168011 * 859257036259 * p212, with: p212 = 2215672318292438329341551789093919668756597710700506491362229289\ 49716840718670030689861282126551415737410604184248168739079523813765870\ 35978526994468873432733002148738098978790716880067275297057598545539637\ 098807 [ go to table entry ]
*** This leads us to HP49(112), which is a c238: 37311930168011859257036259221567231829243832934155178909391966875659771\ 07005064913622292894971684071867003068986128212655141573741060418424816\ 87390795238137658703597852699446887343273300214873809897879071688006727\ 5297057598545539637098807
Which partially factored into: 131 * 2721660787 * 364148211209 * 4332696358733373457 * c196
I was able to factor HP49(112).c196 with gmp-ecm with B1=110e6 and lucky sigma=426853020. This gives us the split c196 = p46 * p151, with: p46 = 2871080232471495934021653967701541108613371057 p151 = 2310258942683190562148481349981529646166666457710725946445425378\ 87492749301442403975219925042828842113740517603022067825908798556477692\ 9828767588285591 [ go to table entry ]
*** This leads us to HP49(113), which is a c241: 13127216607873641482112094332696358733373457287108023247149593402165396\ 77015411086133710572310258942683190562148481349981529646166666457710725\ 94644542537887492749301442403975219925042828842113740517603022067825908\ 7985564776929828767588285591
Which partially factored into: 3 * 13 * 23 * 521845650935569 * 868711762772471 * 319988447520300554621 * 28389161986882946018325701897 * c159
I was able to factor HP49(113).c159 with gmp-ecm with B1=110e6 and lucky sigma=1608282488. This gives us the split c159 = p46 * p113, with: p46 = 4476784590773507504219451975358661227634604289 p113 = 7937968436512120054007404759114714054246049623545813848950867773\ 8334605570121814426485117922308620342259219122429 [ go to table entry ]
*** This leads us to HP49(114), which is a c244: 31323521845650935569868711762772471319988447520300554621283891619868829\ 46018325701897447678459077350750421945197535866122763460428979379684365\ 12120054007404759114714054246049623545813848950867773833460557012181442\ 6485117922308620342259219122429
Which pretty quickly factored into: 19 * 983 * 2663 * 78607 * 9934389995249 * 21656051585046364524395089 * 45811515442003960460099942651 * p164, with: p164 = 8128977805895626607033264670100486500595772941131584619352172246\ 20002330247018292473999585316046931850891592168404345391443470839102446\ 76679456195607708735639313427 [ go to table entry ]
*** This leads us to HP49(115), which is a c246: 19983266378607993438999524921656051585046364524395089458115154420039604\ 60099942651812897780589562660703326467010048650059577294113158461935217\ 22462000233024701829247399958531604693185089159216840434539144347083910\ 244676679456195607708735639313427
Which pretty quickly factored into: 3 * 3 * 3 * 339257 * 256784956591 * 36693424661311252997 * 12089711795346540523800293 * p183, with: p183 = 1915138220008002714613864800803463985954766228490424773556933617\ 71517488657715528360851816690277903228983539095849848639342470604943315\ 995243199368402520964016310098028081653466011863 [ go to table entry ]
*** This leads us to HP49(116), which is a c250: 33333925725678495659136693424661311252997120897117953465405238002931915\ 13822000800271461386480080346398595476622849042477355693361771517488657\ 71552836085181669027790322898353909584984863934247060494331599524319936\ 8402520964016310098028081653466011863
Which took a short while to factor into: 227 * 52386283 * 39852303700003 * 34918470225660868578167 * 71390396918591830182237959705744641 * p169, with: p169 = 2821594399022506045260907988881750768134579956275599251807250458\ 64578242838340892740600945894595344446356435593917588135425058734571590\ 0852529152005426789424094520021323 [ go to table entry ]
*** This leads us to HP49(117), which is a c252: 22752386283398523037000033491847022566086857816771390396918591830182237\ 95970574464128215943990225060452609079888817507681345799562755992518072\ 50458645782428383408927406009458945953444463564355939175881354250587345\ 715900852529152005426789424094520021323
Which has the partial factorization: 3 * 23 * 99525233 * 12143755081 * 2844434001269627828783 * c210
The decimal expansion of HP49(117).c210 is: 95917046558938390327954019204739154761431263890783122604947504259838592\ 10155458387786445163000407451624133752306936169505691875284896202298903\ 67061416022719796052116843953349582116196928958606632045980053799913 [ go to table entry ]
I am continuing to work on HP49(117).c210. The search continues!
go directly to table entries 110-117
David Cleaver factored HP49(117).c210 = p95 * p116. [ December 3, 2014 ] [ go to table entry ]
" Hello Patrick, I have some more progress to report! I have finally factored the c210 from HP49(117). I started trying to factor it via ecm with GMP-ECM from August 31, 2012, through April 1, 2013. In that time I had completed 6*t60 (= 1.2*t65). Since it looked like ecm wouldn't crack it, I decided to factor it via GNFS. I used Msieve, with gpu polynomial selection capabilities, to run polynomial selection from March 16, 2013, through July 15, 2013. I did some test sieving from July 2, 2013, through July 17, 2013, to figure out which would most likely be the best polynomial to use. The polynomial/parameters that I ended up using were: type: gnfs # norm 1.276810e-020 alpha -9.238464 e 9.932e-016 rroots 5 skew: 380780879.24 c0: -162062780465967901494709111193197313231897108452480 c1: 13812347733683567053764230784091491451134952 c2: 22102839514830809629173664060748362 c3: -520746958301071507022048503 c4: -168875771147350788 c5: 535643820 Y0: -17807540461984351122128386845862353501171 Y1: 108424014196861749931 rlim: 500000000 alim: 500000000 lpbr: 32 lpba: 33 mfbr: 64 mfba: 96 rlambda: 2.7 alambda: 3.7 I then collected relations from August 1, 2013, through May 19, 2014. It was thanks to the help of the Amazon Elastic Cloud Compute (EC2) service that I was able to finish collecting relations so quickly. I bought spot instances to keep costs down, but there were several times when spot pricing would go above my high bid and so my instances were shutdown. When I saw the prices fall again I would start up several new instances. From August through February I had 5 spot instances running. And from March through May I had 10 spot instances running. Each instance was a cc2.8xlarge instance, which was a dual Xeon E5-2670 (total of 16 cores, 32 threads) with 60.5GB ram. On each instance I ran the Amazon Linux AMI x86_64 HVM EBS OS and had 32 threads collecting relations. I wrote a simple web interface to hand out work assignments. I wrote a simple script, that ran on each instance, which got work from my web interface to keep all 32 threads busy. When a thread finished processing a chunk of work, the script would gzip the relations and send those over to my ftp server. Each thread used gnfs-lasieve4I16e and would take anywhere from 9 to 12 hours to process a chunk of work. In total, I ran 29882 instance hours x 32 threads = 956224 thread hours. I collected a total of 859026466 relations with 520615500 unique, 338410717 duplicate, and 249 bad relations. From May 20, 2014, through May 29, 2014, I tested different target densities in Msieve to make the matrix as small as possible. I was able to use a target density of 125 which got the matrix down to 71776202 x 71776379. I then ran Linear Algebra on a single 16 core machine from May 29, 2014, through October 3, 2014, using 13 threads (because more could actually slow the job down). At the end of that, 3052 hours, it had recovered 26 non-trivial dependencies. I then started running the Square-Root step, which took about 10.5 hours per dependency, and the factorization was found on the 2nd dependency on October 4th, 2014! So now, after 765 days (or 2 years, 1 month, and 5 days) of work, with 568 days (or 1 year, 6 months, 19 days) of that spent on GNFS on the c210, we find that HP49(117) has the full factorization: 3 * 23 * 99525233 * 12143755081 * 2844434001269627828783 * p95 * p116 p95 = 579991850255395814930902290226590574070465619261577712182337361547894\ 69010389546134055763746997 p116 = 16537654195779115452085989138575434836851289636159339542929128160183\ 686876788663786928798769682882741367314660621029 *** This leads us to HP49(118), which is a c255: 323995252331214375508128444340012696278287835799918502553958149309022902265\ 905740704656192615777121823373615478946901038954613405576374699716537654195\ 779115452085989138575434836851289636159339542929128160183686876788663786928\ 798769682882741367314660621029 Which had the partial factorization: 31 * 59 * 1559 * 89626966666659827 * c232 The c232 was factored by GMP-ECM after about 60 hours with the lucky parameters: Using B1=43000000, B2=240490660426, sigma=1:1648399426 c232 = p47 * p185 p47 = 13239299873681306480869143752057086094694552407 p185 = 95758009093092999931626631706893838237446804628957426949545161439643\ 850763983152977771070456646529606514514350669236880120878528179383004060084\ 979184123521819930400481691041161410407051 *** This leads us to HP49(119), which is a c257: 315915598962696666665982713239299873681306480869143752057086094694552407957\ 580090930929999316266317068938382374468046289574269495451614396438507639831\ 529777710704566465296065145143506692368801208785281793830040600849791841235\ 21819930400481691041161410407051 Which has the partial factorization: 73 * 16249 * c251 The decimal expansion of HP49(119).c251 is: 266330909267922634367369046305315204797687428494350971277546348221683954382\ 507914865091802754788127799593469081315896606977094898528309347119787046816\ 393993232632706978213255816917295388773177366265980367036319706797376648877\ 20652086830617767029002763 I have been trying to factor this c251 with GMP-ECM since October 8th. So far, I have run around 2*t60 with no luck. If this number ends up not having a factor with less than, maybe, 80 digits, then HP49 may be stuck here at step 119 for quite a long time. It will take a LOT of effort to factor a c251 via GNFS. Here's hoping for a lucky ecm curve or a dedicated effort to push this number further! The search continues! -David C."
I have some more progress to report! I have finally factored the c210 from HP49(117). I started trying to factor it via ecm with GMP-ECM from August 31, 2012, through April 1, 2013. In that time I had completed 6*t60 (= 1.2*t65). Since it looked like ecm wouldn't crack it, I decided to factor it via GNFS. I used Msieve, with gpu polynomial selection capabilities, to run polynomial selection from March 16, 2013, through July 15, 2013. I did some test sieving from July 2, 2013, through July 17, 2013, to figure out which would most likely be the best polynomial to use. The polynomial/parameters that I ended up using were: type: gnfs # norm 1.276810e-020 alpha -9.238464 e 9.932e-016 rroots 5 skew: 380780879.24 c0: -162062780465967901494709111193197313231897108452480 c1: 13812347733683567053764230784091491451134952 c2: 22102839514830809629173664060748362 c3: -520746958301071507022048503 c4: -168875771147350788 c5: 535643820 Y0: -17807540461984351122128386845862353501171 Y1: 108424014196861749931 rlim: 500000000 alim: 500000000 lpbr: 32 lpba: 33 mfbr: 64 mfba: 96 rlambda: 2.7 alambda: 3.7
I then collected relations from August 1, 2013, through May 19, 2014. It was thanks to the help of the Amazon Elastic Cloud Compute (EC2) service that I was able to finish collecting relations so quickly. I bought spot instances to keep costs down, but there were several times when spot pricing would go above my high bid and so my instances were shutdown. When I saw the prices fall again I would start up several new instances. From August through February I had 5 spot instances running. And from March through May I had 10 spot instances running. Each instance was a cc2.8xlarge instance, which was a dual Xeon E5-2670 (total of 16 cores, 32 threads) with 60.5GB ram. On each instance I ran the Amazon Linux AMI x86_64 HVM EBS OS and had 32 threads collecting relations. I wrote a simple web interface to hand out work assignments. I wrote a simple script, that ran on each instance, which got work from my web interface to keep all 32 threads busy. When a thread finished processing a chunk of work, the script would gzip the relations and send those over to my ftp server. Each thread used gnfs-lasieve4I16e and would take anywhere from 9 to 12 hours to process a chunk of work. In total, I ran 29882 instance hours x 32 threads = 956224 thread hours. I collected a total of 859026466 relations with 520615500 unique, 338410717 duplicate, and 249 bad relations. From May 20, 2014, through May 29, 2014, I tested different target densities in Msieve to make the matrix as small as possible. I was able to use a target density of 125 which got the matrix down to 71776202 x 71776379. I then ran Linear Algebra on a single 16 core machine from May 29, 2014, through October 3, 2014, using 13 threads (because more could actually slow the job down). At the end of that, 3052 hours, it had recovered 26 non-trivial dependencies. I then started running the Square-Root step, which took about 10.5 hours per dependency, and the factorization was found on the 2nd dependency on October 4th, 2014!
So now, after 765 days (or 2 years, 1 month, and 5 days) of work, with 568 days (or 1 year, 6 months, 19 days) of that spent on GNFS on the c210, we find that HP49(117) has the full factorization: 3 * 23 * 99525233 * 12143755081 * 2844434001269627828783 * p95 * p116
p95 = 579991850255395814930902290226590574070465619261577712182337361547894\ 69010389546134055763746997 p116 = 16537654195779115452085989138575434836851289636159339542929128160183\ 686876788663786928798769682882741367314660621029
*** This leads us to HP49(118), which is a c255: 323995252331214375508128444340012696278287835799918502553958149309022902265\ 905740704656192615777121823373615478946901038954613405576374699716537654195\ 779115452085989138575434836851289636159339542929128160183686876788663786928\ 798769682882741367314660621029
Which had the partial factorization: 31 * 59 * 1559 * 89626966666659827 * c232
The c232 was factored by GMP-ECM after about 60 hours with the lucky parameters: Using B1=43000000, B2=240490660426, sigma=1:1648399426 c232 = p47 * p185 p47 = 13239299873681306480869143752057086094694552407 p185 = 95758009093092999931626631706893838237446804628957426949545161439643\ 850763983152977771070456646529606514514350669236880120878528179383004060084\ 979184123521819930400481691041161410407051
*** This leads us to HP49(119), which is a c257: 315915598962696666665982713239299873681306480869143752057086094694552407957\ 580090930929999316266317068938382374468046289574269495451614396438507639831\ 529777710704566465296065145143506692368801208785281793830040600849791841235\ 21819930400481691041161410407051
Which has the partial factorization: 73 * 16249 * c251
The decimal expansion of HP49(119).c251 is: 266330909267922634367369046305315204797687428494350971277546348221683954382\ 507914865091802754788127799593469081315896606977094898528309347119787046816\ 393993232632706978213255816917295388773177366265980367036319706797376648877\ 20652086830617767029002763
I have been trying to factor this c251 with GMP-ECM since October 8th. So far, I have run around 2*t60 with no luck. If this number ends up not having a factor with less than, maybe, 80 digits, then HP49 may be stuck here at step 119 for quite a long time. It will take a LOT of effort to factor a c251 via GNFS. Here's hoping for a lucky ecm curve or a dedicated effort to push this number further! The search continues!
go directly to table entries 117-119
No homeprime reached after 118 steps !!
I'm grateful for the work of Warut Roonguthai (email) for the expansion of number HP( 49 ) upto step 55. For the moment it seems this is becoming a similar unending case as the famous 196-reversal palindromic phenomenon. - go to topic
Dave Rusin (email) tried with the means at his disposal to factor the number c105 of HP( 49 ) at step 56. Here's why his program had to give up : the program he used has three phases :
Major progress came from Paul Leyland (email) who found the two prime factors p41 and p65 of HP( 49 ) at step 56 in a timespan of only one week (compare this with Dave Rusin estimate of 13 years!) using his MPQS program. - go to topic A new breakthrough came when he cracked the c137 of step 74 of HP( 49 ) into p46 * p91 after six months of computation using ECM. - go to topic
Click here to view some of the author's [P. De Geest] entries to the table. Click here to view some entries to the table about palindromes.
Jeffrey Heleen (email) started working already on this topic problem many years ago and even explored the topic up to the number 1000. - go to topic
Eric W. Weisstein maintains also an interesting 'Math Encyclopedia' page about this topic under the heading Home Prime.
Prime Curios! - site maintained by G. L. Honaker Jr. and Chris Caldwell
[ TOP OF PAGE]