Half way decent fortunate conjecture attack?

[CRGreathouse]

Originally Posted by Joshua2

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.

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.

Originally Posted by Joshua2

Do you still believe my conjecture is related to the size of prime gaps?

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).

[lavalamp]

Couter examples:

k=3829584908031798; \\ second iter
k=3829584908031800; \\ fourth iter
k=3829584908031801; \\ first and fourth iter
k=3829584908031803; \\ fourth iter

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 here. 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.

[Joshua2]

Originally Posted by CRGreathouse

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.

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.

Originally Posted by CRGreathouse

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.

I follow that.

Originally Posted by CRGreathouse

Remember that if Q < p^2 it is prime...

I remember it was said, I don't see how it is true. And what if Q >= p^2?

Originally Posted by CRGreathouse

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

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.

[Joshua2]

Originally Posted by lavalamp

Couter examples:

k=3829584908031798; \\ second iter
k=3829584908031800; \\ fourth iter
k=3829584908031801; \\ first and fourth iter
k=3829584908031803; \\ fourth iter

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).

[CRGreathouse]

Originally Posted by Joshua2

I remember it was said, I don't see how it is true.

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.

Originally Posted by Joshua2

And what if Q >= p^2?

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.

Originally Posted by Joshua2

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.

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.

[Joshua2]

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?