Probability that n is a semi-prime or prime

carpetpool · 2017-01-16, 17:34

What is the probability than for any integer n, n is a semi-prime (a semi-prime is a numbers which has only 3 or 4 positive divisors, or two prime factors) or a prime (numbers which only has divisors 1 and n)?

Hint: Who on this forum doesn't know the probability n is prime is roughly 1/log(n)?

science_man_88 · 2017-01-16, 18:14

Quote:

Originally Posted by carpetpool

What is the probability than for any integer n, n is a semi-prime (a semi-prime is a numbers which has only 3 or 4 positive divisors, or two prime factors) or a prime (numbers which only has divisors 1 and n)?

Hint: Who on this forum doesn't know the probability n is prime is roughly 1/log(n)?

3 denotes a prime square and only has one distinct prime factor.

carpetpool · 2017-01-16, 18:20

Quote:

Originally Posted by science_man_88

3 denotes a prime square and only has one distinct prime factor.

Yes, but the problem to answering this question with the probability a number is prime is equivalent to factoring n, which is most likely not possible as of today.

science_man_88 · 2017-01-16, 18:29

Quote:

Originally Posted by carpetpool

Yes, but the problem to answering this question with the probability a number is prime is equivalent to factoring n, which is most likely not possible as of today.

in fact even the 4 divisor case has a subset where n is a prime cube. also ceil(log_2(n)) is the highest number of factors any n can have ceil(log(3)) if it's odd. then you can reduce the problem to how many ways can you arrange the exponents of the primes in the factorization of a number such that it has a specific number of divisors versus how many partitions of numbers s<ceil(log(3)) there are in total. so up to certain values it is potentially easily figurable. you can figure out the number of divisors of a number by the product of the exponent +1 for each exponent given. edit: okay replace ceil with floor but you get the point I hope.

CRGreathouse · 2017-01-16, 22:59

Quote:

Originally Posted by carpetpool

What is the probability than for any integer n, n is a semi-prime (a semi-prime is a numbers which has only 3 or 4 positive divisors, or two prime factors) or a prime (numbers which only has divisors 1 and n)?

Asymptotically, log log n/log n.

carpetpool · 2017-01-17, 00:52

Quote:

Originally Posted by CRGreathouse

Asymptotically, log log n/log n.

How do you interpret that?

I am assuming (log (log n))/(log n). Right?

GP2 · 2017-01-17, 09:01

For what it's worth:

The first Mersenne number with no known factors is M1277 (or M1207 if we count non-prime exponents, but I don't think this is a semi-prime candidate).

There are 14 Mersenne primes smaller than this, and 42 Mersenne semi-primes (OEIS sequence A085724). The latter set includes M4, M9 and M49 which have non-prime exponents.

Here is an old thread about Mersenne semi-primes.

danaj · 2017-01-17, 11:11

Quote:

Originally Posted by carpetpool

How do you interpret that?

I am assuming (log (log n))/(log n). Right?

A trivial google search yields semiprime probability with "log(log(n))/log(n) + O(1/log(n))" shown. It links to a more complicated mathoverflow discussion.

The comments about factoring seem to be about trying to give a correct answer for a specific n. Remember that primality is much simpler than factorization in complexity (and in practice). This is also a help if we do find a single factor, in that we can reasonably see whether the remainder is composite. While we don't need a full factorization, as n gets very large I'm not sure that helps much with complexity.

CRGreathouse · 2017-01-17, 16:38

Quote:

Originally Posted by carpetpool

How do you interpret that?

I am assuming (log (log n))/(log n). Right?

Yes -- I'm not sure how else one could interpret it.

Also, here (as usual) log means base e.

CRGreathouse · 2017-01-17, 16:45

Quote:

Originally Posted by danaj

A trivial google search yields semiprime probability with "log(log(n))/log(n) + O(1/log(n))" shown. It links to a more complicated mathoverflow discussion.

Yes, that's my MathOverflow question!

Quote:

Originally Posted by danaj

Remember that primality is much simpler than factorization in complexity (and in practice). This is also a help if we do find a single factor, in that we can reasonably see whether the remainder is composite. While we don't need a full factorization, as n gets very large I'm not sure that helps much with complexity.

Right, this is how [url=https://github.com/CRGreathouse/PARI-extensions/blob/69c72d1c6da659ad92966c28a37e5c24be1c4e31/prime.gp.c#L6]I do it/[url], I don't know of a better way. For random numbers this works decently with SQUFOF + ECM (there is often a small factor you can pull out). For large hard numbers it's infeasible as you suggest, nothing easier than NFS.

danaj · 2017-01-17, 23:45

Ah, I had seen you wrote an answer, but missed that it was your question!

I thought the link gave a little more explanation for the OP, including more detail for someone to read if they were curious.

Thanks for the code link. Now you're making me think about implementing it, not because I have anything useful to add, but because it looks like a fun bit of optimization for smaller inputs. For larger ones, yes -- some heuristics trying to weed out easier results common with random inputs, but for the harder ones there's not an easy answer.

2017-01-16, 17:34	#1
carpetpool "Sam" Nov 2016 335₁₀ Posts	Probability that n is a semi-prime or prime What is the probability than for any integer n, n is a semi-prime (a semi-prime is a numbers which has only 3 or 4 positive divisors, or two prime factors) or a prime (numbers which only has divisors 1 and n)? Hint: Who on this forum doesn't know the probability n is prime is roughly 1/log(n)?

Similar Threads
Thread	Thread Starter	Forum	Replies	Last Post
Semi-prime factorization conjecture	Alberico Lepore	Alberico Lepore	7	2018-02-16 08:27
Probability that n is a prime power	carpetpool	Miscellaneous Math	6	2017-01-30 02:54
probability a number is prime with a weighted k.	Trilo	Homework Help	12	2014-06-06 19:17
Probability of a Mersenne number being prime	vimil	Information & Answers	13	2007-12-12 11:21
probability of finding a Mersenne prime	optim	Math	2	2003-12-06 19:03

2017-01-17, 09:01	#7
GP2 Sep 2003 2·5·7·37 Posts	For what it's worth: The first Mersenne number with no known factors is M1277 (or M1207 if we count non-prime exponents, but I don't think this is a semi-prime candidate). There are 14 Mersenne primes smaller than this, and 42 Mersenne semi-primes (OEIS sequence A085724). The latter set includes M4, M9 and M49 which have non-prime exponents. Here is an old thread about Mersenne semi-primes.

2017-01-17, 23:45	#11
danaj "Dana Jacobsen" Feb 2011 Bangkok, TH 2·5·7·13 Posts	Ah, I had seen you wrote an answer, but missed that it was your question! I thought the link gave a little more explanation for the OP, including more detail for someone to read if they were curious. Thanks for the code link. Now you're making me think about implementing it, not because I have anything useful to add, but because it looks like a fun bit of optimization for smaller inputs. For larger ones, yes -- some heuristics trying to weed out easier results common with random inputs, but for the harder ones there's not an easy answer.