Oops, punched in the wrong values in the calculator. Hari Seldon’s count of number of primes below 2[sup]1024[/sup] is right, not mine. It’s still a huge enough number.
Hari Seldon writes:
> The number of primes below n = 2^1024 is roughly n/710,
> which is something like 2^1021.
(2^1024)/710 doesn’t equal 2^1021. Let’s start from the beginning. The number of primes below 2^1024 is approximately (2^1024)/ln(2^1024), which does equal approximately (2^1024)/710. But that equals about 2^1014.53.
Just out of curiousity, is this proven? How can we be sure that the number of primes is infinite?
That was actually proven by Euclid, and is another classic proof by contradiction.
Suppose there are in fact finitely many primes, and list them as 2, 3, 5, …, P ( so P is the largest prime).
Form the number Q = 2.3.5…P + 1
Now every integer greater than 2 is either prime or has a prime divisor. In particular, this is true of Q.
But: Q is not divisible by 2 ( it leaves a remainder of 1).
Similarly, Q leaves a remainder of 1 when divided by 3.
In fact, it is clear that Q leaves a remainder of 1 when divided by each of 2, 3, 5, …, P. This is our contradiction, for we supposed that 2, 3, 5, …, P were all the primes, and we have shown that none of them divides Q. Therefore our assumption that there are only finitely many primes must be false.
Maybe this is just beyond me but I don’t quite get it.
What do you mean by:
“Form the number Q = 2.3.5…P + 1”
Is Q a set (including all primes and P + 1), or a single number (P + 1)?
“But: Q is not divisible by 2 ( it leaves a remainder of 1)”
Why is this? Actually I guess my confusion is still over what Q is. Obviously it can’t be P + 1 since that is divisible 2, no?
Q is the number dre2xl was talking about yesterday.
To form Q, take the product of the numbers on the list 2, 3, 5, …, P ( i.e. multiply them together) and then add 1 to the result. The 1 that is added at the end is the remainder in each of the divisions mentioned later in the proof.