## Factorization of 10 consecutive integers > 10^500

Expand Messages
• Let x=13860*(10^60+1898683) N=x^2*(x^2-23)*(x^2-41)*(x^2-64)/55440-4 then N+k is factorized for k in [0,9]. Proof:
Message 1 of 8 , Aug 11, 2007
Let

x=13860*(10^60+1898683)
N=x^2*(x^2-23)*(x^2-41)*(x^2-64)/55440-4

then N+k is factorized for k in [0,9].

Proof:

Software used:
GGNFS
GMP-ECM
Msieve
OpenPFGW
Pari-GP
Primo

Neighbouring composites:
c470=(N-1)/(5^2*41*23689760674499*20201699120271441240691)
c449=(N+10)/(2*3*23*449*304781745193811\
*47370240325563932561*432893534978100829771)

11 August 2007
• ... Wow! Big congratulations on an astonishing record. ... After 5 days of the page, there are already more numbers above the 500-digit limit than I expected
Message 2 of 8 , Aug 11, 2007
> x=13860*(10^60+1898683)
> N=x^2*(x^2-23)*(x^2-41)*(x^2-64)/55440-4
>
> then N+k is factorized for k in [0,9].

Wow!
Big congratulations on an astonishing record.
Earlier I wrote:
> I maintain many prime record pages manually and want a limit
> that is unlikely to give many large submissions within a few years.

After 5 days of the page, there are already more numbers
above the 500-digit limit than I expected to see for years.
http://hjem.get2net.dk/jka/math/consecutive_factorizations.htm is updated.

--
Jens Kruse Andersen
• ... I was also astounded. I had been doing some p25 work on a sample of 1158 (potential) factorizations of 5 consecutive integers at 500 digits, based on PFGW
Message 3 of 8 , Aug 11, 2007
--- In primeform@yahoogroups.com, "Jens Kruse Andersen"
<jens.k.a@...> wrote:

> Big congratulations on an astonishing record.

I was also astounded. I had been doing some p25 work on a
sample of 1158 (potential) factorizations of 5 consecutive
integers at 500 digits, based on PFGW doublets, obtained by
running with the switches -f5000 -d for the two inner
members of Jarek's (essentially unique?) quartic
construction.

I estimated the Poisson mean, mu(k), for k>8 successive
factorizations, as

mu(k)=(40/25)^2*1158*(k-4)*(25*exp(Euler)/500)^(k-5)

where the first factor signified a willingness to step up to
p40 work if 2 out of k>8 slots had not yet cracked. This
heuristic gave mu(9)=0.93, which suggested that k=9 was
worth trying, without increasing the size of the PFGW
sample. (GMP-ECM is preferable to PFGW, on AMD64s running
linux.)

In the event, my second case with k=8 immediately gave
k=10, with no need for p40, thanks to /two/ flukes

N+0 = 2^2*97*p506
N+1 = 3*19*443*p504

at the lowly p7 level that Pari-GP was using to monitor
possible extensions of sequences, before handing over to
/serious/ GMP-ECM work.

At this point I strongly suspected that there was a
programming bug, since the chance of two free lunches at
p7 level was merely

(7*exp(Euler)/500)^2 = 0.06%

But it was a case of fortune favouring the brave: morally,
I deserved a result at k=9, eventually; happily, I got a
result at k=10, much faster than I expected to crack k=9.

Then there was the residual matter of factorizing 8
algebraic cofactors with 128 digits. (Jens says that this is
"relatively easy", but I do not know how many c128's he has
cracked with MPQS or GNFS. My score is precisely 0, with one
notable disaster trying to parallelize GGNFS on a c124.)

In the event, I did not need Sean Irvines's help: the
hardest factorization in a 128-digit cofactor was merely

c118 = ((13860*(10^60+1898683))^2/8-1)/9106676377 = p45*p73

with

p45 = 612167007455266691724205830229887098156127313

found by Chris Monico's GGNFS, which allows for parallel
sieving and seems reasonably stable below 120 digits.

That factorization took half a day:

> Total sieving time: 61.39 hours. [Shared by 10 processors]
> Total relation processing time: 0.36 hours.
> Matrix solve time: 3.92 hours.
> Time per square root: 0.34 hours.

and was achieved just before the moors become dangerous:

http://en.wikipedia.org/wiki/Glorious_Twelfth

David
• ... I know the feeling of finding more than was searched. It s nice! ... Well, I didn t say what it was relative to ;-) But I have changed relatively easy to
Message 4 of 8 , Aug 12, 2007
> But it was a case of fortune favouring the brave: morally,
> I deserved a result at k=9, eventually; happily, I got a
> result at k=10, much faster than I expected to crack k=9.

I know the feeling of finding more than was searched. It's nice!

> Then there was the residual matter of factorizing 8
> algebraic cofactors with 128 digits. (Jens says that this is
> "relatively easy", but I do not know how many c128's he has
> cracked with MPQS or GNFS. My score is precisely 0, with one
> notable disaster trying to parallelize GGNFS on a c124.)

Well, I didn't say what it was relative to ;-)
But I have changed "relatively easy" to "possible" on the record page.

--
Jens Kruse Andersen
• Posted by: Jens Kruse Andersen jens.k.a@get2net.dk jkand71 ... Wait a sec. You re constructing the composites. Why aren t you constructing them so that
Message 5 of 8 , Aug 13, 2007
Posted by: "Jens Kruse Andersen" jens.k.a@... jkand71
> > Then there was the residual matter of factorizing 8
> > algebraic cofactors with 128 digits. (Jens says that this is
> > "relatively easy", but I do not know how many c128's he has
> > cracked with MPQS or GNFS. My score is precisely 0, with one
> > notable disaster trying to parallelize GGNFS on a c124.)
>
> Well, I didn't say what it was relative to ;-)
> But I have changed "relatively easy" to "possible" on the record page.

Wait a sec. You're constructing the composites. Why aren't you
constructing them so that they'd be SNFS rather than GNFS?
Forget stripping out the tiddlers with ECM, just use the 30%
leverage that SNFS gives you instead.

Phil

() ASCII ribbon campaign () Hopeless ribbon campaign
/\ against HTML mail /\ against gratuitous bloodshed

[stolen with permission from Daniel B. Cristofani]

____________________________________________________________________________________
Got a little couch potato?
Check out fun summer activities for kids.
http://search.yahoo.com/search?fr=oni_on_mail&p=summer+activities+for+kids&cs=bz
• ... Yes, that s eminently possible: it is easy to make the cofactors with digits/4 into simple quintics or sextics. The local problem is that with my GGNFS
Message 6 of 8 , Aug 13, 2007
--- In primeform@yahoogroups.com, Phil Carmody
<thefatphil@...> wrote:

> Wait a sec. You're constructing the composites. Why aren't you
> constructing them so that they'd be SNFS rather than GNFS?
> Forget stripping out the tiddlers with ECM, just use the 30%
> leverage that SNFS gives you instead.

Yes, that's eminently possible: it is easy to make the
cofactors with digits/4 into simple quintics or sextics.

The local problem is that with my GGNFS set-up the SNFS
option is broken, as Bouk well knows :-(

One fine day I might squeeze that extra 30%, with the
understanding that I might need to subcontract SNFS.

It's a good job Phil did not make his excellent suggestion
before my latest record effort, else I might have acted on
it and then missed the fluke that the second case with k=8

David
• ... I fixed it, at last. So now I guess that I am morally obliged to squeeze at least 25% extra digits. I ll try k=6 first, since there I have found a pair of
Message 7 of 8 , Aug 29, 2007

> The local problem is that with my GGNFS set-up the SNFS
> option is broken, as Bouk well knows :-(

I fixed it, at last. So now I guess that I am morally
obliged to squeeze at least 25% extra digits.

I'll try k=6 first, since there I have found a pair of
rather neat 72nd [sic] order polynomials, that factorize
8/24 of the algebraic sextics into 16 cubics and leave the
remaining 16 sextics in a tidy form for SNFS, if they don't
fall below the MPQS or GNFS thresholds, after GMP-ECM.

But it may take a while to realize this 72nd order idea...

David (with thanks to Bouk and Phil)
• ... ? m=67440294559676054016000; ? y=(2*x^6+3*x^3-148)^2; ? N=(y-11^4)*(y-35^2)*(y-47^2)*(y-94^2)*(y-146^2)*(y-148^2)/m; ? factor(N*(N-1)) %4 = [x 3] [x^3 - 11
Message 8 of 8 , Sep 7, 2007

> But it may take a while to realize this 72nd order idea...

? m=67440294559676054016000;
? y=(2*x^6+3*x^3-148)^2;
? N=(y-11^4)*(y-35^2)*(y-47^2)*(y-94^2)*(y-146^2)*(y-148^2)/m;
? factor(N*(N-1))
%4 =
[x 3]

[x^3 - 11 1]

[x^3 - 3 1]

[x^3 + 2 1]

[x^3 + 6 1]

[x^3 + 10 1]

[x^3 + 11 1]

[x^3 + 13 1]

[2*x^3 - 23 1]

[2*x^3 - 19 1]

[2*x^3 - 17 1]

[2*x^3 - 9 1]

[2*x^3 - 1 1]

[2*x^3 + 3 1]

[2*x^3 + 9 1]

[2*x^3 + 25 1]

[2*x^6 + 3*x^3 - 296 1]

[2*x^6 + 3*x^3 - 294 1]

[2*x^6 + 3*x^3 - 288 1]

[2*x^6 + 3*x^3 - 269 1]

[2*x^6 + 3*x^3 - 242 1]

[2*x^6 + 3*x^3 - 234 1]

[2*x^6 + 3*x^3 - 195 1]

[2*x^6 + 3*x^3 - 183 1]

[2*x^6 + 3*x^3 - 126 1]

[2*x^6 + 3*x^3 - 113 1]

[2*x^6 + 3*x^3 - 101 1]

[2*x^6 + 3*x^3 - 87 1]

[2*x^6 + 3*x^3 - 62 1]

[2*x^6 + 3*x^3 - 21 1]

[2*x^6 + 3*x^3 - 8 1]

[2*x^6 + 3*x^3 + 3 1]

A k=6 record, using SNFS, is expected, shortly.

David
Your message has been successfully submitted and would be delivered to recipients shortly.