20191018, 10:33  #1 
Feb 2016
UK
2·3·5·13 Posts 
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.5M10M 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.5M10M range? 
20191018, 11:05  #2 
Jun 2003
4719_{10} Posts 
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. Last fiddled with by axn on 20191018 at 11:06 
20191018, 12:25  #3 
Feb 2017
Nowhere
2^{2}×5×179 Posts 
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. 
20191018, 13:03  #4 
Feb 2016
UK
390_{10} Posts 
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. 
20191018, 17:44  #5 
Jun 2003
3·11^{2}·13 Posts 
Yes, indeed. It is very rare to see anything other than natural log in prime number math.

20191019, 03:49  #6 
"Curtis"
Feb 2005
Riverside, CA
1000100110001_{2} Posts 
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 1k10k, 7 in 10k100k, 2 in 100k1M. So, I "expect" 4 or 5 primes from 1M10M. 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 1k10k, 12 primes in 10k100k, 10 primes in 100k1M. So, I "expect" 11 primes in 1M10M. I've tested to about 3.1M, with 9 primes found (seems a bit lucky too). Last fiddled with by VBCurtis on 20191019 at 03:50 
20191019, 12:07  #7  
Feb 2017
Nowhere
2^{2}·5·179 Posts 
Quote:
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 nonresidue of a prime, that prime can't divide evaluations of the polynomial for integer values of x. If D is a quadratic nonresidue modulo a bunch of small primes, the polynomial seems to be "rich" in prime evaluations. 

20191019, 13:20  #8 
Jun 2003
3·11^{2}·13 Posts 

20191019, 13:29  #9 
"Curtis"
Feb 2005
Riverside, CA
3^{3}×163 Posts 
I should note that my example k's are Riesel: k*2^n  1, rather than +1.
Luckily, that doesn't change the heuristic. 
20191022, 10:21  #10  
Feb 2016
UK
2·3·5·13 Posts 
Quote:
nrange, prime count 10100: 2 1001000: 5 1k10k: 7 10k100k: 9 100k435k: 4 100k1M extrapolated: 6 1.50M1.82M: 0 Since the ranges are in constantlog scaling (at least that's how I see it), the 100k435k 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 1M10M. 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. Last fiddled with by mackerel on 20191022 at 10:21 Reason: I don't know my k from my n 

20191022, 10:27  #11  
Jun 2003
3×11^{2}×13 Posts 
Quote:


Thread Tools  
Similar Threads  
Thread  Thread Starter  Forum  Replies  Last Post 
Pay attention please.  a1call  Puzzles  28  20180525 00:03 
School Teachng  davieddy  Lounge  6  20110927 01:20 
Attention vaughan  mdettweiler  No Prime Left Behind  2  20091226 04:23 
Prime Search at School  Unregistered  Information & Answers  5  20091015 22:44 
School's out!  ixfd64  Lounge  15  20050629 13:45 