20170827, 21:48  #1 
"Sam"
Nov 2016
2^{2}×79 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. 
20170827, 23:18  #2  
Aug 2006
2×2,963 Posts 
Quote:
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 19thcentury number theory. The answer is ~ 1/phi(2p) * x/log x = 1/(p1) * 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 LandauRamanujan 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. 

20170827, 23:33  #3 
"Forget I exist"
Jul 2009
Dumbassville
8,369 Posts 
( 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 20170827 at 23:55 
20170831, 15:16  #4 
Romulan Interpreter
Jun 2011
Thailand
2^{3}×1,103 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 20170831 at 15:18 
20170831, 17:20  #5  
Feb 2017
Nowhere
3×7×13^{2} Posts 
Quote:
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/(p1) < 1/2. Last fiddled with by Dr Sardonicus on 20170831 at 17:24 

20170831, 18:37  #6 
Aug 2006
2·2,963 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.

20170901, 13:59  #7 
Feb 2017
Nowhere
3·7·13^{2} Posts 
Using the formula c*x*log(x)^(1/(p1)  1) for the number of numbers <= x which are composed of prime factors congruent to 1 (mod 2*p), and 1/(p1)*x/log(x) for the number of such primes, we get an approximate probability (in terms of the constant factor c) of
1/((p1)*c) * 1/log(x)^1/(p1) 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 previouslycited 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. 
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  20181216 01:57 
Probability that n is a semiprime or prime  carpetpool  Miscellaneous Math  27  20170119 21:00 
Is there a prime of the form......  PawnProver44  Miscellaneous Math  9  20160319 22:11 
Small prime test divisor efficiency strategy  fenderbender  Math  5  20070718 18:39 
Search for a number theoretic function related to "prime divisor sums"  juergen  Math  2  20040710 23:01 