Wish I paid more attention at school...
 

To go straight to the point:

What is the expected number of primes between two n values for primes of the form k*2^n+1? Assume k is insignificant.

Feels like it is really basic, but I'm failing to search for it. Trying to work it out myself isn't going anywhere fast.

I'm kinda relearning things as I go along. At first I had a go at using pi(x) approximation, making Excel explode from asking it to do 10^(big number), remembering how to use logs, before I realised that was probably giving me all primes, not just ones of the form above. So that was out.

The alternative route of using 1/log x for the probability seemed more reasonable, but I'm not good enough to integrate it over a range. Taking a number of the magnitude of 2^1.5M for example, that is approximately 10^450k, so probability would be 1/450k? Which sounded really low, but I suppose I then have to factor in how many candidates would be removed by sieve.

Why am I doing this? I have a "spare" computer that is offline. I thought I'd have a go sieving a range and finding top5k primes with it. I picked a fun k, checked no one else had reported primes on it, and let it go. I started with the n range 1.5M-10M as big enough to be t5k reportable. After... a lot of time, no primes found. Then I started getting worried, what if this was one of those k where no primes are found until really high n? Or am I doing something else wrong? So I did a quick sieve on n<1.5M and started testing it. Primes a plenty. Tiny primes, but primes none the less. So I'm wondering what's the estimated number of primes in that 1.5M-10M range?

I don't know if there is any clever formula. But here is how you (I) do it (the hard way):

Sum up the probabilities of the candidates that survived sieving, where Prob(k*2^n+1) = 1/ln(k*2^n+1) ~= 1/(n*ln(2))

Multiply the sum by the sieve factor. sieve factor = 1.781 * ln(p), where p is the sieve depth (maybe in the range 10^9 - 10^15)

That will give you the expected number of primes in that range.

EDIT:- All calculations uses natural logarithm.

After a moment of quiet reflection, I am assuming that k is divisible by at least one odd prime. There is a condition on the possible prime factors p of k*2^n + 1:

k*2^n == -1 (mod p)

2^n == (-k)^(-1) (mod p)

znorder(Mod(-k,p)) divides znorder(Mod(2,p))

I have no idea how to determine, for a given k, which primes p are eliminated as possible factors, except by evaluating multiplicative orders for each individual p.

I note that, in the exceptional case k = 1, the condition eliminates all primes p congruent to 7 (mod 8) from consideration.

axn, I feel another spreadsheet coming on with what you described. Also natural log is used in the examples I mentioned earlier for pi(x) and the probability of any number being prime? So I would have some error there from using log10 for example.

Dr Sardonicus that is hitting above my level. If it makes any difference I just checked and the k I picked is apparently prime.

[QUOTE=mackerel;528292]Also natural log is used in the examples I mentioned earlier for pi(x) and the probability of any number being prime? So I would have some error there from using log10 for example.[/QUOTE]

Yes, indeed. It is very rare to see anything other than natural log in prime number math.

I use a heuristic method, since the frequency of primes depends so strongly on the choice of k (thus, "high weight" and "low weight" k values).

I count the number of primes from n=1000 to 10000, then 10k to 100k, then 100k to 1M. I expect the number of primes from 1M to 10M to be similar to those counts.

Example, k=13: 4 primes in 1k-10k, 7 in 10k-100k, 2 in 100k-1M. So, I "expect" 4 or 5 primes from 1M-10M. I've tested to about 4.4M so far, and gotten rather lucky with 6 primes over 1M.

Example 2: k=99: 13 primes in 1k-10k, 12 primes in 10k-100k, 10 primes in 100k-1M. So, I "expect" 11 primes in 1M-10M. I've tested to about 3.1M, with 9 primes found (seems a bit lucky too).

[QUOTE=VBCurtis;528333]I use a heuristic method, since the frequency of primes depends so strongly on the choice of k (thus, "high weight" and "low weight" k values).
<snip>[/QUOTE]
Perhaps the "weight" of k has to do with [i]really small[/i] primes which can't divide k*2^n + 1. These include (1) prime divisors of k, and (2) small primes p not dividing k for which znorder(Mod(-k,p)) does not divide znorder(Mod(2,p)).

With k = 99, none of the values k*2^n + 1 are divisible by 3, 7, or 11.

With k = 13, there are values of k*2^n + 1 divisible by each of these primes.

A somewhat analogous phenomenon occurs with (usually monic) quadratic polynomials in Z[x]. If the discriminant D is a quadratic non-residue of a prime, that prime can't divide evaluations of the polynomial for integer values of x. If D is a quadratic non-residue modulo a bunch of small primes, the polynomial seems to be "rich" in prime evaluations.

[QUOTE=Dr Sardonicus;528345]Perhaps the "weight" of k has to do with [i]really small[/i] primes which can't divide k*2^n + 1.[/QUOTE]
Indeed. But it is not just [B]which[/B] small primes divide, but also whether they are "in sync" or "out of sync". Sierpinski numbers are extreme cases with zero weight.

I should note that my example k's are Riesel: k*2^n - 1, rather than +1.
Luckily, that doesn't change the heuristic.

[QUOTE=VBCurtis;528333]I count the number of primes from n=1000 to 10000, then 10k to 100k, then 100k to 1M. I expect the number of primes from 1M to 10M to be similar to those counts.[/QUOTE]

Finally sat down and counted the primes in the tested ranges so far...

n-range, prime count
10-100: 2
100-1000: 5
1k-10k: 7
10k-100k: 9
100k-435k: 4
100k-1M extrapolated: 6
1.50M-1.82M: 0

Since the ranges are in constant-log scaling (at least that's how I see it), the 100k-435k range is over half way, but is comparable to the two lower ranges.

For the actual range of interest starting 1.5M, this accounts for just over 8% of the range 1M-10M. Assuming the past scaling still holds, then I'm not "overdue" yet having done roughly 2/3 of the work towards 1st expected prime. This is an interesting way to give perspective on the expected number of primes, and I can now focus my efforts to cover that range faster. I was dabbling with other things on the side too, which can now be killed.

[QUOTE=mackerel;528568]Finally sat down and counted the primes in the tested ranges so far...[/QUOTE]

[QUOTE=mackerel;528292]axn, I feel another spreadsheet coming on with what you described.[/QUOTE]
Did you put together that spreadsheet? Would be interesting to see "predicted" vs actual.