mersenneforum.org  

Go Back   mersenneforum.org > Extra Stuff > Miscellaneous Math

Reply
 
Thread Tools
Old 2017-01-16, 17:34   #1
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

52×13 Posts
Post 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)?
carpetpool is offline   Reply With Quote
Old 2017-01-16, 18:14   #2
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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.
science_man_88 is offline   Reply With Quote
Old 2017-01-16, 18:20   #3
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

52·13 Posts
Post

Quote:
Originally Posted by science_man_88 View Post
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.
carpetpool is offline   Reply With Quote
Old 2017-01-16, 18:29   #4
science_man_88
 
science_man_88's Avatar
 
"Forget I exist"
Jul 2009
Dumbassville

203008 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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
science_man_88 is offline   Reply With Quote
Old 2017-01-16, 22:59   #5
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2017-01-17, 00:52   #6
carpetpool
 
carpetpool's Avatar
 
"Sam"
Nov 2016

32510 Posts
Post

Quote:
Originally Posted by CRGreathouse View Post
Asymptotically, log log n/log n.
How do you interpret that?

I am assuming (log (log n))/(log n). Right?
carpetpool is offline   Reply With Quote
Old 2017-01-17, 09:01   #7
GP2
 
GP2's Avatar
 
Sep 2003

5·11·47 Posts
Default

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.
GP2 is offline   Reply With Quote
Old 2017-01-17, 11:11   #8
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

32×101 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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.
danaj is offline   Reply With Quote
Old 2017-01-17, 16:38   #9
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3×1,993 Posts
Default

Quote:
Originally Posted by carpetpool View Post
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 is offline   Reply With Quote
Old 2017-01-17, 16:45   #10
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by danaj View Post
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 View Post
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.
CRGreathouse is offline   Reply With Quote
Old 2017-01-17, 23:45   #11
danaj
 
"Dana Jacobsen"
Feb 2011
Bangkok, TH

32×101 Posts
Default

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

Thread Tools


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

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

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, 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.