## Euclidean generation of prime numbers

Expand Messages
• Euclid s proof that there are infinitely many prime numbers gives a method of generating prime numbers: Start with a set S = {p_1, ..., p_r}. Find q := (p_1
Message 1 of 40 , Jan 31, 2007
• 0 Attachment
Euclid's proof that there are infinitely many prime numbers gives a
method of generating prime numbers:

Find q := (p_1 ... p_r) + 1.
Case 1: q is prime, and we put it in S.
Case 2: q is not prime, and we put its smallest prime factor in S.
(Of course, even in Case 1 we are putting the smallest factor of q in S).

Is there any literature about the properties of this algorithm, e.g.
1. How fast does max(S) grow?
2. If p is the least prime number not in S, how long will it take to
generate p?
3. Can we say anything about the prime numbers that are never generated
in this way?
4. Can we get arbitrarily long runs of consecutive Case1's, or
consecutive Case2's?

And what if we take the largest prime factor, instead of the smallest
one? Or if we use q:= (p_1 ... p_r) - 1?

Any references would be appreciated.

Thanks,
Alastair

--
http://www.AlastairFarrugia.net
• For example 2 adjacent gaps cannot be equal if they aren t multiple of 6. For example the gap between 2 pairs of twins is at least 4. For example each prime
Message 40 of 40 , Feb 7, 2007
• 0 Attachment
For example 2 adjacent gaps cannot be equal if they aren't multiple of
6. For example the gap between 2 pairs of twins is at least 4. For
example each prime number has the form 2n+/-1, 3n+/-1, 4n+/-1, 6n+/-1.
Each pair of twins has the form 12n+-1, there are approximate formulas
for the nth prime and the number of primes < x and so on. You cannot
call all this random ore unpredictable. Of course the prime numbers are
distributed as regularly as possible, that's a tautology. In
mathematics everything is as regular as possible. Is pi random? Build
P=2,357111317192329, and you have the same case as pi. Consider the
primes to be an irrational number, and there are no problems. If you
mean there is no formula f(n) which produces primes for each n, then
you are right. In this sense primes are random. (I am not quite sure 
there is a formula p=[k^n^3] (H.W.Mills) which is said to produce only
prime numbers). If you define "formula" as an algorithm, as a
calculation instruction such as the sieve of Eratosthenes, then the
primes are not random but simply what they are. Perhaps the compound
numbers are random? Or are they only non-transparently complicated?

Werner
Your message has been successfully submitted and would be delivered to recipients shortly.