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)? :smile:

[QUOTE=carpetpool;451045]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)? :smile:[/QUOTE]

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

[QUOTE=science_man_88;451050]3 denotes a prime square and only has one distinct prime factor.[/QUOTE]

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.

[QUOTE=carpetpool;451051]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.[/QUOTE]

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.

[QUOTE=carpetpool;451045]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)?[/QUOTE]

Asymptotically, log log n/log n.

[QUOTE=CRGreathouse;451072]Asymptotically, log log n/log n.[/QUOTE]

How do you interpret that?

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

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 [URL="http://oeis.org/A085724"]A085724[/URL]). The latter set includes M4, M9 and M49 which have non-prime exponents.

Here is [URL="http://www.mersenneforum.org/showthread.php?t=14249"]an old thread about Mersenne semi-primes[/URL].

[QUOTE=carpetpool;451075]How do you interpret that?

I am assuming (log (log n))/(log n). Right?[/QUOTE]

A trivial google search yields [url=https://en.wikipedia.org/wiki/Talk%3ASemiprime#Probability]semiprime probability[/url] 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 [i]n[/i]. 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 [i]n[/i] gets very large I'm not sure that helps much with complexity.

[QUOTE=carpetpool;451075]How do you interpret that?

I am assuming (log (log n))/(log n). Right?[/QUOTE]

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

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

[QUOTE=danaj;451095]A trivial google search yields [url=https://en.wikipedia.org/wiki/Talk%3ASemiprime#Probability]semiprime probability[/url] with "log(log(n))/log(n) + O(1/log(n))" shown. It links to a more complicated mathoverflow discussion.[/QUOTE]

Yes, that's my MathOverflow question!

[QUOTE=danaj;451095]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 [i]n[/i] gets very large I'm not sure that helps much with complexity.[/QUOTE]

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.

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.

[QUOTE=CRGreathouse;451105]

Also, here (as usual) log means base e.[/QUOTE]
I think that's only usual to Pari/GP, but I could be wrong. I thought ln was the proper notation for natural log and log without a base specified, was base 10 not e.
I haven't seen the log convention for base e anywhere else but then again I am no mathematician.:smile:
But on my defense, I did stay at Holiday Inn once. :jokedrum:

[QUOTE=danaj;451132]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.[/QUOTE]

I hope you do code it, because I think that more can be done than the simple code I linked to, and I find that I use what I wrote reasonably often.

I feel bad, because I often write "issemi(n)=bigomega(n)==2" in the OEIS, knowing that I don't use that code but not wanting to bloat the entry with a full version of my code. Of course there's not all that much that can be done in GP -- the most you have access to are the flags of factorint. It's much nicer with access to the PARI internals.

[QUOTE=a1call;451136]I thought ln was the proper notation for natural log and log without a base specified, was base 10 not e.[/QUOTE]

Mathematicians don't use log to represent the base-10 log, only engineers and (some) high-school teachers do. :smile: Computer scientists sometimes use log to mean natural log and sometimes to mean binary log, but most often they don't mean any particular base (as in big-O notation). Other mathematicians rarely use log for anything but the natural log.

[QUOTE=CRGreathouse;451142]Mathematicians don't use log to represent the base-10 log, only engineers and (some) high-school teachers do. :smile: Computer scientists sometimes use log to mean natural log and sometimes to mean binary log, but most often they don't mean any particular base (as in big-O notation). Other mathematicians rarely use log for anything but the natural log.[/QUOTE]

ISO 31-11 defines:-

lb - binary log (base 2)
ln - natural log (base e)
lg - common log (base 10)

also, all the books of mathematical tables from my youth used:-
log - common logarithm (base 10)
ln - natural logarithm (base e)
as did/do all electronic calculators I have used.
I am also pretty sure that my slide rule used log for common logarithm. :smile:

[QUOTE=Antonio;451153]ISO 31-11 defines:-

lb - binary log (base 2)
ln - natural log (base e)
lg - common log (base 10)

also, all the books of mathematical tables from my youth used:-
log - common logarithm (base 10)
ln - natural logarithm (base e)
as did/do all electronic calculators I have used.
I am also pretty sure that my slide rule used log for common logarithm. :smile:[/QUOTE]
Mathematical tables, at least of logarithms, no longer have relevance to the modern mathematician, and not really to the modern engineer either really.

ISO defines tons of standards that aren't really respected... and I would qualify the one you list of one such standard.

I'll agree with Charles on this one. In number theory books and papers in particular, "log" means the natural logarithm unless otherwise specified. I've seen base 2 specified, e.g. the AKS paper, where they still use "log" throughout the paper but mention in one early sentence that it means base 2 since that is not the normal expectation. As Charles notes, many times it doesn't matter such as in big-O.

Paraphrasing someone's quip, once you get out of high school you find the common logarithm is very uncommon.

I will occasionally use "log[sub]2[/sub](n)" to make it readily apparent this is base 2. Confusingly, a few authors have decided to use the subscript to denote iteration, sometimes combined with a superscript to denote exponentiation of the whole thing. So "[tex]\log_2^3(n)[/tex]" means log(log(n))^3 to them. I do not like this notation (especially when one has to work it out from previous equations rather than being explained), and fortunately rarely see it. Oh -- they of course mean the natural log, since that goes without saying. :)

[Joking on]
log means log[SUB]10[/SUB], anything else is just another extremist minority group trying to impose their views on the rest of the world.
[Joking off]

I don't mind either I just wish the world was consistent, being an engineer using log[SUB]e[/SUB] doesn't come naturally :smile:
I always have to think about it, usually after the first couple of wrong calculations (and it doesn't help that my(all) calculators were designed for engineers/high school students).

[QUOTE=danaj;451155]I've seen base 2 specified, e.g. the AKS paper, where they still use "log" throughout the paper but mention in one early sentence that it means base 2 since that is not the normal expectation.[/QUOTE]

Right. The culture in computer science is different and they often use log for the binary logarithm (though in all cases where I've seen this they call it out).

[QUOTE=danaj;451155]Paraphrasing someone's quip, once you get out of high school you find the common logarithm is very uncommon.[/QUOTE]

Right. It was in use in the slide rule era but since electronic calculators in the 70s and 80s it's fallen into disuse in mathematics (but as I understand, it's still in use in engineering).

[QUOTE=danaj;451155]I will occasionally use "log[sub]2[/sub](n)" to make it readily apparent this is base 2. Confusingly, a few authors have decided to use the subscript to denote iteration, sometimes combined with a superscript to denote exponentiation of the whole thing. So "[tex]\log_2^3(n)[/tex]" means log(log(n))^3 to them.[/QUOTE]

Right. I see subscripted logs used much more often to denote iteration than base. But that's probably just in analytic number theory and allied fields; probably mathematicians in other areas write log_b to mean log base b. I agree, it can be confusing.

[QUOTE=a1call;451136]I think that's only usual to Pari/GP, but I could be wrong. I thought ln was the proper notation for natural log and log without a base specified, was base 10 not e.
I haven't seen the log convention for base e anywhere else but then again I am no mathematician.:smile:
But on my defense, I did stay at Holiday Inn once. :jokedrum:[/QUOTE]

working in log base e is simpler potentially though see numberphile:

[YOUTUBE]AuA2EAgAegE[/YOUTUBE]

Pari/GP: log(x): natural logarithm of x

Mathematica: Log[x] gives the natural logarithm of x

C: log(x) from math.h gives the natural log of x

Perl: log(x) gives the natural log of x

Python: math.log(x) gives the natural log of x

Julia: log(x) gives the natural log of x

Go: math.log(x) gives the natural log of x

Maple: ln(x) is the natural log, log[b](x) is the log to base b. If left out, b=e. Hence log(x) is the natural log of x

This sure doesn't look isolated to Pari. It seems highly unusual to use base 10 without calling it out via log10 or an argument. The natural log is pretty useful, the others not as much. A function like digits() covers a fairly common and special case of base 10 log, and similarly for base 2 for getting the number of bits.

[QUOTE=danaj;451179]
This sure doesn't look isolated to Pari. It seems highly unusual to use base 10 without calling it out via log10 or an argument. The natural log is pretty useful, the others not as much. [/QUOTE]

It's a bit exaggerated to call the notion used by the rest (from mathematicians and programmers ) of the world "highly unusual".

[QUOTE]Because the notation log [I]x[/I] has been used for all three bases (or when the base is indeterminate or immaterial), the intended base must often be inferred based on context or discipline. In computer science and mathematics, log usually refers to log2 and log[I]e[/I], respectively.[URL="https://en.wikipedia.org/wiki/Logarithm#cite_note-12"][11][/URL] In [B]other[/B] contexts log often means log10.[URL="https://en.wikipedia.org/wiki/Logarithm#cite_note-13"][12][/URL][/QUOTE][URL]https://en.wikipedia.org/wiki/Logarithm#Particular_bases[/URL]

It is arguable that the logarithm function predates the discovery of e as well as computers, so chances are that log, unspecific must have referred to base 10 originally by all.
Base 10 log is still quite useful in logarithmic scales and units.
[URL]https://en.wikipedia.org/wiki/Logarithmic_scale[/URL]

[QUOTE=a1call;451190]It's a bit exaggerated to call the notion used by the rest (from mathematicians and programmers ) of the world "unusual".

[URL]https://en.wikipedia.org/wiki/Logarithm#Particular_bases[/URL]

It is arguable that the logarithm function predates the discovery of e as well as computers, so chances are that log, unspecific must have referred to base 10 originally by all.
Base 10 log is still quite useful in logarithmic scales and units.
[URL]https://en.wikipedia.org/wiki/Logarithmic_scale[/URL][/QUOTE]

the moment magnitude scale can be related to the log_(10^(3/2))(x) where x is energy just as easily based on the descriptions given. and for pH it could also relate to the log of x in base 1/10 in theory.

[QUOTE=a1call;451190]It's a bit exaggerated to call the notion used by the rest (from mathematicians and programmers ) of the world "highly unusual".
[/QUOTE]
You're in a mathematics forum, in a thread discussing the implied base of a usage of log in a mathematics formula. Dr Greathouse's statement is right on, in the context of this thread and this forum.

As a former physics major, I found it confusing during my graduate math studies that log was *never* disambiguated; a statement such as Dr Greathouse's would have cleared up much for me as I changed from science studies to mathematics. I assumed this formula was log_10 myself, years ago, only deciding otherwise by repeating the calculations of others using both bases to learn which was proper (and then doubting whether the other person had chosen the right base). So, his "highly unusual" is quite helpful in telling us to default to natural log *anywhere* in higher mathematics (say, above differential equations).

[QUOTE=VBCurtis;451202]
As a former physics major, I found it confusing during my graduate math studies that log was *never* disambiguated; a statement such as Dr Greathouse's would have cleared up much for me as I changed from science studies to mathematics. I assumed this formula was log_10 myself, years ago, only deciding otherwise by repeating the calculations of others using both bases to learn which was proper (and then doubting whether the other person had chosen the right base). So, his "highly unusual" is quite helpful in telling us to default to natural log *anywhere* in higher mathematics (say, above differential equations).[/QUOTE]
As a physics major with an admitted strong bias to the mathematical bent, I was never really confused by what "log" meant. But maybe things are different since when you went to high school? Even in pre-calc (circa 2009 for me) it was pretty clear that "log" meant the natural.

I've taught pre-calculus at a US public university for the last 20 years, and every textbook we've used has defined log as log_10, and natural log as only ln. Our single-variable calculus texts likewise always use ln for natural log (Stewart, Thomas, and Larson are the texts I've taught out of for Calculus).

My "highly unusual" comment was in regard to programming languages and math packages, where I gave a number of examples. All of them use "log" to refer to the natural log. It was countering the comment that "that's only usual to Pari/GP" which seems to be in error.

There is another disagreement about what the base assumption is in written notation, but let's not conflate the two.

Re number theory, It looks like Cohen's "Course in ..." book uses lg/ln, while Apostol (a common intro textbook) says on page 8 "...where log x is the natural logarithm of x" and then goes on to use log as the natural log throughout the text. I typically find log to mean natural log in number theory papers, but that is purely anecdotal. I don't believe I've ever seen it specifically mean base 10.

[QUOTE=CRGreathouse;451141]I hope you do code it, because I think that more can be done than the simple code I linked to, and I find that I use what I wrote reasonably often.

I feel bad, because I often write "issemi(n)=bigomega(n)==2" in the OEIS, knowing that I don't use that code but not wanting to bloat the entry with a full version of my code. Of course there's not all that much that can be done in GP -- the most you have access to are the flags of factorint. It's much nicer with access to the PARI internals.[/QUOTE]

I haven't dug into the internals of Pari too much to speed these things up (though after the Atelier I may do more). What I see so far:

206.124 sec gp: sum(n=10^17,10^17+10^6,bigomega(n)==2)
29.116 sec gp: sum(n=10^17,10^17+10^6,issemi(n))
9.996 sec perl -Mntheory -E 'for (10**17..10**17+1e6){ $t++ if scalar(factor($_)) == 2; } say $t;'
2.052 sec perl -Mntheory -E 'for (10**17..10**17+1e6){ $t++ if is_semiprime($_); } say $t;'

I'm sure things get more interesting once into bignums, and I haven't written that. There's some optimization that can be made in other areas, for example uisprime() is over 5x slower than my code, which we may fix this year.That's probably most of the difference between our codes for issemiprime.

More important for Pari is the 20x difference in bigomega at this size.