In introductory elementary theory courses there’s footnotes of all these theorems like this guy proved the number of primes less than n is less than ln(1000n)lnlnlnln(ln2)/sin(ln(n)) or whatever. But the actual courses don’t really have logarithms.
How do they relate primes or whatever else with logarithms? I mean, I know of logarithms as inverses of exponentiation. I don’t see how primes and such relate to exponential growth or its inverse. I hope my question is clear enough. For example, if it were trig functions, I’d look for how they relate to a circle. With logarithms, I’m not even sure if the inverse of exponentiation train of thought is even correct.
In: Mathematics
One way log pops up is because it is the antiderivative of 1/x. For example the discretized version is **the harmonic sum 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + … + 1/n which is about the same as the area under the curve 1/x from 1 to n, which in turn is ln(n)**, the natural logarithm of n.
Then **the sum of reciprocal primes 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + 1/13 + … + 1/p is roughly ln(ln(p))**:
The _infinite harmonic series_ 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + … “factors” into the product of
– 1 + 1/2 + 1/4 + 1/8 + 1/16 + …
– 1 + 1/3 + 1/9 + 1/27 + 1/81 + …
– 1 + 1/5 + 1/25 + 1/125 + 1/625 + …
– 1 + 1/7 + 1/49 + 1/343 + …
– 1 + 1/11 + 1/121 + …
– …
Try to see what happens if you multiple all those lines together and expand: unique prime factorization means that each 1/n appears exactly once!
But then 1 + 1/p + 1/p² + 1/p³ + … is a _geometric series_ with value 1/(1 – 1/p). So we find the weird equality
1/1 + 1/2 + 1/3 + 1/4 + 1/5 + … = 1 / [(1 – 1/2)·(1 – 1/3)·(1 – 1/5)·(1 – 1/7)·(1 – 1/11)· … ]
and taking logarithms and using that ln(1-x) ~ -x we finally arrive at
ln( 1/1 + 1/2 + 1/3 + 1/4 + 1/5 + … ) ~ 1/2 + 1/3 + 1/5 + 1/7 + 1/11 + 1/13 + …
If done carefully and correctly one then finds that the left side grows like ln(ln(n)) as seen at the beginning and thus so does the sum of reciprocal primes. If continued even much more carefully and with further arguments this leads to the proofs of two very important results from analytic number theory:
– The **Prime Number Theorem**: there are ~ n/ln(n) primes up to n.
– **Dirichlet’s Theorem on primes in arithmetic progressions**: if a and n are coprime positive integers, then there are infinitely many primes in the sequence a, a+n, a+2n, a+3n, a+4n, … (and for each possible choice for a we get approximately the same amount of primes).
I’ll be honest, I’m not totally sure of the answer to your specific question exactly (though you could probably Google it, so it probably doesn’t actually fit this sub), but here’s a thought that might get you started. Primes are all about multiplication. Let’s assume we’re trying to get some kind of upper bound. We could assume that every integer is a prime. We know this isn’t true, but we also know that we’re overestimating, not underestimating. So we could assume that from 1 to 10, there are 10 primes.
Let’s suppose we want to know about the product of these primes (because multiplication). Well, that would be 1×2×3×4×5×6×7×8×9×10=10!, but factorials can be tricky. So let’s just replace each ‘prime’ with a bigger number. We could replace them all with 10 (okay, a number that’s at least as big). Then, the number we’re looking at for the product of all the primes is definitely no bigger than 10¹⁰.
Now, suddenly, we’re in exponent land. We could look at the natural log of this, and we get ln(10¹⁰)=10ln(10), and things begin to head towards the form of the upper bound in your proof.
Latest Answers