| World!Of Numbers | |||
Introduction
This page presents a list of "the repeated factorization 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.
Messages
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 problemThank you very much, Jeffrey, for sharing you work with us. I welcome your list of numbers
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,984and 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. :) ..."
not having reached the endprime smaller than 1000 very much. It will provide new
'impetus' for like-minded persons to go further in exploring the subject. As 'palindromes' is
the main topic of my website I took the liberty to highlight the five palindromes in your list.
These became my favorites and would like to give them priority over the nonpalindromic
ones for numbercrunchers who are interested enough to accept the challenge.
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 Factorization of Concatenated Primefactors of the Composite Numbers)
The factors are p41 * p65, orWell done, both of you !
21034137982005155236145561292210835084361
and
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.
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 thatMy compliments to you, Paul !
this number factors as p46 * p91. It was found after ~ 5000 curves at B1=3M and
3350 curves at B1=11M.
The two factors are respectively
3804796914905629947782783176497447433056300673
and
297575514989250201776144220639738150129498705/
0078840501836673559420025718611870754546792073 "
On [ August 6, 2000 ] Igor Schein (email) sent me some results of his investigation
of 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."
On [ November 25, 2000 ] Sander Hoogendoorn (email) informed me he started collecting
these 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 wouldAlex and Paul, that is top level programming, congratulations!
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 you
know if we find more factors."
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 theAlex and Paul, you both are quite a math-fertile team. Well done again!
previous c138 and took a closely similar amount of processing power so I won't repeat
all the details I gave last time. On this occasion, Alex found the polynomial and performed
about 95% of the sieving. I did the filtering, linear algebra and square root phases. For
some reason, this factorization caused us many more problems than the previous one
and several bugs or inadequacies in our software came to light. One such problem forced us
to do the linear algebra twice, on two slightly different matrixes, and delayed our finding
the factors by several days.
Alex would like to thank the Research Unit for System Architecture of the Department
of Computer Sciences at the Technische Universität München for the use of their computers
in the sieving phase. I used two servers at Microsoft Research Ltd, Cambridge for my small
contribution to the sieving and for the square root phase; the linear algebra was performed
on the 32-cpu cluster at MSR Cambridge.
HP49(82)
by Alex) and a composite co-factor which will be much easier to factor than its two
predecessors. The current factorization is p1 * p3 * p9 * p30 * c118. We will be working
on the c118 in the near future. Regards, Paul & Alex"
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."
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 84th
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>
(seeLarge 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 29th 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."
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 100th 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 98th and 99th 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 100th 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 100th 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 "
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 https://maths-people.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
factorization 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."
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."
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."
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."
go directly to table entries 117-119
Tom Dean tackles HP49(119). [ March 19, 2022 ]
[ go to table info ]
" I started working on homeprime 49, step 119.Tom Dean reports on his effort to factorize HP49(119). [ April 1, 2022 ]
I confirmed the small primes in the factorization as 73 and 16249,
with a GMP-based brute force multi-processing prime factorization up to 10^15.
I started factorization of the remaining c251 using cado-nfs on Feb 13, 2022.
Est(imated) completion March 31, 2022.
I am using an AMD 3970X with 64G RAM.
I will update you when it completes.
Tom Dean "
[ go to table info ]
" Unfortunately, cado-nfs.py failed after six weeks.
From a cado maintainer:
Bear in mind that the current factoring record is a 250-digit number,
and that required 2700 core-years. Or, in another unit, 85 years on a
32-core machine. It _is_ parallelizable, but if you want to get the
calendar time below several months, you have to use a fairly big number
of machines, and you're bound to encounter a few dragons.
I tried rebuilding cado-nfs, but, could not get it to recognize configuration
parameters.
I note that a c251 is being attempted at nfs@home.
I will try to find out what that is and maybe join the project.
Tom Dean "
go directly to table entry 119
The Table
|
4 2 * 2 2 * 11 Homeprime 211 reached after 2 steps ( Sloane's A037919 ) 6 2 * 3 Homeprime 23 reached after 1 step 8 2 * 2 * 2 2 * 3 * 37 3 * 19 * 41 3 * 3 * 3 * 7 * 13 * 13 3 * 11123771 7 * 149 * 317 * 941 229 * 31219729 11 * 2084656339 3 * 347 * 911 * 118189 11 * 613 * 496501723 97 * 130517 * 917327 53 * 1832651281459 3 * 3 * 3 * 11 * 139 * 653 * 3863 * 5107 Homeprime 3331113965338635107 reached after 13 steps ( Featured in Prime Curios! 3331113965338635107 ) ( Sloane's A006919 and A037920 ) 9 3 * 3 3 * 11 Homeprime 311 reached after 2 steps ( Sloane's A037921 ) 10 2 * 5 5 * 5 5 * 11 7 * 73 Homeprime 773 reached after 4 steps ( Sloane's A037922 ) 12 2 * 2 * 3 Homeprime 223 reached after 1 step 14 2 * 7 3 * 3 * 3 3 * 3 * 37 47 * 71 13 * 367 Homeprime 13367 reached after 5 steps ( Sloane's A037923 ) 15 3 * 5 5 * 7 3 * 19 11 * 29 Homeprime 1129 reached after 4 steps ( Sloane's A037924 ) 16 2 * 2 * 2 * 2 2 * 11 * 101 3 * 11 * 6397 3 * 163 * 6373 Homeprime 31636373 reached after 4 steps ( Sloane's A037925 ) 18 2 * 3 * 3 Homeprime 233 reached after 1 step 20 2 * 2 * 5 3 * 3 * 5 * 5 5 * 11 * 61 11 * 4651 3 * 3 * 12739 17 * 194867 19 * 41 * 22073 709 * 273797 3 * 97 * 137 * 17791 11 * 3610337981 7 * 3391 * 4786213 3 * 3 * 3 * 3 * 7 * 23 * 31 * 1815403 13 * 17 * 23 * 655857429041 7 * 7 * 2688237874641409 3 * 31 * 8308475676071413 Homeprime 3318308475676071413 reached after 15 steps ( Sloane's A037926 ) 21 3 * 7 Homeprime 37 reached after 1 step 22 2 * 11 Homeprime 211 reached after 1 step 24 2 * 2 * 2 * 3 3 * 3 * 13 * 19 Homeprime 331319 reached after 2 steps ( Sloane's A037927 ) 25 5 * 5 5 * 11 7 * 73 Homeprime 773 reached after 3 steps ( Sloane's A037928 ) 26 2 * 13 3 * 71 7 * 53 3 * 251 Homeprime 3251 reached after 4 steps ( Sloane's A037929 ) 27 3 * 3 * 3 3 * 3 * 37 47 * 71 13 * 367 Homeprime 13367 reached after 4 steps ( Sloane's A037930 ) 28 2 * 2 * 7 Homeprime 227 reached after 1 step 30 2 * 3 * 5 5 * 47 Homeprime 547 reached after 2 steps ( Sloane's A037931 ) 32 2 * 2 * 2 * 2 * 2 2 * 41 * 271 Homeprime 241271 reached after 2 steps ( Sloane's A037932 ) 33 3 * 11 Homeprime 311 reached after 1 step 34 2 * 17 7 * 31 17 * 43 3 * 7 * 83 3 * 13 * 97 Homeprime 31397 reached after 5 steps ( Sloane's A037933 ) 35 5 * 7 3 * 19 11 * 29 Homeprime 1129 reached after 3 steps ( Sloane's A037934 ) 36 2 * 2 * 3 * 3 7 * 11 * 29 Homeprime 71129 reached after 2 steps ( Sloane's A037935 ) 38 2 * 19 3 * 73 PALINDROMIC homeprime 373 reached after 2 steps ( Sloane's A037936 ) 39 3 * 13 PALINDROMIC homeprime 313 reached after 1 step 40 2 * 2 * 2 *5 5 * 5 * 89 3 * 3 * 3 * 3 * 3 * 23 7 * 7 * 59 * 1153 29 * 2675557 3 * 31 * 3147049 809 * 1019 * 4019 3 * 53639 * 502807 3 * 31 * 41 * 92745739 Homeprime 3314192745739 reached after 9 steps ( Sloane's A037937 ) 42 2 * 3 * 7 3 * 79 Homeprime 379 reached after 2 steps ( Sloane's A037938 ) 44 2 * 2 * 11 3 * 11 * 67 3 * 3 * 3463 13 * 113 * 227 173 * 229 * 331 11 * 15748121 541 * 2062381 11 * 607 * 810553 2281 * 5088913 Homeprime 22815088913 reached after 9 steps ( Sloane's A037939 ) 45 3 * 3 * 5 5 * 67 3 * 3 * 3 * 3 * 7 17 * 37 * 53 239 * 727 3 * 41 * 1949 Homeprime 3411949 reached after 6 steps ( Sloane's A037940 ) 46 2 * 23 Homeprime 223 reached after 1 step 48 2 * 2 * 2 * 2 * 3 71 * 313 3 * 11 * 2161 3 * 13 * 199 * 401 19 * 43 * 109 * 3517 11 * 17 * 109 * 877 * 1087 23 * 1481 * 7039 * 46591 3 * 3 * 7 * 53 * 67 * 1034726207 3 * 11251223678242069 23 * 4583 * 2952795526741 359 * 5782291 * 1130063089 835996339 * 43011938251 31 * 49123 * 54898161457127 467 * 79367 * 8496358995643 61 * 61 * 79 * 1591356884791277 Homeprime 6161791591356884791277 reached after 15 steps ( Sloane's A037941 ) 49
No homeprime reached after 118 steps !! 50 2 * 5 * 5 3 * 5 * 17 Homeprime 3517 reached after 2 steps 51 3 * 17 Homeprime 317 reached after 1 step 52 2 * 2 * 13 Homeprime 2213 reached after 1 step 54 2 * 3 * 3 * 3 Homeprime 2333 reached after 1 step 55 5 * 11 7 * 73 Homeprime 773 reached after 2 steps 56 2 * 2 * 2 * 7 17 * 131 37 * 463 Homeprime 37463 reached after 3 steps 57 3 * 19 11 * 29 Homeprime 1129 reached after 2 steps 58 2 * 29 Homeprime 229 reached after 1 step 60 2 * 2 * 3 * 5 3 * 5 * 149 Homeprime 35149 reached after 2 steps 62 2 * 31 3 * 7 * 11 3 * 1237 Homeprime 31237 reached after 3 steps 63 3 * 3 * 7 Homeprime 337 reached after 1 step 64 2 * 2 * 2 * 2 * 2 * 2 2 * 3 * 7 * 11 * 13 * 37 29 * 101 * 80953 853 * 3411701 3 * 181 * 367 * 42821 127 * 2505013723 Homeprime 1272505013723 reached after 6 steps 65 5 * 13 3 * 3 * 3 * 19 11 * 13 * 233 11 * 101203 3 * 3 * 23 * 53629 3 * 3 * 1523 * 24247 3 * 3 * 3 * 7 * 47 * 3732109 11 * 18013 * 16843763 151 * 740406071813 3 * 13 * 13 * 54833 * 5458223 3 * 3 * 97 * 179 * 373 * 7523 * 71411 1571 * 1601 * 1350675311441 3 * 3 * 13 * 33391 * 143947 * 279384649 11 * 23 * 204069263 * 6417517893491 7 * 11 * 1756639 * 83039633268945697 29 * 29 * 5165653 * 13503983 * 12122544283 228345060379 * 1282934064985326977 3 * 3 * 3 * 2979253 * 3030445387 * 9367290955541 1381 * 3211183211 * 75157763339900357651 Homeprime 1381321118321175157763339900357651 reached after 19 steps 66 2 * 3 * 11 Homeprime 2311 reached after 1 step 68 2 * 2 * 17 3 * 739 Homeprime 3739 reached after 2 steps 69 3 * 23 17 * 19 3 * 3 * 191 Homeprime 33191 reached after 3 steps 70 2 * 5 * 7 Homeprime 257 reached after 1 step 72 2 * 2 * 2 * 3 * 3 3 * 7411 11 * 19 * 179 Homeprime 1119179 reached after 3 steps 74 2 * 37 3 * 79 Homeprime 379 reached after 2 steps 75 3 * 5 * 5 5 * 71 Homeprime 571 reached after 2 steps 76 2 * 2 * 19 7 * 317 3 * 3 * 3 * 271 Homeprime 333271 reached after 3 steps 77 See expansion of number 49 from step 2 onwards No homeprime reached after 117 steps !! 78 2 * 3 * 13 3 * 3 * 257 7 * 4751 3 * 24917 101 * 3217 3 * 17 * 19867 3 * 89 * 118801 3 * 129706267 Homeprime 3129706267 reached after 8 steps 80 2 * 2 * 2 * 2 * 5 5 * 5 * 7 * 127 3 * 3 * 103 * 601 23 * 1439287 3 * 43 * 53 * 33851 31 * 521 * 212701 11 * 29 * 83 * 1190513 24917 * 45343789 3 * 13 * 17 * 3758288603 47 * 109 * 211 * 289720051 521 * 90420751035931 3 * 7 * 13 * 28927 * 6608832661 13 * 293 * 974872480075829 11 * 131 * 4259 * 1290683 * 1678277 19 * 75253 * 45682591 * 170420821 3541 * 55782362519794174081 47 * 94253 * 1769473 * 45181157867 13 * 35801984243 * 10300789571213 24144697 * 1012307071 * 5465225099 7 * 344924244303295816495032157 25084266359 * 292810008440530123 3 * 103 * 187547 * 449917889 * 962054203309 3 * 17 * 1031 * 59017279006673853482475689 3 * 4091 * 84942079 * 1022090777 * 297603119071 3 * 7 * 10457 * 12329 * 16693 * 50392193 * 14969202179383 3 * 30259 * 71055159937 * 57524912931153279285967 3 * 89 * 13961402129 * 885962415125636289188463869 3 * 293 * 41233 * 11038436757548471 * 97266672953292277 3 * 7 * 11 * 1853767605161 * 7690929649893487130760222347 2887 * 128548159915501079906799324521471122535581 31 * 3169 * 1387271471 * 452100449741 * 46858220729781791489 Homeprime 313169138727147145210044974146858220729781791489 reached after 31 steps 81 3 * 3 * 3 * 3 3 * 11 * 101 7 * 7 * 7 *907 13 * 13 * 4603 3 * 4378201 11 * 13 * 19 * 12653 3 * 29 * 443 * 288833 3 * 61 * 83 * 21689597 19 * 3089 * 4597 * 13411 Homeprime 193089459713411 reached after 9 steps 82 2 * 41 Homeprime 241 reached after 1 step 84 2 * 2 * 3 * 7 Homeprime 2237 reached after 1 step 85 5 * 17 11 * 47 31 * 37 Homeprime 3137 reached after 3 steps 86 2 * 43 3 * 3 * 3 * 3 * 3 3 * 41 * 271 3 * 3 * 7 * 5417 3 * 1125139 47 * 607 * 1091 1453 * 327647 3 * 31 * 137 * 114067 23 * 14397265829 11 * 17 * 89 * 113 * 1230631 3 * 79 * 379 * 43721 * 284657 3 * 10457 * 1209331666867 3 * 13 * 73 * 283 * 3853254754967 7 * 7583 * 15642293 * 377850899 7 * 43 * 983 * 55228357 * 474772229 73 * 1019155551073390065373 601 * 290328047 * 4189529884459 Homeprime 6012903280474189529884459 reached after 17 steps 87 3 * 29 7 * 47 3 * 3 * 83 17 * 199 3 * 3 * 3 * 7 * 7 * 13 3 * 3 * 3 * 123619 17 * 19595507 7 * 14771 * 16631 37 * 1931813963 3 * 3 * 3 * 71 * 3779 * 51341 3 * 73 * 277 * 569 * 966803 3 * 3 * 31 * 89 * 15032724013 7 * 11 * 37 * 79 * 137 * 30853 * 35023 3 * 31 * 196838267 * 3886045633 4909 * 674672720039496037 73821863 * 66507054593299 3 * 3 * 17 * 1069 * 75833 * 595192748879 41 * 43 * 1881512748629379008933 Homeprime 41431881512748629379008933 reached after 18 steps 88 2 * 2 * 2 * 11 7 * 19 * 167 Homeprime 719167 reached after 2 steps 90 2 * 3 * 3 * 5 5 * 467 7 * 11 * 71 Homeprime 71171 reached after 3 steps 91 7 * 13 23 * 31 3 * 3 * 7 * 37 11 * 3067 3 * 3 * 17 * 739 3 * 1105913 23 * 61 * 22171 Homeprime 236122171 reached after 7 steps 92 2 * 2 * 23 3 * 3 * 13 * 19 Homeprime 331319 reached after 2 steps 93 3 * 31 Homeprime 331 reached after 1 step 94 2 * 47 13 * 19 Homeprime 1319 reached after 2 steps 95 5 * 19 3 * 173 19 * 167 3 * 6389 Homeprime 36389 reached after 4 steps 96 2 * 2 * 2 * 2 * 2 * 3 61 * 3643 19 * 32297 3 * 61 * 10559 3 * 12036853 17 * 43 * 426863 107 * 16293709 3 * 3 * 3 * 11 * 241 * 149717 1613 * 20651730409 3 * 23 * 2337980459861 7 * 13 * 103 * 211 * 1634389987 7 * 76771 * 13269579308471 7 * 3041 * 3649039943138033 73 * 607 * 24527 * 258733 * 2597533 3 * 11 * 31 * 71952341419928966371 59 * 52765626310871524219769 107 * 229 * 1349807 * 179981492001889 3 * 149 * 7267433 * 330083824660722439 9767 * 394909447 * 8166090096149911 6917 * 1463621591 * 9647886019564813 7 * 6091 * 16223342078849817010718849 1279 * 5949269916608349374368264831 37 * 739 * 467978980723278658134600017 7 * 19 * 19 * 47 * 6758847359447 * 47013224061319 7 * 227 * 1237 * 51179327 * 67321039 * 1061958490511 3 * 1437251 * 72118441 * 23241560648369540947007 13789 * 230597 * 88003588750669 * 1123460390190091 17 * 29 * 29 * 67 * 109 * 797 * 22263569 * 4660829203 * 1596899264419 Homeprime 172929671097972226356946608292031596899264419 reached after 28 steps ! 98 2 * 7 * 7 Homeprime 277 reached after 1 step 99 3 * 3 * 11 7 * 11 * 43 Homeprime 71143 reached after 2 steps 100 2 * 2 * 5 * 5 5 * 11 * 41 3 * 17047 Homeprime 317047 reached after 3 steps For the Home Primes greater than 100 please refer to |
Contributions and sources
I'm grateful for the work of Warut Roonguthai (email) for the expansion of number HP( 49 ) up to 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 :
- trial division checked for all small factors (up to around 10^6).
- The elliptic curve method is probabilistic, but it has a very high likelihood of finding any small factors, and decreasing
likelihood of finding larger ones. That program ran over 1200 times, which should have made it more likely than not that
it would find any prime factor of up to 30 digits. This morning [ June 15, 1997 ] it stopped without finding any. - the quadratic sieve method will eventually factor the number completely, but requires a huge amount of partial data.
This morning, as it entered this phase, the computer gave the following message : - number to factor [105 digits] :
- 4349837300068295069063245879245079069305
- 7918835011730882390173172445242099505108
- 7537386538239252454821397
- estimated running time (usr-time) :
- 12 years 266 days 22 hours 40.9741 minutes.
It seems that we'll have to wait for more powerful computers and/or factorizing programs.
This uncracked number c105 WAS a good 'testing case' thereto... read on !
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
|
its prime factors", when applied to nth composite number, or -1 if no such number. its prime factors", or -1 if no such number. its prime factors (A037276), and repeat until a prime is reached (or -1 if no prime is ever reached). in increasing order. (without repetition). in increasing order (write answer in base 10). in base 2) concatenate its prime factors (A048985); repeat until a prime is reached (or -1 if no prime is ever reached). in base 2) concatenate its prime factors (A048985); repeat until a prime is reached (or -1 if no prime is ever reached). [Answer is written in base 10.] Click here to view some of the author's [P. De Geest] entries to the table. |
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
Lists of Homeprime numbers without endprimes.
Repeated Factorization of Concatenated Primefactors of the Composite Numbers up to 100 and beyond...
[ TOP OF PAGE]
Patrick De Geest - Belgium
E-mail address : pdg@worldofnumbers.com