 mersenneforum.org > Math Wish I paid more attention at school...
 Register FAQ Search Today's Posts Mark Forums Read  2019-10-18, 10:33 #1 mackerel   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.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?   2019-10-18, 11:05 #2 axn   Jun 2003 471910 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 2019-10-18 at 11:06   2019-10-18, 12:25 #3 Dr Sardonicus   Feb 2017 Nowhere 22×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.   2019-10-18, 13:03 #4 mackerel   Feb 2016 UK 39010 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.   2019-10-18, 17:44   #5
axn

Jun 2003

3·112·13 Posts Quote:
 Originally Posted by mackerel 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.   2019-10-19, 03:49 #6 VBCurtis   "Curtis" Feb 2005 Riverside, CA 10001001100012 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 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   2019-10-19, 12:07   #7
Dr Sardonicus

Feb 2017
Nowhere

22·5·179 Posts Quote:
 Originally Posted by VBCurtis 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).
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.   2019-10-19, 13:20   #8
axn

Jun 2003

3·112·13 Posts Quote:
 Originally Posted by Dr Sardonicus 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.   2019-10-19, 13:29 #9 VBCurtis   "Curtis" Feb 2005 Riverside, CA 33×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.   2019-10-22, 10:21   #10
mackerel

Feb 2016
UK

2·3·5·13 Posts Quote:
 Originally Posted by VBCurtis 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   2019-10-22, 10:27   #11
axn

Jun 2003

3×112×13 Posts Quote:
 Originally Posted by mackerel Finally sat down and counted the primes in the tested ranges so far...
Quote:
 Originally Posted by mackerel 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.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post a1call Puzzles 28 2018-05-25 00:03 davieddy Lounge 6 2011-09-27 01:20 mdettweiler No Prime Left Behind 2 2009-12-26 04:23 Unregistered Information & Answers 5 2009-10-15 22:44 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