 mersenneforum.org Probability that n is a semi-prime or prime
 Register FAQ Search Today's Posts Mark Forums Read  2017-01-16, 17:34 #1 carpetpool   "Sam" Nov 2016 52×13 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)?    2017-01-16, 18:14   #2
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

203008 Posts 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.   2017-01-16, 18:20   #3
carpetpool

"Sam"
Nov 2016

52·13 Posts 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.   2017-01-16, 18:29   #4
science_man_88

"Forget I exist"
Jul 2009
Dumbassville

203008 Posts 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.

Last fiddled with by science_man_88 on 2017-01-16 at 18:42   2017-01-16, 22:59   #5
CRGreathouse

Aug 2006

3·1,993 Posts 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.   2017-01-17, 00:52   #6
carpetpool

"Sam"
Nov 2016

32510 Posts 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?   2017-01-17, 09:01 #7 GP2   Sep 2003 5·11·47 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, 11:11   #8
danaj

"Dana Jacobsen"
Feb 2011
Bangkok, TH

32×101 Posts 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.   2017-01-17, 16:38   #9
CRGreathouse

Aug 2006

3×1,993 Posts 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.   2017-01-17, 16:45   #10
CRGreathouse

Aug 2006

3·1,993 Posts 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.   2017-01-17, 23:45 #11 danaj   "Dana Jacobsen" Feb 2011 Bangkok, TH 32×101 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.   Thread Tools Show Printable Version Email this Page Similar Threads Thread Thread Starter Forum Replies Last Post Alberico Lepore Alberico Lepore 7 2018-02-16 08:27 carpetpool Miscellaneous Math 6 2017-01-30 02:54 Trilo Homework Help 12 2014-06-06 19:17 vimil Information & Answers 13 2007-12-12 11:21 optim Math 2 2003-12-06 19:03

All times are UTC. The time now is 19:48.

Tue Oct 19 19:48:05 UTC 2021 up 88 days, 14:17, 0 users, load averages: 1.54, 1.69, 1.67