## Factorization of 6 consecutive integers > 10^1100

Expand Messages
• Let m=67440294559676054016000 y=(m*(10^71+145589)+22)^2 N=(y-11^4)*(y-35^2)*(y-47^2)*(y-94^2)*(y-146^2)*(y-148^2)/m-5 then N+k is factorized for k in [0,5].
Message 1 of 15 , Aug 14, 2007
Let

m=67440294559676054016000
y=(m*(10^71+145589)+22)^2
N=(y-11^4)*(y-35^2)*(y-47^2)*(y-94^2)*(y-146^2)*(y-148^2)/m-5

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

Proof:

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

Neighbouring composites:
c1094=(N-1)/(5*1948359547)
c1090=(N+6)/(2*11969*4471247659)
subjected to 300 ECM curves at B1=100000

14 August 2007
• ... Congratulations! Very neat. I was wondering whether you would go for 6 record numbers with a construction inspired by Jaroslaw s P(X). Thanks for showing
Message 2 of 15 , Aug 14, 2007
> m=67440294559676054016000
> y=(m*(10^71+145589)+22)^2
> N=(y-11^4)*(y-35^2)*(y-47^2)*(y-94^2)*(y-146^2)*(y-148^2)/m-5
>
> then N+k is factorized for k in [0,5].

Congratulations!
Very neat. I was wondering whether you would go for 6 record
numbers with a construction inspired by Jaroslaw's P(X).
Thanks for showing such an interest in my record page.
http://hjem.get2net.dk/jka/math/consecutive_factorizations.htm is updated.
I assume you don't object to 94-digit factorizations being
"relatively easy".

--
Jens Kruse Andersen
• ... No objection at all: I took a lazy route for k=6, staying well within the comfort zone of Msieve. Update on the wings: N = -6 mod
Message 3 of 15 , Aug 14, 2007
--- In primeform@yahoogroups.com, "Jens Kruse Andersen" <jens.k.a@...>
wrote:

> I assume you don't object to 94-digit factorizations being
> "relatively easy".

No objection at all: I took a lazy route for k=6,
staying well within the comfort zone of Msieve.

Update on the wings:

N = -6 mod 460041067299095322777708682147

with p35 still running.

David
• Hello ! I have a collection about 210 6k twins. for n+2 and n-2 I have scan all primfactors up to 1.6E9, without success. Perhaps find one of you the 4th
Message 4 of 15 , Aug 16, 2007
Hello !

I have a collection about 210 6k twins.
for n+2 and n-2 I have scan all primfactors up to
1.6E9,
without success.

Perhaps find one of you the 4th candidate. Any ideas
or interests ?

regards

Norman

Wissenswertes für Bastler und Hobby Handwerker. BE A BETTER HEIMWERKER! www.yahoo.de/clever
• ... If you run ECM up to p20 level you have a good chance: mu = 2*210*exp(Euler)*20/6200 = 2.4 and then you may well end up with a long haul, usin ECPP at 6.2k
Message 5 of 15 , Aug 16, 2007
--- In primeform@yahoogroups.com, "N.L." <nluhn@...> wrote:

> I have a collection about 210 6k twins.
> for n+2 and n-2 I have scan all primfactors up to
> 1.6E9, without success.

If you run ECM up to p20 level you have a good chance:

mu = 2*210*exp(Euler)*20/6200 = 2.4

and then you may well end up with a long haul,
usin ECPP at 6.2k digits, for a /genuine/ record.
[Note that, uncharacteristically, Jens allowed himself
to cheat, by not waiting for Primo at 4178 digits.]

David
• ... Around half would find no factor from 1.6E9 to p20 level ECM, so that half doesn t contribute to the chance. And p20 ECM on 420 6k numbers is not easy:
Message 6 of 15 , Aug 16, 2007
> --- In primeform@yahoogroups.com, "N.L." <nluhn@...> wrote:
>
>> I have a collection about 210 6k twins.
>> for n+2 and n-2 I have scan all primfactors up to
>> 1.6E9, without success.
>
> If you run ECM up to p20 level you have a good chance:
>
> mu = 2*210*exp(Euler)*20/6200 = 2.4

Around half would find no factor from 1.6E9 to p20 level ECM,
so that half doesn't contribute to the chance.
And p20 ECM on 420 6k numbers is not easy:
420*74 curves taking 5 GHz minutes on one of my cpu cores
gives 108 GHz days.
With one (dual core) computer and lots of projects, I would
only give it p15 ECM if I got the twins.

> and then you may well end up with a long haul,
> usin ECPP at 6.2k digits, for a /genuine/ record.
> [Note that, uncharacteristically, Jens allowed himself
> to cheat, by not waiting for Primo at 4178 digits.]

I don't know if anybody would do 6k ECPP for my novel record page.
I wouldn't do 4178 digits, so it's up for grabs for a record share:
(240819405*2^13879+3)/(3*13*43*358877)
I may have cheated a little by allowing a prp factor but I also list the
proven 4-number record which I also have.

By the way, 6k with Primo would make the Primo top-20:
http://www.ellipsa.net/public/primo/top20.html
There are no certifications since 2005.
The Prime Pages ECPP top-20 at http://primes.utm.edu/top20/page.php?id=27
has a Primo submission from July 12 2007:
http://primes.utm.edu/primes/page.php?id=81647
It's 17443#/2-2^17443 with 7508 digits by Markus Hiltbrunner
who has no other primes. It would be third on the Primo top-20.
Is there a published certificate? It appears Marcel requires it but not
Chris.

--
Jens Kruse Andersen
• Hello ! That is the problem ! A ECM test for a single number ( I have 420!) takes to many time. Better is a Pollard Test for 6k numbers but I don t have a
Message 7 of 15 , Aug 16, 2007
Hello !

That is the problem !
A ECM test for a single number ( I have 420!) takes to
many time. Better is a Pollard Test for 6k numbers but
I don't have a programm that handle this type.
I can test factors up to 10^11..if I have luck,okay ,I
don't have luck ->pitch!

--
Norman

--- Jens Kruse Andersen <jens.k.a@...> schrieb:

> > --- In primeform@yahoogroups.com, "N.L."
> <nluhn@...> wrote:
> >
> >> I have a collection about 210 6k twins.
> >> for n+2 and n-2 I have scan all primfactors up to
> >> 1.6E9, without success.
> >
> > If you run ECM up to p20 level you have a good
> chance:
> >
> > mu = 2*210*exp(Euler)*20/6200 = 2.4
>
> Around half would find no factor from 1.6E9 to p20
> level ECM,
> so that half doesn't contribute to the chance.
> And p20 ECM on 420 6k numbers is not easy:
> 420*74 curves taking 5 GHz minutes on one of my cpu
> cores
> gives 108 GHz days.
> With one (dual core) computer and lots of projects,
> I would
> only give it p15 ECM if I got the twins.
>
> > and then you may well end up with a long haul,
> > usin ECPP at 6.2k digits, for a /genuine/ record.
> > [Note that, uncharacteristically, Jens allowed
> himself
> > to cheat, by not waiting for Primo at 4178
> digits.]
>
> I don't know if anybody would do 6k ECPP for my
> novel record page.
> I wouldn't do 4178 digits, so it's up for grabs for
> a record share:
> (240819405*2^13879+3)/(3*13*43*358877)
> I may have cheated a little by allowing a prp factor
> but I also list the
> proven 4-number record which I also have.
>
> By the way, 6k with Primo would make the Primo
> top-20:
> http://www.ellipsa.net/public/primo/top20.html
> There are no certifications since 2005.
> The Prime Pages ECPP top-20 at
> http://primes.utm.edu/top20/page.php?id=27
> has a Primo submission from July 12 2007:
> http://primes.utm.edu/primes/page.php?id=81647
> It's 17443#/2-2^17443 with 7508 digits by Markus
> Hiltbrunner
> who has no other primes. It would be third on the
> Primo top-20.
> Is there a published certificate? It appears Marcel
> requires it but not
> Chris.
>
> --
> Jens Kruse Andersen
>
>

__________________________________
Yahoo! Clever - Der einfachste Weg, Fragen zu stellen und Wissenswertes mit Anderen zu teilen. www.yahoo.de/clever
• ... I don t know why GMP-ECM stopped giving recommended p15 parameters. ... This is the README file of gmp-ecm-5.0, a new version of gmp-ecm, replacing version
Message 8 of 15 , Aug 16, 2007
Norman wrote:
> A ECM test for a single number ( I have 420!) takes to
> many time. Better is a Pollard Test for 6k numbers but
> I don't have a programm that handle this type.
> I can test factors up to 10^11..if I have luck,okay ,I
> don't have luck ->pitch!

I don't know why GMP-ECM stopped giving recommended p15 parameters.
Here is some of the documentation for a former version:
------------------------------------
This is the README file of gmp-ecm-5.0, a new version of gmp-ecm,
replacing version 4c.

The ECM method is a probabilistic method, and can be viewed in some sense
as a generalization of the P-1 and P+1 method, where we only require that
P+t is smooth, with t random of order P^(1/2). The optimal B1 and B2 bounds
have to be chosen according to the (usually unknown) size of P. The
following
table gives a set of near-to-optimal B1 and B2 pairs, with the corresponding
expected number of curves to find a factor of given size (this table does
not
take into account the "extra factors" found by Brent-Suyama's extension, see
below).

digits D optimal B1 B2 expected curves N(B1,B2,D)
15 2e3 1.2e5 30
20 11e3 1.4e6 90
25 5e4 1.2e7 240
30 25e4 1.1e8 500
35 1e6 8.4e8 1100
40 3e6 4.0e9 2900
45 11e6 2.6e10 5500
50 43e6 1.8e11 9000
55 11e7 6.8e11 22000
60 26e7 2.3e12 52000
65 85e7 1.3e13 83000
70 29e8 7.2e13 120000

Table 1: optimal B1 and expected number of curves to find a
factor of D digits.

Important note: the expected number of curves is significantly smaller
than the "classical" one we get with B2=100*B1. This is due to the
fact that this new version of gmp-ecm uses a default B2 which is much
larger than 100*B1 (for large B1), thanks to the improvements in step 2.

After performing the expected number of curves from Table 1, the
probability that a number of D digits was missed is exp(-1), i.e.
about 37%. After twice the expected number of curves, it is exp(-2),
i.e. about 14%, and so on.

Example: after performing 9000 curves with B1=43e6 and B2=1.8e11,
the probability to miss a 50-digit factor is about 37%.

In summary, we advise the following method:

0 - choose a target factor size of D digits
1 - choose "optimal" B1 and B2 values to find factors of D digits
2 - run once P-1 with those B1 and B2
3 - run 3 times P+1 with those B1 and B2
4 - run N(B1,B2,D) times ECM with those B1 and B2, where N(B1,B2,D) is the
expected number of ECM curves with step 1 bound B1, step 2 bound B2,
to find a factor of D digits (cf above table)
5 - if no factor is found, either increase D and go to 0, or use another
factorization method (MPQS, GNFS)
------------------------------------

Some things have changed in later versions. I'm not sure how
they affect p15 work.
This is a guess at reasonable p15 parameters with GMP-ECM 6.1.2:

P-1 with B1=20000 and default B2: ecm -pm1 20000
3 times P+1 with B1=10000 and default B2: ecm -c 3 -pp1 10000
26 curves with B1=2000 and default B2: ecm -c 26 2000

This may take around 2 GHz weeks for 420 6k numbers.

Suppose you have saved far more primes n-1 where n is trivially
factored and n+1 was composite.
Then n-1, n, 2n-2, 2n, 3n-3,3n are factored. You could then
try trial factoring and prp (no ecm) on
n-3, n-2, 2n-3, 2n-1, 2n+1, 3n-2, 3n-1.
If one of these gives a prp cofactor then you have 3 of 4 and
could do p15 ecm on the last (the last two if 2n-1 split).
If successful, you would probably have two 6k prp's that
require ECPP, but I accept them as prp records.

--
Jens Kruse Andersen
• ... Marcel missed this one, from July 2007: http://primes.utm.edu/primes/page.php?id=81647 David
Message 9 of 15 , Aug 16, 2007
--- In primeform@yahoogroups.com, "Jens Kruse Andersen" <jens.k.a@...>
wrote:

> http://www.ellipsa.net/public/primo/top20.html
> There are no certifications since 2005.

Marcel missed this one, from July 2007:

http://primes.utm.edu/primes/page.php?id=81647

David
• ... That sounds like less than a week s work, for Sean Irvine. Best advice to Norman: share your finds with Sean! David
Message 10 of 15 , Aug 16, 2007
--- In primeform@yahoogroups.com, "Jens Kruse Andersen" <jens.k.a@...>
wrote:

> 420*74 curves taking 5 GHz minutes on one of my cpu cores
> gives 108 GHz days.

That sounds like less than a week's work, for Sean Irvine.

David
• ... I see that p15 was enough: http://hjem.get2net.dk/jka/math/consecutive_factorizations.htm ... Congrats to Norman and Christophe. David
Message 11 of 15 , Aug 28, 2007
--- In primeform@yahoogroups.com, "N.L." <nluhn@...> wrote:

> A ECM test for a single number ( I have 420!) takes to
> many time.

I see that p15 was enough:

http://hjem.get2net.dk/jka/math/consecutive_factorizations.htm
> n+3 = 2^3*943127*5020192965913*prp6203

Congrats to Norman and Christophe.

David
• ... Yes, congratulations. They found two cases with p12 and p13 as penultimate factors. There is no plan to prove prp6203. After 3 weeks with the page, my 4
Message 12 of 15 , Aug 28, 2007
> I see that p15 was enough:
>
> http://hjem.get2net.dk/jka/math/consecutive_factorizations.htm
>> n+3 = 2^3*943127*5020192965913*prp6203
>
> Congrats to Norman and Christophe.

Yes, congratulations.
They found two cases with p12 and p13 as penultimate factors.
There is no plan to prove prp6203.

After 3 weeks with the page, my 4 records are already beaten, and 3 further
lengths have been found. I'm surprised by so many great results so quickly.
Thanks to everybody. I expect things to cool down now but what do I know?

--
Jens Kruse Andersen
• ... That s easy to explain: your idea for a record page was so clearly and cleanly executed that anyone who had anything up their sleeve was almost bound to
Message 13 of 15 , Aug 29, 2007
--- In primeform@yahoogroups.com, "Jens Kruse Andersen" <jens.k.a@...>
wrote:

> I'm surprised by so many great results so quickly.

That's easy to explain: your idea for a record page was
so clearly and cleanly executed that anyone who had
anything up their sleeve was almost bound to respond.

> I expect things to cool down now but what do I know?

Well, at least the k=6 and k=8 records are soft targets
for Phil's GNFS ==> SNFS improvement. (k=7 and k=10
may be harder to improve since there I had beginner's
luck, with the PFGW + GMP-ECM parts of the problem.)

David
• ... Well, it may be that k=3 is also under threat: http://www.primegrid.com/all_news.php#11 ... But maybe that message is about a Woodall/Cullen find? David
Message 14 of 15 , Aug 29, 2007
--- In primeform@yahoogroups.com, "Jens Kruse Andersen"
<jens.k.a@...> wrote:

> I expect things to cool down now but what do I know?

Well, it may be that k=3 is also under threat:

http://www.primegrid.com/all_news.php#11
> and we want to know your details before we publicize it.

But maybe that message is about a Woodall/Cullen find?

David
• ... This apparently unvalidated claim is still on list. Perhaps Chris might ask the submitter for evidence? David
Message 15 of 15 , Jul 12, 2010
--- In primeform@yahoogroups.com,
"Jens Kruse Andersen" <jens.k.a@...> wrote:

> The Prime Pages has a Primo submission from July 12 2007:
> http://primes.utm.edu/primes/page.php?id=81647
...
> Is there a published certificate?
> It appears Marcel requires it but not Chris.

This apparently unvalidated claim is still on list.
Perhaps Chris might ask the submitter for evidence?

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