Re: Old question: looking for prime number list > 1,000,000

Ronald Bruck <bruck@xxxxxxxxxxxxxxxxx> writes:
> In article <1136070047.312541.171560@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
> rich burge <r3769@xxxxxxx> wrote:
>
> > Robert Israel wrote:
> > > In article <1135797694.699111.277250@xxxxxxxxxxxxxxxxxxxxxxxxxxxx>,
> > > Christian Drewing <christian.drewing@xxxxxxxxxxxxxx> wrote:
> > >
> > > >I spent hours on Google but I couldnt find a list with prime numbers >
> > > >1,000,000.
> > > >So is there a list with all known prime numbers on the net? Clearly
> > > >written, not in powers of 2.
> > >
> > > What counts as a "known" prime number? Is 156593416582327342765171
> > > known? I guess it is now, but it wasn't 5 minutes ago.
> >
> > I would say the is prime above is "known" if one can produce the n s.t.
> > p_n=156..171.
>
> Or you can print a "certificate" of primality. Mathematica says
>
> {156593416582327342765171, 2, {2, {3, 2, {2}}, {5, 2, {2}}, {293,
> 2, {2, {73, 5, {2, {3, 2, {2}}}}}}, {2521, 17, {2, {3, 2, {2}},
> {5, 2, {2}}, {7, 3, {2, {3, 2, {2}}}}}}, {7066620663212963,
> 2, {2, {19, 2, {2, {3, 2, {2}}}}, {3407, 5, {2, {13, 2, {2,
> {3, 2, {2}}}}, {131, 2, {2, {5, 2, {2}}, {13, 2, {2, {3,
> 2, {2}}}}}}}}, {54582829957, 2, {2, {3, 2, {2}}, {19, 2, {2,
> {3, 2, {2}}}}, {3329, 3, {2, {13, 2, {2, {3, 2, {2}}}}}},
> {23971, 10, {2, {3, 2, {2}}, {5, 2, {2}}, {17, 3, {2}},
> {47, 5, {2, {23, 5, {2, {11, 2, {2, {5, 2,
> {2}}}}}}}}}}}}}}}}
>
> is such. See V. Pratt, "Every prime has a succinct certificate", SIAM
> J. of Comp. 4 (1975) 214--220.


Yuck. Trees are wasteful, use a DAG instead.

? print(isprime(156593416582327342765171,1))
[2, 2, 1; 3, 2, 1; 5, 2, 1; 293, 2, 1; 2521, 2, 1; 7066620663212963, 2, [2, 2, 1; 19, 2, 1; 3407, 2, 1; 54582829957, 2, 1]]

Even that's wasteful. 156593416582327342765171's primality can be made
contingent on only that of 20872498081 by using BLS, which in turn can
be made contingent solely on the primality or 2,3,5, and 7, again using
BLS.

I was just about to add that this number appears to be unusually
succint, but decided that I should check to see how unusual it
is...

? nextprime(156593416582327342765171+1)
156593416582327342765187
? print(factor(156593416582327342765187+1))
[2, 2; 3, 1; 15712496819, 1; 830514178121, 1]
? print(factor(15712496819+1))
[2, 2; 3, 2; 5, 1; 9343, 2]
? print(factor(9343+1))
[2, 7; 73, 1]

So 156593416582327342765187 is contingent on 15712496819
which is contingent on 2, 3, 5, and 9343 which in turn
is contingent on only 2.

The next prime, 156593416582327342765267, is contingent on
2, 11, 23, and 30839, which in turn is contingent on 2, 3,
and 5.

So the first number wasn't unusually succinct at all, it
appears. Using a Lenstra proof rather than a BLS proof
(which is _faster_) one could toy around even more with
the choice of factors (I simply took the best subset of
all the N+1's or the best subset of all the N-1's), and
aim for an even more succint certificate.


Phil
--
What is it: is man only a blunder of God, or God only a blunder of man?
-- Friedrich Nietzsche (1844-1900), The Twilight of the Gods
.

Relevant Pages