These two facts are not unrelated. If we have a prime (or any number, really) of the form p = 6x-1, then p^2 = 36x^2-12x +1 = 12(3x^2 - x) + 1 = 12u+1 for u = 3x^2 - x.

Similarly if we have a prime of the form p = 6x+1, then p^2 = 12u+1 for u = 3x^2 + x.

So the second fact does not place a stronger restriction on primes than the first.

By “formula” could you mean a deterministic black box that tries successively larger integers for division by all the integers smaller than their square root, and spits them out, or returns the nth one when you enter n? If your “formula” can do simple conditionals and iterating and the like, that would be a formula that can produce all primes.

I guess I’m asking about the definition of “formula”, but it seems like it’d be kind of hamstringing mathematics to define it such that this obviously feasible black box isn’t included in the definition.

Starting with 2 in the Fractran machine’s only register, the powers-of-two 2[sup]2[/sup], 2[sup]3[/sup], 2[sup]5[/sup], 2[sup]7[/sup], 2[sup]11[/sup], 2[sup]13[/sup], 2[sup]17[/sup], 2[sup]19[/sup], 2[sup]23[/sup], … are generated in order. It’s a ridiculously slow way to generate the primes but it seems impressive that Conway could come up with such a brief prime-generation program in his peculiar Fractran language.

A number is neither divisible by 2 nor by 3 just in case it is of the form 6x - 1 or 6x + 1; also, this happens just in case its square is of the form 12x + 1.

These in turn are instances of the following:

A number is neither divisible by n1, nor n2, nor n3, …, just in case its remainder modulo the least common multiple of (n1, n2, n3, …) is also divisible by none of them. From this list of possible remainders for the number itself, we can also construct analogously a list of possible remainders for the number’s square.

These are rather trivial observations, and not of any great boon in enumerating primes or checking for primality.

Just to continue the pattern a bit further, to make it clear:

Don’t even look at 4-- You’ve already weeded it out as divisible by two.
Weed out all numbers divisible by 5 (except 5)
Don’t look at 6-- Already weeded out
Weed out all numbers divisible by 7 (except 7)
8, 9, and 10 are already weeded out
Weed out all numbers divisible by 11 (except 11)

So, to turn Chronos’ description into pseudocode (and thereby rob it of its poetic charm, I’m afraid):

Create array A consisting of elements A[2] to A[n].
Initialize all elements of A to TRUE initially.
For each *i* from 2 to *n*:
If A[*i*] is TRUE:
For each *k* where *k* is a multiple of *i* and *i < k <= n*:
A[*k*] := FALSE

Afterwards, all the elements of A which are still TRUE, are prime numbers.

This is the basic Sieve of Eratosthenes, and it’s quite efficient. There are still a few optimizations possible, however:

[ul]
[li]In the outer loop, you actually only need to go up to the square root of n. Any non-prime numbers above sqrt(n) will have been sieved out at that point.[/li][li]For the inner loop, you can start sieving at i squared rather than at the first multiple of i greater than i itself. That’s because any number between i and i squared must be either prime or a multiple of a number below i.[/li][li]And finally we can apply the optimization which the OP started the thread with: there’s no point in wasting space in array A on numbers which are a multiple of 2 or 3, since all of those will never be prime anyway. So you can rewrite the algorithm so that only numbers of the form (x * 6 +/- 1) are ever considered.[/li][/ul]

I wrote a program in BASIC to find primes. It worked, but it took like an hour to test the first couple of hundred integers. It would have eventually broken when the numbers got too big, but I lost patience with it long before then.

With the Sieve of Eratosthenes I would expect you could find the first couple of hundred integers in a matter of seconds, even in BASIC on a Commodore 64.

Of course, if you use this algorithm:

for *i* from 2 to *n*:
*prime* = TRUE
for *x* from 2 to *i - 1*:
if *i* is dividable by *x*:
*prime* = FALSE
if *prime* is TRUE:
print *i* + " is a prime number!"

… then it can take a while even on a fast modern PC…

Of course, you can take this a step further, too, and only include numbers in the array that aren’t multiples of 2, 3, or 5. Or 2, 3, 5, and 7, and so on. Or, of course, you could just exclude the even numbers, for two-thirds of the benefit of the 6n±1 method. It all depends on how much you value speed of the program vs. complexity (which usually translates to time spent programming).