Half way decent fortunate conjecture attack?

[R. Gerbicz]

All of the posted codes are wrong:

nextprime(x): finds the smallest pseudoprime (see ispseudoprime) greater than or equal
to x.

And there is a large conjectured table also: http://www.research.att.com/~njas/sequences/A005235 for the first 2000 terms.
And http://www.research.att.com/~njas/sequences/A055211 for the other sequence.

[fivemack]

isprime() does APRCL tests (as you can tell by running it after doing setdefault(debug,3)); runtime in the up-to-kilodigit range on K8/2200 is fit quite nicely by

10 nanoseconds * (number of digits) ^ 3.63

which suggests (extrapolating horribly) that 6k digits would take about a week on such a system. Better than I'd thought.

I'd install 64-bit Linux rather than trying to compile pari-gp on Vista x64, but this may just be my prejudices showing. There's no point trying to optimise the search code, the isprime() will take the dragon's share (larger than a lion ...) of the time.

[lavalamp]

Originally Posted by R. Gerbicz

All of the posted codes are wrong:

nextprime(x): finds the smallest pseudoprime (see ispseudoprime) greater than or equal
to x.

I already said that. Where is my code wrong?

[Joshua2]

Originally Posted by fivemack

I think you have very much underestimated the sloth of guaranteed primality tests for large general numbers. The product of the first 2000 primes is about 10^7483; checking such a number with a competent parallel implementation of ECPP (NB I don't know if such a thing exists) would take about a week, using gp would take to a fair approximation forever.

I was planning on not doing a deterministic test in order to try and exceed the n=2000 that is already tested. I ran the deterministic test up to 150 or so and it gets slow fast. I thought I might run it and see if any of the probable tests were actually wrong. (I could log the numbers and test them with primo.)

The problem with installing linux is I use this machine for other stuff like school. Maybe in the summer, or I can try messing with dual partition or a live CD or something, but it seems this code is likely to take a month at least.

Do you think it would be reasonable to do this distributed? Or computing the bases take too much duplicate time? It seems the primorials are definetely not the limiting factor here.

[lavalamp]

This could easily be broken up into a distributed project, as testing each term is completely independant of other terms. It takes almost no time at all to calculate the primorial function up to very high levels, in fact I just ran this code to see the iterations where the primorial function has grown by another 1000 digits:

P=1;
k=0;
x=1;

forprime(a=2,500000,
  P*=a;
  k++;
  d=ceil(log(P)/log(10));

  if(d>=x*1000,
    print("iter\t= ",k,"\nprime\t= ",a,"\ndigits\t= ",d,"\n");
    x++
  );

  if(d>=20000,
    break()
  )
);

The code runs in sub 100ms, and goes through 4792 iterations.

The first output from it is:

iter	= 350
prime	= 2357
digits	= 1000

I decided to calculate P to the 350th iteration, then I ran q=nextprime(P+2), which took 49 seconds. I verified it was prime with isprime(q), that took 37 minutes and returned in the affirmative.

q-P=3133 for the 350th iteration, which agrees with this table.

For distribution, perhaps run the project in two stages, the first being calculating values using nextprime only (which would have to be uploaded), the second checking that the output of nextprime is in fact prime. If you ran both projects at the same time, the folks with faster computers could verify with isprime, and the slower computers could advance the list of tentatively fortunate numbers.

I doubt that even distributed, the isprime() side would get much past (or even to) the thousandth iteration though.

[Joshua2]

How do you make pari log the probable primes?

[CRGreathouse]

Originally Posted by Joshua2

How do you make pari log the probable primes?

\\ blah blah blah
if(ispseudoprime(n),
  write("mylogfile.txt","Pari sez that "n" is probably prime.");
  \\ do whatever else you need here
);
\\ blah blah blah

[Joshua2]

Thanks! Does anyone know if the proof or same here is true? I can't follow it myself. Also has anyone heard my generalized conjecture before?

[CRGreathouse]

Maybe I just don't understand it, but as I read it there are lots of counterexamples. Sampler:


5083 - 7! = 43

43 is prime
43 < 7^2
5083 = 13 * 17 * 23

----

17 + 7! = 5057

17 is prime
17 < 7^2
5057 = 13 * 389

----

5043 - 7! = 3

3 is prime
3 < 7^2
5043 = 3 * 41^2

[Joshua2]

So your saying that you don't think that proof is valid. You haven't found any errors with my q-kPrimorial(n) is prime (or the first couple on a few can be 9) have you?

[lavalamp]

Originally Posted by Joshua2

How do you make pari log the probable primes?

Originally Posted by CRGreathouse

\\ blah blah blah
if(ispseudoprime(n),
  write("mylogfile.txt","Pari sez that "n" is probably prime.");
  \\ do whatever else you need here
);
\\ blah blah blah

To make it easier to read into Pari again later, I'd write it like so:

write("C:/trip/probprime.txt","probprime=",q,";");

If you were writing a lot of these files, you might also wish to include the number of the iteration in the file name.