mersenneforum.org Probability that N is prime given each divisor of N has the form 2*k*p+1
 Register FAQ Search Today's Posts Mark Forums Read

 2017-08-27, 21:48 #1 carpetpool     "Sam" Nov 2016 33510 Posts Probability that N is prime given each divisor of N has the form 2*k*p+1 Given that each divisor of N has the form 2*k*p+1 for p > 2, what is the probability that N is prime? For p = 2, this is log(N)/2 since N can be any odd number. What about p = 3, 4, 5, 6, 7, and so on? Second lemma/problem, given ANY integer N, and Q being the smallest integer greater than N with each prime factor dividing Q of the form 2*k*p+1 with p > 2, what is the probability that Q is prime? For example, we choose N = 15038177170 at random and we want to find the smallest integer Q > N with each prime factor of the form 2*5*k+1. How likely is it that Q be prime? well in this case Q happens to be 15038177201 which IS prime. I did a 6 more tests like this with numbers the same size as this N and only 1 time Q turned out to be composite. In fact, given this same problem with a different p > 5, and another (large) n, it is more likely that Q will be prime! But how likely? To see an idea of this, take N = 3814354591765069364 and p = 13. That is the smallest number > N with each prime factor congruent to 1 (mod 2*13). In fact Q = 3814354591765069691 IS the smallest number greater than N with each prime factor congruent to 1 (mod 2*13). Q is indeed, prime. Note that if we had chosen to find the next two integers Q with this condition, we would have Q = 3814354591765069691, 3814354591765069717. The first one is prime, while the second one is composite (3814354591765069717 = 53 · 830363 · 86671678003). 53 = 2*13*2 + 1 830363 = 2*13*31937+1 86671678003 = 2*13*3333526077+1 This is actually unusual as it would've been expected the next two both be prime, in fact testing another number of similar size with p = 13, showed differently with the next two numbers with each divisor of the form 2*13*k+1 being prime. So now choosing N = 602004462102586143517 and finding the smallest integer Q with each prime factor dividing Q having the form 2*29*k+1, Q is extremely likely to be prime. Is anyone willing to do a quick investigation into this? Thanks for help.
2017-08-27, 23:18   #2
CRGreathouse

Aug 2006

5,987 Posts

Quote:
 Originally Posted by carpetpool Given that each divisor of N has the form 2*k*p+1 for p > 2, what is the probability that N is prime? For p = 2, this is log(N)/2 since N can be any odd number. What about p = 3, 4, 5, 6, 7, and so on?
Is this for a particular, fixed p?

In that case, we have two questions. First, asymptotically how many primes of the form 2kp + 1 are there up to x? Second, asymptotically how many numbers up to x are products of primes of that form?

The first question is the prime number theorem in arithmetic progressions, the crowning achievement of 19th-century number theory. The answer is ~ 1/phi(2p) * x/log x = 1/(p-1) * x/log x.

The second question is related to the question of the density of numbers which can be expressed as the sum of two squares. For that case the answer is Kx/sqrt(log x) for a constant K (the Landau-Ramanujan constant); I think you might get the same behavior, with other constants of course, for each choice of p.

If so the probability would be K_p/sqrt(log x) for some constant K_p depending on p.

Some numerical testing seems to support this, with K_3 around 1.5. More knowledgeable foremites are encouraged to chime in.

2017-08-27, 23:33   #3
science_man_88

"Forget I exist"
Jul 2009
Dartmouth NS

20E216 Posts

Quote:
 Originally Posted by carpetpool Given that each divisor of N has the form 2*k*p+1 for p > 2, what is the probability that N is prime? For p = 2, this is log(N)/2 since N can be any odd number.
( emphasis mine) no it can not be. 2*k*2+1= 4*k+1 which is only half the odd numbers. ( and not all these only have factors of the proper form).

Last fiddled with by science_man_88 on 2017-08-27 at 23:55

 2017-08-31, 15:16 #4 LaurV Romulan Interpreter     "name field" Jun 2011 Thailand 19×541 Posts deleted someone said it already, but I didn't read to the end before spitting it out... sorry Last fiddled with by LaurV on 2017-08-31 at 15:18
2017-08-31, 17:20   #5
Dr Sardonicus

Feb 2017
Nowhere

2×3×17×61 Posts

Quote:
 Originally Posted by CRGreathouse Is this for a particular, fixed p? In that case, we have two questions. First, asymptotically how many primes of the form 2kp + 1 are there up to x? Second, asymptotically how many numbers up to x are products of primes of that form? The first question is the prime number theorem in arithmetic progressions, the crowning achievement of 19th-century number theory. The answer is ~ 1/phi(2p) * x/log x = 1/(p-1) * x/log x. The second question is related to the question of the density of numbers which can be expressed as the sum of two squares. For that case the answer is Kx/sqrt(log x) for a constant K (the Landau-Ramanujan constant); I think you might get the same behavior, with other constants of course, for each choice of p. If so the probability would be K_p/sqrt(log x) for some constant K_p depending on p. Some numerical testing seems to support this, with K_3 around 1.5. More knowledgeable foremites are encouraged to chime in.
An asymptotic formula (derived by means of the Wiener-Ikehara Theorem) may be found in

10.1 Integers generated by primes in residue classes

on p. 237 of ANALYTIC NUMBER THEORY An Introductory Course by Paul T Bateman and Harold G Diamond

If I read the hypotheses correctly, the answer for a number composed of prime factors all in a given residue class (mod m) (which is relatively prime to m of course!) has the form c*x*(log(x))^(1/h - 1) where h = eulerphi(m). When m = 4, we have h = 2, and the formula is consistent with the one given above.

When m is an odd prime p (or 2*p) we have phi(m) = p - 1. This is again 2 for m = 3 or 6. But for larger primes p, we have 1/(p-1) < 1/2.

Last fiddled with by Dr Sardonicus on 2017-08-31 at 17:24

 2017-08-31, 18:37 #6 CRGreathouse     Aug 2006 5,987 Posts Thank you, very helpful. So yes, in that particular case, but in general the exponent of the logarithm in the denominator need not be 1/2.
 2017-09-01, 13:59 #7 Dr Sardonicus     Feb 2017 Nowhere 2×3×17×61 Posts Using the formula c*x*log(x)^(1/(p-1) - 1) for the number of numbers <= x which are composed of prime factors congruent to 1 (mod 2*p), and 1/(p-1)*x/log(x) for the number of such primes, we get an approximate probability (in terms of the constant factor c) of 1/((p-1)*c) * 1/log(x)^1/(p-1) that a number near x composed of p congruent to 1 (mod 2*p) is prime. When x is large enough (depends on p and c) the probability of being prime is much greater than for a random number number congruent to 1 (mod 2*p) of the same magnitude, which would be 1/log(x). The previously-cited source has a formula of sorts (on p. 240) for the constant c, which it makes explicit for m = 4, and gives a numerical estimate in that case. I believe there is a similar explicit formula for primes congruent to 1 (mod m), but I'm too lazy to work it out.

 Similar Threads Thread Thread Starter Forum Replies Last Post JeppeSN Math 117 2022-08-30 16:41 carpetpool Miscellaneous Math 27 2017-01-19 21:00 PawnProver44 Miscellaneous Math 9 2016-03-19 22:11 fenderbender Math 5 2007-07-18 18:39 juergen Math 2 2004-07-10 23:01

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

Thu Feb 2 09:10:26 UTC 2023 up 168 days, 6:39, 1 user, load averages: 0.96, 0.77, 0.82