Probability that N is prime given each divisor of N has the form 2*k*p+1

carpetpool · 2017-08-27, 21:48

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.

CRGreathouse · 2017-08-27, 23:18

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.

science_man_88 · 2017-08-27, 23:33

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

LaurV · 2017-08-31, 15:16

deleted
someone said it already, but I didn't read to the end before spitting it out... sorry

Dr Sardonicus · 2017-08-31, 17:20

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.

CRGreathouse · 2017-08-31, 18:37

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.

Dr Sardonicus · 2017-09-01, 13:59

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.

2017-08-27, 21:48	#1
carpetpool "Sam" Nov 2016 517₈ Posts	*Probability that N is prime given each divisor of N has the form 2kp+1* Given that each divisor of N has the form 2kp+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 2kp+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 25k+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 213). In fact Q = 3814354591765069691 IS the smallest number greater than N with each prime factor congruent to 1 (mod 213). 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 = *213*2 + 1 830363 = 21331937+1 86671678003 = 213*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 213k+1 being prime. So now choosing N = 602004462102586143517 and finding the smallest integer Q with each prime factor dividing Q having the form 229*k+1, Q is extremely likely to be prime. Is anyone willing to do a quick investigation into this? Thanks for help.

2017-08-31, 15:16	#4
LaurV Romulan Interpreter "name field" Jun 2011 Thailand 10100000101101₂ 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

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Smallest prime of the form a^2^m + b^2^m, m>=14	JeppeSN	Math	117	2022-08-30 16:41
Probability that n is a semi-prime or prime	carpetpool	Miscellaneous Math	27	2017-01-19 21:00
Is there a prime of the form......	PawnProver44	Miscellaneous Math	9	2016-03-19 22:11
Small prime test divisor efficiency strategy	fenderbender	Math	5	2007-07-18 18:39
Search for a number theoretic function related to "prime divisor sums"	juergen	Math	2	2004-07-10 23:01

2017-08-31, 18:37	#6
CRGreathouse Aug 2006 2²×3×499 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 18BB₁₆ Posts	Using the formula cxlog(x)^(1/(p-1) - 1) for the number of numbers <= x which are composed of prime factors congruent to 1 (mod 2p), 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 2p) 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 2p) 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.