See
http://linux.softpedia.com/get/Science-and-Engineering/Mathematics/PARI-GP-35205\
.shtml



________________________________
From: sopadeajo2001 <sopadeajo2001@...>
To: primeform@yahoogroups.com
Sent: Friday, September 4, 2009 12:00:51 PM
Subject: [primeform] Pari gp with Ubuntu Linux


I just began a new dual boot with Ubuntu.
I'll try (if i can ) to use window$ as few as possible; so i downloaded Pari gp
but i cannot find the .exe equivalent in Linux to begin Pari gp.
I do not know anything about commands in Linux.Any helping soul?




[Non-text portions of this message have been removed]

Andrew Steward maintains an amazing list of all known legal generalized
repunit primes at http://www.primes.viner-steward.org/andy/titans.html .

In Chris Caldwell's sense, a legal generalized repunit prime is a prime
number of the form (b^p-1)/(b-1) such that 3<=b<=5p, b<>10, p prime.

Unfortunately, as far as I know, a list of pseudoprimes to fill the gaps
in Andy's list is not available, so I started collecting them to help
Andrew's site grow.

You can find the list at phi.redgolpe.com .

                              Bernardo Boncompagni

________________________________________________

"When the missionaries arrived, the Africans had
the  land  and  the  missionaries had the bible.
They  taught  how  to pray with our eyes closed.
When  we  opened  them, they had the land and we
had the bible"
                              Jomo Kenyatta

VisualTaxa - Taxonomy in a visual way
                    http://visualtaxa.redgolpe.com
________________________________________________

Thanks for sharing the comments and analysis David!

Your point is valid, but may be an oversimplification.

The probability you mention appears to be the chance a cofactor is prime and not
the probability ECM will completely work under a given range. The FAQ at
ElevenSmooth suggests the probability an L-digit number will completely factor
after eliminating factors between 10^a and 10^b is:
h(L,a,b)=sum(k=1,10,(exp(-log(b/a)) * (log(b/a)^k)/k!) * (exp(c)*b /
(L-k*(b-a)/log(b/a))))

Your logic still applies and the probability is in favor of the single 600-digit
number completely factoring before two 300 digit ones given the same ECM curves
but not that bad. And this doesn't take into account that GMP-ECM appears to run
about 3 times faster on numbers of 300 digits than 600 digits.

It's all academic I think anyway because the bottleneck appears to be SNFS at
200 digits (perhaps taking ~10 days each to finish on a quad core).

- Joe Crump


--- In primeform@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
>
>
>
> --- In primeform@yahoogroups.com,
> "Jens Kruse Andersen" <jens.k.a@> wrote:
>
> > Congratulations on retaking the record for k=9.
>
> The k=10 record, by Joe and Michael (the brothers Crump)
> is rather intriguing: it has too *much* algebraic factorization.
>
> In essence, they proceed from the observation that
> x^2*(2*x^2-5)^2 - n is algebraically factorizable for
> 8 of the 10 values n=0...9 :
>
>  for(n=0,9,f=factor(x^2*(2*x^2-5)^2-n)[,1]~;if(#f>1,print([n,f])))
> [0, [x, 2*x^2 - 5]]
> [1, [2*x^3 - 5*x - 1, 2*x^3 - 5*x + 1]]
> [2, [x^2 - 2, 2*x^2 - 4*x + 1, 2*x^2 + 4*x + 1]]
> [3, [x^2 - 3, 2*x^2 - 2*x - 1, 2*x^2 + 2*x - 1]]
> [4, [2*x^3 - 5*x - 2, 2*x^3 - 5*x + 2]]
> [6, [2*x^2 - 3, 2*x^4 - 7*x^2 + 2]]
> [8, [2*x^2 - 1, 2*x^4 - 9*x^2 + 8]]
> [9, [x - 1, x + 1, 2*x^2 - 2*x - 3, 2*x^2 + 2*x - 3]]
>
> The factorizations for n=0,2,3,9 involves terms with
> no more than 33% of the digits of the target.
> So if you are prepared to run SNFS up to (say) 200
> digits (with a suitable cubic for x) you can reach
> 600 digit targets, in these cases, as they remark.
>
> The factorizations for n=6,8 are useful: they reduce
> the digits in the GMP-ECM part of the work from 600
> to 400 digits, for these two targets.
>
> But then comes the snag: the factorizations for n=1,4
> are strongly counterproductive: each splits a 600-digit
> target into a pair of 300-digit targets. It is clearly
> much harder, on average, to achieve complete factorizations
> of a pair of numbers of length L digits than for a single
> number of length 2L. Suppose that you are prepared to
> run ECM to a depth of d << L digits. Then the probability
> of factorizing both parts, each with length L, is
>
> P_both = (exp(Euler)*d/L)^2
>
> while the probability of factorizing a target with
> no algebraic factorization is
>
> P_single = exp(Euler)*d/(2*L)
>
> This hang-up happens twice, at n=1 and n=4.
> Hence the "penalty" for too much algebraic factorization
> is an *inefficiency* by a factor of roughly
>
> (P_single/P_both)^2 = (exp(-Euler)*L/(2*d))^2
>
> With, say, L=300 and d=30, this is a factor of about 8.
>
> So the challenge in polynomial selection is this:
> to get 4 good multi-SNFS targets (here at n=0,2,3,9)
> plus a pair of GMP-ECM easements (here at n=6,8)
> without paying the (say) 8-fold penalty for a
> pair of counterproductive factorizations (here at n=1,4).
>
> It's a neat puzzle, to which I have, as yet, no solution.
>
> In any case, I am staying, at present, with my
> "25% or 100%" strategy, based on Prouhet-Tarry-Escott,
> for 8 or 9 consecutive factorizations, as in
>
> http://users.cybercity.dk/~dsl522332/math/consecutive_factorizations.htm
>
> David (with thanks to Jens and Joe, for stimulus)
>

--- In primeform@yahoogroups.com,
"kraDen" <kradenken@...> wrote:

> I'm currently attempting to rewrite my C++ code in assembler.

Watch this space, folks. Mike's code is already rather nifty;
Ken's might get even niftier.

Per ardua ad astra

David

Hi Mike,

--- In primeform@yahoogroups.com, "mikeoakes2" <mikeoakes2@...> wrote:
>
>
>
>
>
> --- In primeform@yahoogroups.com, "kraDen" <kradenken@> wrote:
> >
> > Hi All
> >
> > (19303382 + $n*41724940)*5011#+1 (n=0-5) describes an AP6 of 2152-2153 digit
primes.
> >
>
> Congrats, Ken!
> (We are playing leap-frog on this one:-)
>
> Did you sieve k=1..250million, or what?
> Any other stats on your run?

sieved n=100,000,000-200,000,000 to 10^12
30,873,079 tests
306917 prps
147359 ap4s
335 ap5s
0 ap6s
extended ap5's (up 77 and down 70) no ap6
extended  ap4's (up 36,660 and down 37,209) no ap6
Modified C++ program to extend all ap3s up and down
gave 48,197,836 chances at an ap4
after newpgening, prping and combining with originals had
416840 prps
325635 ap4s
764 ap5s
0 ap6s
Thankfully extending the ap4s this time yielded the desired result

> -Mike Oakes
>

cheers
Ken

p.s.
I'm currently attempting to rewrite my C++ code in assembler. when/if I succeed
(am having fun (trouble) with the file I/O and array referencing at the moment)
I hope to attack some aps > 10 in length

--- In primeform@yahoogroups.com,
"djbroadhurst" <d.broadhurst@...> wrote:

> Congratulations to Timea Csajbok, Gabor Farkas, Antal Jarai,
> Zoltan Jarai and Janos Kasza for a bigger Sophie:
> http://primes.utm.edu/primes/page.php?id=90711

And renewed congratulations, for another:
http://primes.utm.edu/primes/page.php?id=90907

Where PrimeGrid and TPS failed, Minnesota, Stanford
and Eötvös Loránd Tudományegyetem succeed, with Sophie.

David

Letting f(x) be your polynomial, you can eliminate one sextic (replacing it with
a quartic) by using f(5*x^3-x^2-x-1).

i.e.

h(x) = (x*(5*x + 9)/2 - 31)^2;
d(x) = (h(x) - 23^2)*(h(x) - 24^2)/55440;
j(x) = d(5*x^3-x^2-x-1);
factor(j(x)*(j(x)-3)*(j(x)-4))


[x - 1 1]
[x + 1 1]
[5*x^2 - 6*x + 5 1]
[5*x^2 - x - 2 1]
[5*x^2 + 4*x + 3 1]
[5*x^3 - x^2 - x - 2 1]
[5*x^3 - x^2 - x - 1 1]
[5*x^3 - x^2 - x + 3 1]
[5*x^3 - x^2 - x + 4 1]
[25*x^3 - 5*x^2 - 5*x - 26 1]
[25*x^3 - 5*x^2 - 5*x - 21 1]
[25*x^3 - 5*x^2 - 5*x - 16 1]
[25*x^3 - 5*x^2 - 5*x + 4 1]
[25*x^3 - 5*x^2 - 5*x + 9 1]
[25*x^3 - 5*x^2 - 5*x + 14 1]
[25*x^4 - 5*x^3 - x + 1 1]
[125*x^6 - 50*x^5 - 45*x^4 + 5*x^3 + 6*x^2 + x - 128 1]
[125*x^6 - 50*x^5 - 45*x^4 + 5*x^3 + 6*x^2 + x - 114 1]
[125*x^6 - 50*x^5 - 45*x^4 + 5*x^3 + 6*x^2 + x - 112 1]
[125*x^6 - 50*x^5 - 45*x^4 + 5*x^3 + 6*x^2 + x - 90 1]
[125*x^6 - 50*x^5 - 45*x^4 + 5*x^3 + 6*x^2 + x - 20 1]

- Joe Crump

--- In primeform@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
>
>
>
> --- In primeform@yahoogroups.com,
> "mikeoakes2" <mikeoakes2@> wrote:
>
> > >  z = w^3*(5*w^3 + 9)/2 - 31;
> > >  n = (z^2 - 23^2)*(z^2 - 24^2)/55440;
> > The main step that boggles the mind is the next-to-last line.
> > Can you elaborate on the route to that sextic
>
> It's a sextic for the benefit of SNFS.
> For most purposes we only need the fact
> that it is a quadratic in v = w^3.
>
> I found it by taking the 12 roots R[k] of the 3 quartics
> and maximizing the number of quadratics
> a*v^2 + b*v + c - d*R[k]
> that factorize. Clearly we should choose c = d*R[j] for
> one of 12 roots.  Also note that the signs of b and d
> are immaterial. So I searched with these loops:
>
>  R=[-32, -31, -24, -23, -12, -9, 9, 12, 23, 24, 31, 32];
>  test(a,b,c,d)=sum(k=1,12,issquare(b^2-4*a*(c-d*R[k])));
>  {for(a=1,10,for(b=1,10,for(j=1,12,for(d=1,10,c=d*R[j];
>  t=test(a,b,c,d);if(t>5,print([[a,b,c,d],t]))))));}
> [[1, 9, -310, 10], 6]
> [[2, 9, -155, 5], 6]
> [[5, 9, -62, 2], 6]
> [[10, 9, -31, 1], 6]
>
> Extending the loops, I found no solution with more than
> 6 out of 12 quadratic factorizations. As you may see from
> > z = w^3*(5*w^3 + 9)/2 - 31
> I chose the solution with a=5 and b=9.
>
> David
>

Ken wrote:
> (19303382 + $n*41724940)*5011#+1 (n=0-5) describes an AP6
> of 2152-2153 digit primes.

Congratulations.
http://users.cybercity.dk/~dsl522332/math/aprecords.htm is updated
with the assumption that NewPGen and PrimeForm were used again.

--
Jens Kruse Andersen

--- In primeform@yahoogroups.com, "kraDen" <kradenken@...> wrote:
>
> Hi All
>
> (19303382 + $n*41724940)*5011#+1 (n=0-5) describes an AP6 of 2152-2153 digit
primes.
>

Congrats, Ken!
(We are playing leap-frog on this one:-)

Did you sieve k=1..250million, or what?
Any other stats on your run?

-Mike Oakes

Hi All

(19303382 + $n*41724940)*5011#+1 (n=0-5) describes an AP6 of 2152-2153 digit
primes.

cheers
Ken


Primality testing (19303382 + 0*41724940)*5011#+1 [N-1,
Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
Calling Brillhart-Lehmer-Selfridge with factored part 33.43%
(19303382 + 0*41724940)*5011#+1 is prime! (1.6747s+0.0019s)
Primality testing (19303382 + 1*41724940)*5011#+1 [N-1,
Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
Calling Brillhart-Lehmer-Selfridge with factored part 33.44%
(19303382 + 1*41724940)*5011#+1 is prime! (1.6605s+0.0017s)
Primality testing (19303382 + 2*41724940)*5011#+1 [N-1,
Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
Calling Brillhart-Lehmer-Selfridge with factored part 33.49%
(19303382 + 2*41724940)*5011#+1 is prime! (1.6666s+0.0018s)
Primality testing (19303382 + 3*41724940)*5011#+1 [N-1,
Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
Calling Brillhart-Lehmer-Selfridge with factored part 33.43%
(19303382 + 3*41724940)*5011#+1 is prime! (1.6531s+0.0018s)
Primality testing (19303382 + 4*41724940)*5011#+1 [N-1,
Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
Calling Brillhart-Lehmer-Selfridge with factored part 33.48%
(19303382 + 4*41724940)*5011#+1 is prime! (1.6634s+0.0017s)
Primality testing (19303382 + 5*41724940)*5011#+1 [N-1,
Brillhart-Lehmer-Selfridge]
Running N-1 test using base 2
Calling Brillhart-Lehmer-Selfridge with factored part 33.43%
(19303382 + 5*41724940)*5011#+1 is prime! (1.6680s+0.0019s)

"By my records, Joe announced his at
> 17 November 2009 02:09
and I posted mine here at
> Tue Nov 17, 2009 2:43
so assuming that both the clocks use GMT
I missed out by almost an hour.

This was an amusing coincidence;
I had no idea that Joe was using my method.

David"

But you own (though shared) the method which can deal to other methods and thus
to other records.

--- In primeform@yahoogroups.com,
"djbroadhurst" <d.broadhurst@...> wrote:

> Extending the loops, I found no solution with more than
> 6 out of 12 quadratic factorizations.

Joe pointed out, off list, that one of the
6 remaining quadratics can be factored by
modifying the final cubic substitution.

Let's look again at my 6 remaining quadratics:

  z = v*(5*v + 9)/2 - 31;
  n = (z^2 - 23^2)*(z^2 - 24^2)/55440;
  f = factor(n*(n-3)*(n-4))[,1];
  for(k=1,#f,if(poldegree(f[k])==2,print(f[k])));
5*v^2 + 9*v - 124
5*v^2 + 9*v - 110
5*v^2 + 9*v - 108
5*v^2 + 9*v - 86
5*v^2 + 9*v - 16
5*v^2 + 9*v + 2

Here is a way to remove the 6th quadratic, while
still keeping SNFS fairly happy for the other 5:

  v = 5*w^3 - w^2 - w - 1;
  print(factor(5*v^2 + 9*v + 2)[,1]~);
[5*w^2 - w - 2, 25*w^4 - 5*w^3 - w + 1]

So if w = O(10^30) we split off about 60 digits
and are left with about 120 for ECM + GNFS (if needed)
and have (at most) 5 targets that might end up
with SNFS difficulty around 180, if ECM does not
get that down to GNFS territory.

An electronic carrot is available for any one who
can remove another SNFS, getting down to only 4.

David

--- In primeform@yahoogroups.com,
"Jens Kruse Andersen" <jens.k.a@...> wrote:

> The Crump record was announced first and submitted first to me,
> so your nice 641-digit case for k=8 is not listed in the record
> history at
http://users.cybercity.dk/~dsl522332/math/consecutive_factorizations.htm
> But it's mentioned in the news section.

Thanks Jens. That's quite right and fair.

By my records, Joe announced his at
> 17 November 2009 02:09
and I posted mine here at
> Tue Nov 17, 2009 2:43
so assuming that both the clocks use GMT
I missed out by almost an hour.

This was an amusing coincidence;
I had no idea that Joe was using my method.

David

David Broadhurst wrote:
> These 8 consecutive factorizations at 641 digits are in
> http://physics.open.ac.uk/~dbroadhu/cert/ifac641g.zip

and later:
> Aha, I have just seen that the Crump team
> has used my Ansatz to go up to 703 digits:
>
> http://immortaltheory.com/cnt/c703.html

The Crump record was announced first and submitted first to me,
so your nice 641-digit case for k=8 is not listed in the record history at
http://users.cybercity.dk/~dsl522332/math/consecutive_factorizations.htm
But it's mentioned in the news section.

--
Jens Kruse Andersen

--- In primeform@yahoogroups.com,
"djbroadhurst" <d.broadhurst@...> wrote:

> http://immortaltheory.com/cnt/c703.html
>
> They were prepared for SNFS difficulty 176,
> which is not hard. But fortunately GMP-ECM
> factored all 6 of my sextics, this time.

I meant to say GMP-ECM + GNFS. The largest
GNFS dificulty, after GMP-ECM, was 117,
which is not hard:

http://homepage2.nifty.com/m_kamada/math/graphs.htm

David

--- In primeform@yahoogroups.com,
"djbroadhurst" <d.broadhurst@...> wrote:

> After using GMP-ECM to depth p35, I was left with a pair
> of composites, with 147 and 148 digits, at an SNFS
> difficulty of about 161 digits, which is rather routine

Aha, I have just seen that the Crump team
has used my Ansatz to go up to 703 digits:

http://immortaltheory.com/cnt/c703.html

They were prepared for SNFS difficulty 176,
which is not hard. But fortunately GMP-ECM
factored all 6 of my sextics, this time.

It's good to see that they are now OpenPFGW converts.

David

--- In primeform@yahoogroups.com,
"djbroadhurst" <d.broadhurst@...> wrote:

> Note that only half of the 12 sextics are now algebraically
> unfactorized. For the record, GMP-ECM factorized 4 of these
> 6 sextic numbers, so I was left with only 2 for SNFS.

After using GMP-ECM to depth p35, I was left with a pair
of composites, with 147 and 148 digits, at an SNFS
difficulty of about 161 digits, which is rather routine:

m: 660000000000000022015110480

c6: 5
c3: 9
c0: 2
Divisors found:
r1=40458...43761 (pp42)
r2=11075...74887 (pp49)
r3=15892...15207 (pp58)

c6: 5
c3: 9
c0: -86
Divisors found:
r1=72684...06931 (pp72)
r2=65615...22978 (pp76)

Note that the SNFS difficulty comes from
5*(66*10^25)^6 =~ 4*10^161
since you get no Brownie points for having
already removed about 14 digits.

As it turned out, the first target would have been
accessible to deeper GMP-ECM. But one has no way of
knowing that, before running SNFS.

The SNFS cost per target was about 4 GHz-days of sieving and
0.3 GHz-days of block-Lanczos, using a trusty 2004-vintage
GGNFS-0.77.1 from Chris Monico, which parallelizes sieving
quite neatly. I'm sure that newer versions are quicker, but
it's reassuring to know that one is using a set-up that has
done bigger things before. For example:

SNFS difficulty: 175 digits.
Divisors found:
r1=40537...23036 (pp83)
r2=69874...49619 (pp86)

was done to provide vital helpers for
http://primes.utm.edu/primes/page.php?id=82297
which finally reached 26.38% for CHG.

David

--- In primeform@yahoogroups.com,
"mikeoakes2" <mikeoakes2@...> wrote:

> >  z = w^3*(5*w^3 + 9)/2 - 31;
> >  n = (z^2 - 23^2)*(z^2 - 24^2)/55440;
> The main step that boggles the mind is the next-to-last line.
> Can you elaborate on the route to that sextic

It's a sextic for the benefit of SNFS.
For most purposes we only need the fact
that it is a quadratic in v = w^3.

I found it by taking the 12 roots R[k] of the 3 quartics
and maximizing the number of quadratics
a*v^2 + b*v + c - d*R[k]
that factorize. Clearly we should choose c = d*R[j] for
one of 12 roots.  Also note that the signs of b and d
are immaterial. So I searched with these loops:

  R=[-32, -31, -24, -23, -12, -9, 9, 12, 23, 24, 31, 32];
  test(a,b,c,d)=sum(k=1,12,issquare(b^2-4*a*(c-d*R[k])));
  {for(a=1,10,for(b=1,10,for(j=1,12,for(d=1,10,c=d*R[j];
  t=test(a,b,c,d);if(t>5,print([[a,b,c,d],t]))))));}
[[1, 9, -310, 10], 6]
[[2, 9, -155, 5], 6]
[[5, 9, -62, 2], 6]
[[10, 9, -31, 1], 6]

Extending the loops, I found no solution with more than
6 out of 12 quadratic factorizations. As you may see from
> z = w^3*(5*w^3 + 9)/2 - 31
I chose the solution with a=5 and b=9.

David

--- In primeform@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
>
> Now observe that
>
>  print([Q[2]-Q[3],Q[2]-Q[1]]/55440)
> [3, 4]
>
> yields small integers. Finally, I set z to be a cunning sextic:
>
>  z = w^3*(5*w^3 + 9)/2 - 31;
>  n = (z^2 - 23^2)*(z^2 - 24^2)/55440;

The main step that boggles the mind is the next-to-last line.
Can you elaborate on the route to that sextic - or is it [as I rather suspect] a
"trade secret"?!

Mike

--- In primeform@yahoogroups.com,
"djbroadhurst" <d.broadhurst@...> foolishly wrote:

> 1105 = 5*11*17

Of course, the whole point is that

1105 = 5*13*17

is the smallest product of 3 odd natural
primes that are not Gaussian primes.
As far as I can tell, no larger product of
this kind is suitable for Jens's challenge

David

--- In primeform@yahoogroups.com,
"mikeoakes2" <mikeoakes2@...> wrote:

> > x = (1320*(5*10^23 + 16678114))^3
> > y = (x*(5*x + 9)/2 - 31)^2
> > N = (y - 23^2)*(y - 24^2)/55440 - 6
> Any tips for the rest of us mortals on how on earth to go about
> dreaming up suitable input starting-numbers for such an exercise?

We know, from Fermat and Gauss, that

1105 = 5*11*17 =
norm((2+I)*(3+2*I)*(4+I)) = 9^2 + 32^2 =
norm((2+I)*(3+2*I)*(4-I)) = 23^2 + 24^2 =
norm((2-I)*(3+2*I)*(4+I)) = 31^2 + 12^2 =
norm((2+I)*(3-2*I)*(4+I)) = 33^2 + 4^2

is the smallest integer that is expressible as the sum of
two coprime squares in more than two ways. From this, we can
form 4 completely factorized quartics that differ only by
constants:

  {Q = [
  (z^2 -  9^2)*(z^2 - 32^2),
  (z^2 - 23^2)*(z^2 - 24^2),
  (z^2 - 31^2)*(z^2 - 12^2),
  (z^2 - 33^2)*(z^2 -  4^2)];}
  for(k=1,4,print(Q[k]));
z^4 - 1105*z^2 + 82944
z^4 - 1105*z^2 + 304704
z^4 - 1105*z^2 + 138384
z^4 - 1105*z^2 + 17424

Now observe that

  print([Q[2]-Q[3],Q[2]-Q[1]]/55440)
[3, 4]

yields small integers. Finally, I set z to be a cunning sextic:

  z = w^3*(5*w^3 + 9)/2 - 31;
  n = (z^2 - 23^2)*(z^2 - 24^2)/55440;
  {for(i=1,3,print();
  f=factor(n-[0,3,4][i])[,1];for(j=1,#f,print(f[j])))}

w - 1
w^2 + w + 1
5*w^3 + 14
5*w^6 + 9*w^3 - 110
5*w^6 + 9*w^3 - 108
5*w^6 + 9*w^3 - 16

w
w^3 - 2
5*w^3 + 9
5*w^3 + 19
5*w^6 + 9*w^3 - 124
5*w^6 + 9*w^3 - 86

w^3 + 4
w^3 + 5
w^3 + 6
5*w^3 - 21
5*w^3 - 16
5*w^3 - 11
5*w^6 + 9*w^3 + 2

Note that only half of the 12 sextics are now algebraically
unfactorized. For the record, GMP-ECM factorized 4 of these
6 sextic numbers, so I was left with only 2 for SNFS.

David

--- In primeform@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
>
> Hence I was minded to improve the record for
> 8 consecutive factorizations to 641 digits:
>
> Let
>
> x = (1320*(5*10^23 + 16678114))^3
> y = (x*(5*x + 9)/2 - 31)^2
> N = (y - 23^2)*(y - 24^2)/55440 - 6
>
> then
>
> p636 =  N/(3*70459)
> p627 = (N + 1)/(2*100811951838973)
> p641 =  N + 4
> p635 = (N + 5)/(2*7*23*1471)
> p638 = (N + 7)/(2^2*613)
>
> are prime. Moreover N + 2, N + 3 and N + 6 are completely
> factorized, with no prime factor having more than 143 digits.
> These 8 consecutive factorizations at 641 digits are in
> http://physics.open.ac.uk/~dbroadhu/cert/ifac641g.zip
>
> Notes: I used OpenPFGW, GMP-ECM, Msieve, ggnfs, Pari-GP.
> All primality proofs were performed by Pari-GP.
> The primality proof for p641 is easy, since
> we know the factorization of p641 - 1 = N + 3.
> The composite numbers
> c583 =
(N-1)/(2^2*7669*393535016983*38412205928303455069*8513952096310465936763)
> c636 = (N+8)/(5*10729)
> are unlikely to have any prime divisor less than 10^30.
>

Many congrats on such a fiendishly clever construction, David.

Any tips for the rest of us mortals on how on earth to go about dreaming up
suitable input starting-numbers for such an exercise?

-Mike Oakes

--- In primeform@yahoogroups.com,
"djbroadhurst" <d.broadhurst@...> wrote:

> Note, however, that the riposte of the Crump team will
> be rather impressive. They are now preparing to run
> SNFS (if necessary, GMP-ECM might still be enough)
> at 200 digits in preparation for scooping
> all the k=8,9,10 records, at 602 digits.

Hence I was minded to improve the record for
8 consecutive factorizations to 641 digits:

Let

x = (1320*(5*10^23 + 16678114))^3
y = (x*(5*x + 9)/2 - 31)^2
N = (y - 23^2)*(y - 24^2)/55440 - 6

then

p636 =  N/(3*70459)
p627 = (N + 1)/(2*100811951838973)
p641 =  N + 4
p635 = (N + 5)/(2*7*23*1471)
p638 = (N + 7)/(2^2*613)

are prime. Moreover N + 2, N + 3 and N + 6 are completely
factorized, with no prime factor having more than 143 digits.
These 8 consecutive factorizations at 641 digits are in
http://physics.open.ac.uk/~dbroadhu/cert/ifac641g.zip

Notes: I used OpenPFGW, GMP-ECM, Msieve, ggnfs, Pari-GP.
All primality proofs were performed by Pari-GP.
The primality proof for p641 is easy, since
we know the factorization of p641 - 1 = N + 3.
The composite numbers
c583 = (N-1)/(2^2*7669*393535016983*38412205928303455069*8513952096310465936763)
c636 = (N+8)/(5*10729)
are unlikely to have any prime divisor less than 10^30.

David Broadhurst, 17 November, 2009

--- In primeform@yahoogroups.com,
"michael_b_porter" <michael_b_porter@...> wrote:

> Congratulations!  That seems to be good enough to take back
> the record.

Thanks, Michael.

Note, however, that the riposte of the Crump team will
be rather impressive. They are now preparing to run
SNFS (if necessary, GMP-ECM might still be enough)
at 200 digits in preparation for scooping
all the k=8,9,10 records, at 602 digits.

I repeat my thanks to Jens for originating
this excellent challenge, which combines
several mathematical and computing skills.

Best regards to all,

David

--- In primeform@yahoogroups.com,
"Jens Kruse Andersen" <jens.k.a@...> wrote:

> I had the record for k=3 with prp's allowed

Well, boss, you did set the rules :-)

But the rule that allows PrP's goes against
the spirit of primality proving, to my mind.

I appreciate, dear Jens, that even with PrP's
allowed you are chasing a formidable challenge at
k=3, above 100k digits. But even if you succeed,
it will be a lesser achievement than the proven
SunGard/PrimeGrid constellation, to my mind. The
discipline of coming up with provable forms is
what adds piquancy to Chris's pages (and most of
yours).

Good luck, in any case!

David

I need some days to understand the chalenge you reach
but I just remark that you wrote it on Armistice day ,
11 is prime as 11 ,11/11/1918 remember day ( what ?)!
Then you need to stand until the 1923 year
for a year prime number.Are some things strange in 1923 ?
Are the history related with prime numbers ?
Amitiés
Pierre


--- In primeform@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
>
> Let
>
> x = (1320*(10^20 + 13065906))^3
> y = (x*(5*x + 9)/2 - 31)^2
> N = (y - 23^2)*(y - 24^2)/55440 - 7
>
> then
>
> p544  =  N/(2^2*85580203)
> p552a = (N + 1)/3
> p546  = (N + 2)/(2*7^2*16127)
> p540  = (N + 5)/(223*9887*252181)
> p552b = (N + 6)/2
> p533  = (N + 8)/(2^2*9479*90863*15503173813)
>
> are prime. Moreover N + 3, N + 4 and N + 7 are completely
> factorized, with no prime factor having more than 128 digits.
> These 9 consecutive factorizations at 552 digits are in
> http://physics.open.ac.uk/~dbroadhu/cert/ifacgg1.zip
>
> Notes: I used OpenPFGW, GMP-ECM, Msieve, ggnfs, Pari-GP.
> All primality proofs were performed by Pari-GP.
> The primality proof for p552b is easy, since
> we know the factorization of p552b - 1 = (N + 4)/2.
> The composite numbers
> c542 = (N - 1)/(5*53*151*259499)
> c524 = (N + 9)/(5*7*31*37*288232349*593280102498871)
> are unlikely to have any prime divisor less than 10^30.
> This particular constellation was studied because
> p539 = (N + 10)/(2*3*60647*24846803)
> is prime. Thus a complete factorization of N + 9
> would have yielded 11 consecutive factorizations.
>
> David Broadhurst, Armistice Day, 2009
>

--- In primeform@yahoogroups.com,
"Jens Kruse Andersen" <jens.k.a@...> wrote:

> Congratulations on retaking the record for k=9.

The k=10 record, by Joe and Michael (the brothers Crump)
is rather intriguing: it has too *much* algebraic factorization.

In essence, they proceed from the observation that
x^2*(2*x^2-5)^2 - n is algebraically factorizable for
8 of the 10 values n=0...9 :

  for(n=0,9,f=factor(x^2*(2*x^2-5)^2-n)[,1]~;if(#f>1,print([n,f])))
[0, [x, 2*x^2 - 5]]
[1, [2*x^3 - 5*x - 1, 2*x^3 - 5*x + 1]]
[2, [x^2 - 2, 2*x^2 - 4*x + 1, 2*x^2 + 4*x + 1]]
[3, [x^2 - 3, 2*x^2 - 2*x - 1, 2*x^2 + 2*x - 1]]
[4, [2*x^3 - 5*x - 2, 2*x^3 - 5*x + 2]]
[6, [2*x^2 - 3, 2*x^4 - 7*x^2 + 2]]
[8, [2*x^2 - 1, 2*x^4 - 9*x^2 + 8]]
[9, [x - 1, x + 1, 2*x^2 - 2*x - 3, 2*x^2 + 2*x - 3]]

The factorizations for n=0,2,3,9 involves terms with
no more than 33% of the digits of the target.
So if you are prepared to run SNFS up to (say) 200
digits (with a suitable cubic for x) you can reach
600 digit targets, in these cases, as they remark.

The factorizations for n=6,8 are useful: they reduce
the digits in the GMP-ECM part of the work from 600
to 400 digits, for these two targets.

But then comes the snag: the factorizations for n=1,4
are strongly counterproductive: each splits a 600-digit
target into a pair of 300-digit targets. It is clearly
much harder, on average, to achieve complete factorizations
of a pair of numbers of length L digits than for a single
number of length 2L. Suppose that you are prepared to
run ECM to a depth of d << L digits. Then the probability
of factorizing both parts, each with length L, is

P_both = (exp(Euler)*d/L)^2

while the probability of factorizing a target with
no algebraic factorization is

P_single = exp(Euler)*d/(2*L)

This hang-up happens twice, at n=1 and n=4.
Hence the "penalty" for too much algebraic factorization
is an *inefficiency* by a factor of roughly

(P_single/P_both)^2 = (exp(-Euler)*L/(2*d))^2

With, say, L=300 and d=30, this is a factor of about 8.

So the challenge in polynomial selection is this:
to get 4 good multi-SNFS targets (here at n=0,2,3,9)
plus a pair of GMP-ECM easements (here at n=6,8)
without paying the (say) 8-fold penalty for a
pair of counterproductive factorizations (here at n=1,4).

It's a neat puzzle, to which I have, as yet, no solution.

In any case, I am staying, at present, with my
"25% or 100%" strategy, based on Prouhet-Tarry-Escott,
for 8 or 9 consecutive factorizations, as in

http://users.cybercity.dk/~dsl522332/math/consecutive_factorizations.htm

David (with thanks to Jens and Joe, for stimulus)

David Broadhurst wrote:
> These 9 consecutive factorizations at 552 digits are in
> http://physics.open.ac.uk/~dbroadhu/cert/ifacgg1.zip

Congratulations on retaking the record for k=9. I have updated
http://users.cybercity.dk/~dsl522332/math/consecutive_factorizations.htm

I have been less fortunate in a retaking attempt.
The Prime Pages database has lots of primes next to a completely
factored number.
Before the 100355-digit twin prime record in August I had the record
for k=3 with prp's allowed, by testing many known primes and finding
a third factorization with a prp cofactor.
After the twin record I have attempted this with enough primes above
100355 digits to get more than 90% chance of success, but no luck.
I have run out of candidates of a form and size I am willing to test,
but I expect to try again later when more primes have been submitted.

--
Jens Kruse Andersen

Congratulations!  That seems to be good enough to take back the record.

- Michael


--- In primeform@yahoogroups.com, "djbroadhurst" <d.broadhurst@...> wrote:
>
> Let
>
> x = (1320*(10^20 + 13065906))^3
> y = (x*(5*x + 9)/2 - 31)^2
> N = (y - 23^2)*(y - 24^2)/55440 - 7
>
> then
>
> p544  =  N/(2^2*85580203)
> p552a = (N + 1)/3
> p546  = (N + 2)/(2*7^2*16127)
> p540  = (N + 5)/(223*9887*252181)
> p552b = (N + 6)/2
> p533  = (N + 8)/(2^2*9479*90863*15503173813)
>
> are prime. Moreover N + 3, N + 4 and N + 7 are completely
> factorized, with no prime factor having more than 128 digits.
> These 9 consecutive factorizations at 552 digits are in
> http://physics.open.ac.uk/~dbroadhu/cert/ifacgg1.zip
>
> Notes: I used OpenPFGW, GMP-ECM, Msieve, ggnfs, Pari-GP.
> All primality proofs were performed by Pari-GP.
> The primality proof for p552b is easy, since
> we know the factorization of p552b - 1 = (N + 4)/2.
> The composite numbers
> c542 = (N - 1)/(5*53*151*259499)
> c524 = (N + 9)/(5*7*31*37*288232349*593280102498871)
> are unlikely to have any prime divisor less than 10^30.
> This particular constellation was studied because
> p539 = (N + 10)/(2*3*60647*24846803)
> is prime. Thus a complete factorization of N + 9
> would have yielded 11 consecutive factorizations.
>
> David Broadhurst, Armistice Day, 2009
>

Let

x = (1320*(10^20 + 13065906))^3
y = (x*(5*x + 9)/2 - 31)^2
N = (y - 23^2)*(y - 24^2)/55440 - 7

then

p544  =  N/(2^2*85580203)
p552a = (N + 1)/3
p546  = (N + 2)/(2*7^2*16127)
p540  = (N + 5)/(223*9887*252181)
p552b = (N + 6)/2
p533  = (N + 8)/(2^2*9479*90863*15503173813)

are prime. Moreover N + 3, N + 4 and N + 7 are completely
factorized, with no prime factor having more than 128 digits.
These 9 consecutive factorizations at 552 digits are in
http://physics.open.ac.uk/~dbroadhu/cert/ifacgg1.zip

Notes: I used OpenPFGW, GMP-ECM, Msieve, ggnfs, Pari-GP.
All primality proofs were performed by Pari-GP.
The primality proof for p552b is easy, since
we know the factorization of p552b - 1 = (N + 4)/2.
The composite numbers
c542 = (N - 1)/(5*53*151*259499)
c524 = (N + 9)/(5*7*31*37*288232349*593280102498871)
are unlikely to have any prime divisor less than 10^30.
This particular constellation was studied because
p539 = (N + 10)/(2*3*60647*24846803)
is prime. Thus a complete factorization of N + 9
would have yielded 11 consecutive factorizations.

David Broadhurst, Armistice Day, 2009