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

All of the posted codes are wrong:
[code]
nextprime(x): finds the smallest pseudoprime (see ispseudoprime) greater than or equal
to x.
[/code]
And there is a large conjectured table also: [URL="http://www.research.att.com/~njas/sequences/A005235"]http://www.research.att.com/~njas/sequences/A005235[/URL] for the first 2000 terms.
And [URL="http://www.research.att.com/~njas/sequences/A055211"]http://www.research.att.com/~njas/sequences/A055211[/URL] for the other sequence.

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.

[QUOTE=R. Gerbicz;160636]All of the posted codes are wrong:
[code]
nextprime(x): finds the smallest pseudoprime (see ispseudoprime) greater than or equal
to x.
[/code][/QUOTE]I already said that. Where is my code wrong?

[QUOTE=fivemack;160627]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.
[/QUOTE]

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.

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:[code]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()
)
);[/code]The code runs in sub 100ms, and goes through 4792 iterations.

The first output from it is:[code]iter = 350
prime = 2357
digits = 1000[/code]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 [url=http://www.research.att.com/~njas/sequences/b005235.txt]this table[/url].

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.

How do you make pari log the probable primes?

[QUOTE=Joshua2;160684]How do you make pari log the probable primes?[/QUOTE]

[code]\\ 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[/code]

Thanks! Does anyone know if the [URL="http://groups.google.com/group/sci.math/browse_thread/thread/67d2f5d465ebea47#"]proof [/URL] or same [URL="http://mathforum.org/kb/thread.jspa?forumID=13&threadID=1891175&messageID=6585430#6585430"]here[/URL] is true? I can't follow it myself. Also has anyone heard my generalized conjecture before?

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

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?

[QUOTE=Joshua2;160684]How do you make pari log the probable primes?[/QUOTE][QUOTE=CRGreathouse;160694][code]\\ 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[/code][/QUOTE]To make it easier to read into Pari again later, I'd write it like so:[code]write("C:/trip/probprime.txt","probprime=",q,";");[/code]If you were writing a lot of these files, you might also wish to include the number of the iteration in the file name.

[QUOTE=Joshua2;160706]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?[/QUOTE]

I haven't tried to check it. Can you give a precise statement of that, please? "For each positive integer k, ..."

Let q(x) be the next prime after x. q(x) - k Primorial(n) is prime for all positive integer n and k. For some k, the sequence will have a 9 within the first few terms, afterwhich all will be prime. That second sentence needs some refining probably by some additional testing or math analysis. I have checked k up to 2500 for the first 50 terms, and sometimes the 1st, 2nd, or 3rd produced 9, after which all were primes. Testing out randomly at large k being several million, or trillion, I came across two values which produced 9 on the 4th iteration.
EDIT:It seems my value of always 9 is not true, but I think that maybe the function needs to stabilze for a few values to produce primes.

I'm still having a little trouble with your statement. What's x in "q(x)"? And the value 1 is very common; I assume you meant to include it. Here's what I assume your conjecture to be:
"Let q(x) be the next prime after x and Q(x) = q(x) - x.
1. For all positive integers n and k, Q(k * primorial(n)) is prime, 1, or 9.
2. For all positive integers k, there is some N such that for all n > N, Q(k * primorial(n)) is prime or 1."


Part 2 can have no finite counterexample. The counterexamples I found to part 1 are
2# * {263, 446, 536, 565, 568, ...}
3# * {413, 523, 717, 806, 922, ...}
5# * {2018, 2736, 3679, 4988, ...}
7# * {48907, 60997, 76102, 95354, ...}
11# * {100284, 169695, 188919, ...}
13# * {869700, 9452087, ...}

I expect that for each value of n there are infinitely many counterexamples.

Another small problem is that pari's implementation of APRCL takes really quite a lot of memory; about 600M for a 2000-digit number, and a little over 4G for a 3000-digit one.

I think this is a rather uninteresting problem, since by construction K = nextprime(p#)-p# must be prime if it's less than p^2, and for it to be greater than p^2 would mean you had a very unusually large gap between primes (p# is roughly e^p, so it'd be a gap of O(log(N)^2) between primes near a number of size N; this is about what one of the conjectures mentioned in [url]http://www.ieeta.pt/~tos/gaps.html[/url] gives as the size of the largest-ever gap between primes up to N, but it would be very odd for such a largest-ever gap to be of the very special form of fortunate numbers.

[QUOTE=fivemack;160748]this is about what one of the conjectures mentioned in [url]http://www.ieeta.pt/~tos/gaps.html[/url] gives as the size of the largest-ever gap between primes up to N, but it would be very odd for such a largest-ever gap to be of the very special form of fortunate numbers.[/QUOTE]

Right. If the maximum prime gap ~ (log x)^2 then almost certainly all fortunate numbers are prime. On the other hand, there seems to be at least a shred of a possibility that there are composite fortunate numbers is the maximum prime gap ~ 2/e^gamma (log x)^2.

[QUOTE=fivemack;160748]
I think this is a rather uninteresting problem, since by construction K = nextprime(p#)-p# must be prime if it's less than p^2, and for it to be greater than p^2 would mean you had a very unusually large gap between primes.[/QUOTE]

I follow the rest of the argument, but I don't see why it must be prime or why greater than p^2 would mean a large prime gap.

As well, I believe you have both my conjecture and the fortunate conjecture misinterpreted, because neither one can produce 1 as the output (see below post). It is nextprime(p#+1) for the fortunate conjecture or nextprime(Kp#+1) for mine.

Edit: because the next number would be even after the +1 term, it could be stated as +2 instead to make it odd as in nextprime(p#+2).

[QUOTE=CRGreathouse;160742]I'm still having a little trouble with your statement. What's x in "q(x)"? [/QUOTE]

q is the nextprime function, so x is any integer.

[QUOTE=CRGreathouse;160742]
And the value 1 is very common; I assume you meant to include it. Here's what I assume your conjecture to be:
"Let q(x) be the next prime after x and Q(x) = q(x) - x.
1. For all positive integers n and k, Q(k * primorial(n)) is prime, 1, or 9.
[/QUOTE]
There shouldn't be any value of 1, because q(x) is next prime after x+1.

So, the Jordan generalized Fortune conjecture. Let q(x) be the next prime after x+1, and Q(x) = q(x) - x. For all positive integers k and n positive integers ten or greater (i'm thinking better is n integer greater than ceiling(log k)), Q(k*primorial(n)) is prime.

k=1 would be the fortune conjecture, with n any positive integer.

I discovered k = 9.99999 x 10 ^ 87 + 1 took nine terms to stabilize to primes.

[QUOTE=Joshua2;160759]q is the nextprime function, so x is any integer.[/QUOTE]

You write:
"Let q(x) be the next prime after x. q(x) - k Primorial(n) is prime for all positive integer n and k."

I think you mean:
"Let q(x) be the next prime after x. q(k Primorial(n)) - k Primorial(n) is prime for all positive integer n and k."

That's what I meant when I wrote "What's x in 'q(x)'?", and why I defined Q(x) to avoid the issue.

[QUOTE=Joshua2;160759]There shouldn't be any value of 1, because q(x) is next prime after x+1.[/QUOTE]

Once again, this comes from not defining terms carefully enough. :razz: I'm using Pari, and in Pari nextprime(x) is the smallest prime greater than or equal to x. Thus nextprime(6) = nextprime(7) = 7.

If you look at my pari, I have nextprime(x+2 or x+3) (pari's notation is somehow equivalent to actually x+1 or x+2). nextprime(6+1) = 11. The smallest possible value is 3, which is the first term of the fortunate series. So I guess I need to change to:

Let q(x) be the next prime after x, and Q(x) = q(x+2) - x. The rest is good as is.

k = 44 took two terms to stabilize (first term was 9).
k= 221 took three.
k=2018 took four
k = 47867 took five.
k= 100284 took six
k = 9.99999 x 10 ^ 87 + 1 took 9 terms to stabilize to primes.
k = 9.999 x 10 ^ 118 + 234 took 10 terms to stabilize.
k= 9 x 10 ^ 173 + 81 took 12 terms

So it seems that I need as k tends to infinity it would take more and more terms. However, 99.9% at least seem to work for all n and not need to stabilize. So I need something like "For all positive integers k and n integer greater than log k, Q(k*primorial(n)) is prime, where Q(x) = q(x+2) - x.

Sorry, I missed your program.

In any case, I don't think I'll be doing any more checking of this conjecture. I think when you say Primorial(9) you mean what I mean by 23# = 223092870, and checking for k that cause problems there would take a lot of crunching (in the petatick range, or several weeks on my computer).

Yes, I by primorial 9 i meant the first 9 primes multiplied together. You don't necessarily need to check there at 9 now that I changed my conjecture to not use nine. Instead of the first saying n starting at 9, see previous post it is log k. So if you are trying k's with a ten digits you might need ones that large, but there are plenty of k's and n's to check that are fast. I am doing some right now and it is churning. Do you still believe my conjecture is related to the size of prime gaps? And if so could you help me understand how?

[QUOTE=Joshua2;160769]So if you are trying k's with a ten digits you might need ones that large, but there are plenty of k's and n's to check that are fast. I am doing some right now and it is churning.[/QUOTE]

Yes, but to find a counterexample to the log k version of your conjecture you need to find very special numbers which means examining a lot. If there was a counterexample it would take a lot of effort to find. Finding one point is easy... finding a trillion is hard.

[QUOTE=Joshua2;160769]Do you still believe my conjecture is related to the size of prime gaps?[/QUOTE]

Of course. If all prime gaps are small, then Q = nextprime(k * p# + 2) - k * p# is small. In particular, if all prime gaps are <= a * log(k * p#)^2 then Q <= 1 + a * log(k * p#)^2 = 1 + a * (log k + log p#)^2 ~ a * (log k + p)^2. Remember that if Q < p^2 it is prime...

Further, if p must be at least the kth prime, then p > k log k and so Q = O(p^2).

Couter examples:[code]k=3829584908031798; \\ second iter
k=3829584908031800; \\ fourth iter
k=3829584908031801; \\ first and fourth iter
k=3829584908031803; \\ fourth iter[/code]The first number is the odd one out here I believe, since it is an unintended counter-example. I aimed for the fourth terms to fall into the prime gap listed as number one in the table [url=http://www.ieeta.pt/~tos/gaps.html]here[/url]. However, for the first counter example, k*7# falls just short of the prime gap. Instead it is for the second iteration that Q(x) randomly happens to not be prime.

Edit: There should be yet more counter examples for 26,807,094,356,222,589 < k < 26,807,094,356,222,637 for the third iteration.

Another edit: k=26807094356222590; is a juicy one, first, third and fourth iteration.

[QUOTE=CRGreathouse;160782]Yes, but to find a counterexample to the log k version of your conjecture you need to find very special numbers which means examining a lot. If there was a counterexample it would take a lot of effort to find. Finding one point is easy... finding a trillion is hard.
[/quote] I don't see the trillion point thing. It would still only take one counterexample to prove my conjecture wrong, and I actually found one, when I get home I can post it. I thought of a way to change my conjecture to make it work though.

[QUOTE=CRGreathouse;160782]
If all prime gaps are small, then Q = nextprime(k * p# + 2) - k * p# is small. In particular, if all prime gaps are <= a * log(k * p#)^2 then Q <= 1 + a * log(k * p#)^2 = 1 + a * (log k + log p#)^2 ~ a * (log k + p)^2.[/QUOTE]
I follow that.
[QUOTE=CRGreathouse;160782] Remember that if Q < p^2 it is prime...[/QUOTE] I remember it was said, I don't see how it is true. And what if Q >= p^2?

[QUOTE=CRGreathouse;160782]
Further, if p must be at least the kth prime, then p > k log k and so Q = O(p^2).[/QUOTE]
p must be greater than (log k)th prime I believe actually, which makes the problem significantly easier. With the big O notation, is that how fast the problem grows, so hard it is computationally right? I didn't follow how you got it, but it should be different using the (log k)th prime.

[QUOTE=lavalamp;160786]Couter examples:[code]k=3829584908031798; \\ second iter
k=3829584908031800; \\ fourth iter
k=3829584908031801; \\ first and fourth iter
k=3829584908031803; \\ fourth iter[/code][/QUOTE]
That's cool how you found these with prime gaps. I believe they don't invalidate my conjecture, because I was saying n>log k, which would mean the error would need to be in the 16th term or greater to invalidate. If you look at my previous posts I found some errors of the fourth term (and other with much smaller k values, and even a error in the 11th term with a big number.) Last night I found a number with 6 digits that had an error on the 7th term, which invalidates my conjecture. To fix it, I have to say instead of n>log k, n>(log(k)+1).

[QUOTE=Joshua2;160865]I remember it was said, I don't see how it is true.[/QUOTE]

Suppose Q has a prime factor <= p, call it r. Then r divides p# (because p# = p * ... * r * ... * 5 * 3 * 2) so r divides k * p# + Q. Thus k * p# + Q is composite. So if k * p# + Q is prime, Q has no prime factors <= p. And if Q has no prime factors <= p and Q < p^2, Q is prime. (In fact if Q < nextprime(p + 1)^2 then Q is prime.)

This is basic stuff.

[QUOTE=Joshua2;160865]And what if Q >= p^2?[/QUOTE]

The point of the analysis is to show that it's very hard for that to happen. If it does, Q is much more likely to be prime than a number of its size. For example, if p = 23, the 'probability' that Q is prime is about 6.1 / log Q rather than 1 / log Q.

[QUOTE=Joshua2;160865]p must be greater than (log k)th prime I believe actually, which makes the problem significantly easier. With the big O notation, is that how fast the problem grows, so hard it is computationally right? I didn't follow how you got it, but it should be different using the (log k)th prime.[/QUOTE]

Sorry, my mistake. The result still holds in that case: Q = O(p^2).

This has nothing to do with "hard it is computationally". It says that Q is 'about at most' p^2. Google "Big O notation" for a precise definition.

Q (869700 p(6th prime)) = 291, not prime. That is quite a large prime gap, and disproves my conjecture of log k. I believe the conjecture works revised to log k + 1.
k=23094906 7th was bad
k=272703171 8th was bad.
I searched for the first occurences of each bad term. It appears to be exponential doesn't it?