mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2017-08-27, 21:48   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

22×79 Posts
Post 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.
carpetpool is offline   Reply With Quote
Old 2017-08-27, 23:18   #2
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2×2,963 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2017-08-27, 23:33   #3
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

8,369 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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
science_man_88 is offline   Reply With Quote
Old 2017-08-31, 15:16   #4
LaurV
Romulan Interpreter
 
LaurV's Avatar
 
Jun 2011
Thailand

23×1,103 Posts
Default

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
LaurV is offline   Reply With Quote
Old 2017-08-31, 17:20   #5
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3×7×132 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
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
Dr Sardonicus is offline   Reply With Quote
Old 2017-08-31, 18:37   #6
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

2·2,963 Posts
Default

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.
CRGreathouse is offline   Reply With Quote
Old 2017-09-01, 13:59   #7
Dr Sardonicus
 
Dr Sardonicus's Avatar
 
Feb 2017
Nowhere

3·7·132 Posts
Default

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.
Dr Sardonicus is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Smallest prime of the form a^2^m + b^2^m, m>=14 JeppeSN Math 114 2018-12-16 01:57
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

All times are UTC. The time now is 02:46.

Tue Oct 20 02:46:11 UTC 2020 up 39 days, 23:57, 0 users, load averages: 1.27, 1.89, 1.97

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.