mersenneforum.org  

Go Back   mersenneforum.org > Great Internet Mersenne Prime Search > Math

Reply
 
Thread Tools
Old 2019-10-18, 10:33   #1
mackerel
 
mackerel's Avatar
 
Feb 2016
UK

2·3·5·13 Posts
Default 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?
mackerel is offline   Reply With Quote
Old 2019-10-18, 11:05   #2
axn
 
axn's Avatar
 
Jun 2003

471910 Posts
Default

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 2019-10-18 at 11:06
axn is online now   Reply With Quote
Old 2019-10-18, 12:25   #3
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22×5×179 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Old 2019-10-18, 13:03   #4
mackerel
 
mackerel's Avatar
 
Feb 2016
UK

39010 Posts
Default

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.
mackerel is offline   Reply With Quote
Old 2019-10-18, 17:44   #5
axn
 
axn's Avatar
 
Jun 2003

3·112·13 Posts
Default

Quote:
Originally Posted by mackerel View Post
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.
Yes, indeed. It is very rare to see anything other than natural log in prime number math.
axn is online now   Reply With Quote
Old 2019-10-19, 03:49   #6
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

10001001100012 Posts
Default

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

Last fiddled with by VBCurtis on 2019-10-19 at 03:50
VBCurtis is offline   Reply With Quote
Old 2019-10-19, 12:07   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

22·5·179 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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>
Perhaps the "weight" of k has to do with really small 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.
Dr Sardonicus is offline   Reply With Quote
Old 2019-10-19, 13:20   #8
axn
 
axn's Avatar
 
Jun 2003

3·112·13 Posts
Default

Quote:
Originally Posted by Dr Sardonicus View Post
Perhaps the "weight" of k has to do with really small primes which can't divide k*2^n + 1.
Indeed. But it is not just which small primes divide, but also whether they are "in sync" or "out of sync". Sierpinski numbers are extreme cases with zero weight.
axn is online now   Reply With Quote
Old 2019-10-19, 13:29   #9
VBCurtis
 
VBCurtis's Avatar
 
"Curtis"
Feb 2005
Riverside, CA

33×163 Posts
Default

I should note that my example k's are Riesel: k*2^n - 1, rather than +1.
Luckily, that doesn't change the heuristic.
VBCurtis is offline   Reply With Quote
Old 2019-10-22, 10:21   #10
mackerel
 
mackerel's Avatar
 
Feb 2016
UK

2·3·5·13 Posts
Default

Quote:
Originally Posted by VBCurtis View Post
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.
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.

Last fiddled with by mackerel on 2019-10-22 at 10:21 Reason: I don't know my k from my n
mackerel is offline   Reply With Quote
Old 2019-10-22, 10:27   #11
axn
 
axn's Avatar
 
Jun 2003

3×112×13 Posts
Default

Quote:
Originally Posted by mackerel View Post
Finally sat down and counted the primes in the tested ranges so far...
Quote:
Originally Posted by mackerel View Post
axn, I feel another spreadsheet coming on with what you described.
Did you put together that spreadsheet? Would be interesting to see "predicted" vs actual.
axn is online now   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Pay attention please. a1call Puzzles 28 2018-05-25 00:03
School Teachng davieddy Lounge 6 2011-09-27 01:20
Attention vaughan mdettweiler No Prime Left Behind 2 2009-12-26 04:23
Prime Search at School Unregistered Information & Answers 5 2009-10-15 22:44
School's out! ixfd64 Lounge 15 2005-06-29 13:45

All times are UTC. The time now is 11:10.

Thu Oct 29 11:10:37 UTC 2020 up 49 days, 8:21, 1 user, load averages: 1.56, 1.66, 1.59

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.