I wrote a sieve in Java that took 56-58 seconds to find all primes up to one million. the same code in C++ (console app compiled on MVC++6.0) ran in less than two.
Displaying them does take quite a long time. There is a better seive than the ol’ Erastathones one, though for the life of me I can’t remember how it works. Anyone?
I don’t see this. Given any finite set S = {a, b,…, m} of primes, the number (ab…m)+1 is not divisible by any primes of S. How is the ordering relation important?
Atkins. Got it.
We’re not limiting ourself to the integers here; there are primes in more general settings. So (ab…m) + 1 could be one of the original primes. Sorry I didn’t mention that.
It may have been a bigger number than 64 bit. To be honest when I wrote 64 bits I was thinking of the DES key (which the NSA used to require it to be no more than 56-bit). I think right now the National Institute of Standards and Technology only requires commercial encryption to have 128-bit keys, though I could be wrong on that.
Anyway, my point was that its certainly possible to take a distributed program like that, drop the part where the program tests against an encryption and just focus on generating primes.
Oh, OK. I misunderstood.
The number of bits needed for something like DES or other symmetric encryption algorithms to be secure is much much less than the number of bits needed to make asymmetric algorithms like PGP.
The real point is using a large number bits like say 1024 you will need an enormous amount of computational power to crack the encryption. I don’t think there is enough hard disk space in the world to store all the prime numbers between 2 and 2^1024. There are approximately 253 * 10^303 prime numbers less than 2^1024 using the x/ln(x) provided by previous posters. The vast majority of these numbers will need 128 bytes each to store. That is about 32 * 10^297 Giga bytes just to store all the numbers.
Just for a point of reference these numbers are really really really huge:
From our favorite columnist’s helper: http://www.straightdope.com/mailbag/mgoogol.html
If the entire universe were filled with protons and electrons so that there was no vacant space, the total number would be about 10 ^110 . . . this is larger than a googol but much less than a googolplex.
The number we are talking about are very much larger than the largest possible number or really tiny particles there could be if there was not so much empty stuff.
Proof that sum of reciprocals of the primes is divergent:
We shall need to take on trust a few intuitively clear results. The first is the most important: if
a[sub]1[/sub] + a[sub]2[/sub] + a[sub]3[/sub] +…
is convergent then for some N
a[sub]N+1[/sub] + a[sub]N+2[/sub] + a[sub]N+3[/sub] +… < 1/2 (*)
Now for fixed j let N[sub]j/sub equal the number of positive integers less than or equal to x not divisible by any prime greater than p[sub]j[/sub], the jth prime number.
Any such n can be written as n[sub]0[/sub][sup]2[/sup]m, where m has no square factor greater than one. By unique prime factorisation ( another of those facts taken on trust) m can be factorised as
m = p[sub]1[/sub][sup]a[sub]1[/sub][/sup]*p[sub]2[/sub][sup]a[sub]2[/sub][/sup]p[sub]3[/sub][sup]a[sub]3[/sub][/sup]…p[sub]j[/sub][sup]a[sub]j[/sub][/sup]
where each a[sub]i[/sub] is either 0 or 1 ( remember m is square-free and n is not divisible by any prime greater than p[sub]j[/sub]). There are 2 choices for each a[sub]i[/sub] so there are at most 2[sup]j[/sup] choices for m. Also n[sub]0[/sub][sup]2[/sup] <= n <= x, so
n[sub]0[/sub] <= sqrt(x). Thus there are at most sqrt(x) choices for n[sub]0[/sub]. Combining,
N[sub]j/sub <= 2[sup]j[/sup]sqrt(x).
Now suppose the series in question is convergent and pick N such that () is true. The number of positive integers less than or equal to x which are divisible by p is at most x/p. Thus the number of positive integers less than or equal to x divisible by at least one prime greater than p[sub]N[/sub] is not more than
x/p[sub]N+1[/sub] + x/p[sub]N+2[/sub] + x/p[sub]N+3[/sub] +…, which is lesss than x/2, by (). Also, by definition, this number equals x - N[sub]N/sub. We then have
x - N[sub]N/sub < x/2 so
x/2 < N[sub]N/sub <= 2[sup]N[/sup]sqrt(x), whence
x <= 2[sup]2N+2[/sup] for all x.
Since this final inequality is plainly not true for all x our assumption about convergence is false and the series diverges.
And do you have any idea how much coding that took?
Does anyone else have a problem with this? I know the patent system is seriously screwed up (There is a patent for pulling on alternate chains of your swing, to produce a lateral swinging motion :rolleyes: ), but how the hell can you patent an integer?
Anyway, I see prior art:
0 is a natural number.
Every natual number has one succsesor, which is also a natural number.
It blows me away that that proof works (as best as I can tell) without referencing the fact that there are an infinite number of primes. Thanks, Jabba!
Yes indeed. In fact one could ( if feeling bloody-minded) prove the divergence theorem first and use it to deduce that there are infinitely many primes ( since plainly any finite series is convergent).
A further point has occurred to me. There is a celebrated theorem of Dirichlet which states that if a and b have no common factor greater than 1 then there are infinitely many primes of the form an+b. The standard proof of this is to show that the sum over all such primes p of (ln p)/p diverges, thus using the counterintuitive line of reasoning I mentioned in my last post. The proof of this result is very hard and I’m not going to attempt to post it.
Similarly there is a long-standing conjecture that there are infinitely many primes p for which p+2 is also prime. Someone ( unfortunately I cannot remember who) tried to prove this by showing that the sum of the reciprocals of such primes diverges. This strategy was doomed to failure though, because he was in fact able to prove that the sum in question actually converges.
Hope I didn’t miss a link to this article in the
New York Times yesterday. Apologies if someone already linked it.
Wonder if this prompted the OP.
I started reading the article but it went way over my head after a while
That article requires registration. Would you mind copying a few relevant paragraphs?
Actually it does use the fact that there are an infinite number of primes. The very first assumption (*) is not true if there are only a finite number.
OOPS! Never mind. If there are only a finite number P of primes, then (*) is true for all N > P.
This is not true at all. If a[sub]k[/sub] is 0 for k>N, then it is certainly true that
a[sub]N+1[/sub] + a[sub]N+2[/sub] + a[sub]N+3[/sub] +… <1/2
ultrafilter, sorry for that. When linking to the NYT I usually add that you may need to register, but that it is free.
As to the article, it talks about “Bernhard Riemann in 1859 in a paper about the distribution of prime numbers, is still widely considered to be one of the greatest unsolved problems in mathematics, sure to wreath its conqueror with glory”
“Solving the [Reimann] hypothesis could lead to new encryption schemes and possibly provide tools that would make existing schemes, which depend on the properties of prime numbers, more vulnerable.”
It’s best to read the article to see how complex this is. I don’t want to quote any more from the article because I may be selecting parts out of context that convey the wrong idea.
OK. You’ve got the basic idea right. There’s more information available here, actually probably much more than anyone would want.
I just wanted to pop in a quick thanks to ultrafilter and Jabba for that sum of the reciprocals theorem. I got curious about that way back in high school and wrote a computer program to do the partial sums, but I gave up on it sometime after it had passed e and before [symbol]p[/symbol] (which took about a day of runtime, but then my code probably wasn’t too efficient).
I would have thought that the proof would use the asymptotic form of the function pi(x), but I never got around to actually trying to work it out.