Half way decent fortunate conjecture attack?
 

I was intrigued by [url]http://primes.utm.edu/glossary/page.php?sort=FortunateNumber[/url] and [url]http://www-lipn.univ-paris13.fr/~banderier/Computations/prime_factorial.html[/url] and I thought I would try a little fortunate computing myself. I made this pari script myself and checked up to k=300. What do you guys think? I thought I might see if I could do it with gmp in 64-bit which should be way faster.

{
p=psum=2;
q=nextprime(p+2);
print(q-p);

for (k=2, 3000,
p=nextprime(p+1);
psum=psum*p;
q=nextprime(psum+2);
print(k);

if(!isprime(q-psum),
print(q-psum);
)
)
}

Running overnight it got to 550. I bet if I increased its memory above 4 megs it would go significantly faster...
To summarize for the people that don't want to read the links, the fortunate series is conjectured to be all prime numbers, and it has been checked to about n=2000, but someone said there might have been a few errors in that result.

I made some optimizations and it seems to be around ~10% faster. Didn't really do official benchmarks.

allocatemem
allocatemem
allocatemem
allocatemem
{
arr=[2, 3, 5, 7, 11, 13, ..., 9973];

psum=1;

for (k=1, 3000,
p=arr[k];
psum=psum*p;
q=nextprime(psum+3);
print(psum+3);
f=q-psum;
print(k " " f);

if(!isprime(f),
print(k);
k=3000;)

);
}

How about just using a forprime(2,10000,...) loop? You can work out in advance which prime you want to stop at, or you could include a counter in the loop and break() it when it reaches a specified point (though this would slow the code down more).

Also, I find that using only 1 letter variables, and in general as fewer characters as possible, helps to speed up the code in Pari/GP.

[QUOTE=lavalamp;160594]How about just using a forprime(2,10000,...) loop? You can work out in advance which prime you want to stop at, or you could include a counter in the loop and break() it when it reaches a specified point (though this would slow the code down more).[/QUOTE]

I don't particularly want to slow the code down more. What is this supposed to do? I'm not exactly sure what you are saying. Is it to not need so many primes in my array at the beginning?

[QUOTE=lavalamp;160594]
Also, I find that using only 1 letter variables, and in general as fewer characters as possible, helps to speed up the code in Pari/GP.[/QUOTE]
Did that now.

It seems most of the time (99%) is spent on the nextprime() method. The primes are ~1400 digits around n=400.

Would anyone care to help me get started with GMP 64-bit? I believe that would significantly increase speed. I downloaded the source. I have visual studio 2008 and vista x64.

Of the two alternatives I gave, only the second would introduce any slow down. Though it would only be very slight, and certainly nowhere near as much as is introduced by printing out a couple of lines worth of progress every iteration.

However, since the loop only gets through very few iterations, you're only losing milliseconds for the print()s, and microseconds for the extra variable being iterated.

A forprime() loop would eliminate the need for the prime array entirely. It is a built in loop in Pari:
[url]http://pari.math.u-bordeaux.fr/dochtml/html/Programming_in_GP:_control_statements.html#forprime[/url]

Here is some sample code that will run through all primes below 1000 (168 iterations):[code]P=1;
k=0;

forprime(a=2,1000,
k++;
P*=a;
q=nextprime(P+2);

if(isprime(q-P)==0,
print(k);
break()
)
);

print("Done ",k," iterations.");[/code]However, since nextprime() only finds the next pseudoprime, it must be verified to prove it's primality with [url=http://pari.math.u-bordeaux.fr/dochtml/html/Arithmetic_functions.html#isprime]isprime()[/url]. If you thought nextprime was slow, just wait until you run this code:[code]P=1;
k=0;

forprime(a=2,1000,
k++;
P*=a;
q=nextprime(P+2);
[color=red]while(isprime(q)==0,
q=nextprime(q+2)
);[/color]

if(isprime(q-P)==0,
print(k);
break()
)
);

print("Done ",k," iterations.");[/code]If you wish to exit after a certain number of iterations, the following will do just that, as well as printing the current progress:[code]l=1000; \\ The number of iterations to run.
P=1;
k=0;

forprime(a=2,500000,
k++;
P*=a;
q=nextprime(P+2);
while(isprime(q)==0,
q=nextprime(q+2)
);

r=q-P;

if(isprime(r)==0,
print("F_k NOT PRIME\nk =\t",k,"\np =\t",a,"\nF_k =\t",r,"\nF_k NOT PRIME\n");
break()
,
print("k =\t",k,"\np =\t",a,"\nF_k =\t",r,"\n")
);

if(k>=l,
break()
)
);

print("Done ",k," iterations.");[/code]Sadly there is little that can be done about the speed of the nextprime/isprime functions. The arguments being passed to them are simply too huge for them to be expected to run quickly.

Cool. I read that this was verified up to n=2000 with mathematica, and n=1300 with maple. Those programs should have been even slower than pari or at least not faster. Maybe they just left it running for a month or two. I was hoping to raise the bounds of how far it had been proved. It seems 64-bit would be my best speedup.

I am also considering various other conjectures. Instead of starting with P=1 as in yours, start with 2, 3, or whatever. I have tried up to 40 for the first 100 or so iterations and they are all prime as well. This isn't obvious is it?

Edit: I discovered a couple P starting values (both odd and even) that result in the first number of the series being 9, after that the series appear to be all primes.
Edit2: P=221 2nd number is 9, then fine. Up to P=2000 ignoring cases where the first or 2nd is 9.
Edit3: P=2018 3rd is 9. Maybe these things can't produce anything but prime or 9? Randomly testing way out 150064 4th is 9.

The code I posted actually starts with P=2, it's just that I initialise it to 1, then on the first iteration the value is set to P=P*2, so P=2 for the first iteration. The next it is set to P=P*3, so P=6, and so on.

If you want to start with a different value, the simply change the first number in the forprime loop, eg:[code]forprime(a=[color=red]7[/color],500000,
[/code]That would start at 7 instead of 2.

As far as compiling the code, GP2C would probably be worth a look. The site claims that code runs 3 to 4 times faster that way.
[url]http://pari.math.u-bordeaux.fr/pub/pari/manuals/gp2c/gp2c.html[/url]

I don't think that GMP contains any deterministic primality tests, so if you were to go the GMP route, you would have to either write your own implementation, or else find an open source one from somewhere (such as Pari for instance :wink:). However, I could be mistaken about GMP there.

467 is the first iteration to cross into 1400+ digits by the way.

That code you gave seems a lot slower. 15s to get to k=75, whereas mine gets to k=100 in 4.5s. It appears to be all that isprime to check the nextprime.

Unfortunately, gp2c seems to require linux, at least that tutorial is for linux. I can't just type make or do links with ln on vista :).

What I'm talking about with the P thing, called i currently on my version, is a multiplier on the primorial. Instead of 1*2*3*5*7*11... have 2*2*3*5*7 or P*2*3*5*7. Where P is 100 or 100000 or whatever. I tried having P being restricted to prime numbers, but I am still coming up with the first term being 9 or 2nd, 3rd, extra as P gets large. After it gets the 9 out of its system it seems to be fine.

I might call something like this the Jordan generalized Fortune conjecture :)
Let P be the product of the first n primes. If q is the smallest prime greater than kP+1, then q-kP is prime or 9 (or instead prime after n is sufficiently large).

[QUOTE=lavalamp;160610]

I don't think that GMP contains any deterministic primality tests[/QUOTE]

All previous work so far has not been deterministic.

"However, all of them are probabilistic tests (Mathematica uses multiple Rabin-Miller and Lucas, Pari GP uses Baillie-Pomerance-Selfridge-Wagstaff and Lucas) and the best known deterministic test is about 1000 times slower."

I'm not sure if the slowdown is worth it or not. I suppose I'll do some of each.

I attached the pari of the your program modified to test the generalized conjecture.

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.

for(c=10,20,print(nextprime(c*10^A)-c*10^A))
(eg eleven sets of {some probably-primality tests + one true-primality})
takes on 2.4GHz core2

[code]
A= 999 222 seconds
A=1499 880 seconds
A=1999 2290 seconds
A=2499 5404 seconds
A=2999 8870 seconds
[/code]

so a bit worse than cubic