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 !

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. :) ..."

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

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.

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 and
3350 curves at B1=11M.

The two factors are respectively
3804796914905629947782783176497447433056300673
and
297575514989250201776144220639738150129498705/
0078840501836673559420025718611870754546792073 "

go directly to table entry

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 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 you
know if we find more factors."

Alex and Paul, that is top level programming, congratulations!

go directly to table entry

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 the
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) is composite, with three small prime factors, one of moderate size (all found
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"

Alex and Paul, you both are quite a math-fertile team. Well done again!

go directly to table entry

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 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)

Paul Leyland (email)'s reply

Richard Brent (email)'s reply

Paul Zimmermann (email)'s reply

go directly to table entry

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."

go directly to table entry

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."

Paul Zimmermann (email)'s reply

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 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. "

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 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 "

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

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 :

• 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.

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

Neil Sloane's "Integer Sequences" Encyclopedia can be consulted online : Neil Sloane's Integer Sequences The list has been poured into sequences by Neil Sloane, Jeff Burch and Michael Greenwald : A006919 Write down all the prime divisors in previous term!. A037271 Number of steps to reach a prime under: "replace n by concatenation of its prime factors", when applied to nth composite number, or -1 if no such number. A037272 Primes reached in A037271, or -1 if no such prime. A037273 Number of steps to reach a prime under: "replace n by concatenation of its prime factors", or -1 if no such number. A037274 Home primes: for n >= 2, primes reached when you start with n, concatenate its prime factors (A037276), and repeat until a prime is reached (or -1 if no prime is ever reached). A037275 Subsequence of record holders in A037274. A037276 Replace n by concatenation of its prime factors. A037919 up to A037941 Trajectory of 4 (up to 48) under prime factor concatenation procedure. A056938 Trajectory of 49. A064841 Working in base 2, replace n by concatenation of its prime divisors in increasing order. A065016 Working in base 2, replace n by the concatenation of its prime factors (without repetition). A048985 Working in base 2, replace n by concatenation of its prime divisors in increasing order (write answer in base 10). A064795 Home primes in base 2: primes reached when you start with n, and (working in base 2) concatenate its prime factors (A048985); repeat until a prime is reached (or -1 if no prime is ever reached). A048986 Home primes in base 2: primes reached when you start with n, and (working 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.] A049065 Record primes reached in A048986. 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]

(All rights reserved) - Last modified : February 7, 2013.

---

Patrick De Geest - Belgium - Short Bio - Some Pictures
E-mail address : pdg@worldofnumbers.com

---

---