Judd's Prime Number Generator Sequence
--------------------------------------
In the winter of 1989 Mr. Laeser had some contest going back at the
high school where the idea was to write a program which generated (and printed)
the most prime numbers in a certain time limit. The best algorithms are of
course sieves and the like, but this is what I came up with one morning while
standing in the shower, while home for Christmas.
(Have you ever noticed that standing in the shower is a great place for
inspiration? I find my best inspirations come either while standing in the
shower or while I am waking up -- go figure.)
Anyways, it goes a little something like this: consider the two
sequences 6n+1 and 6n-1:
6n-1 6n+1
---- ----
5 7
11 13
17 19
23 25 <--- 5^2
29 31
5*7 --> 35 37
41 43
47 49 <-- 7*7
53 55 <-- 5*11
59 61
5*13 -> 65 67
71 73
7*11 -> 77 79
83 85 <-- 5*17
89 91 <-- 7*13
5*19 -> 95 97
101 103
107 109
113 115 <-- 5*23
119 121 <-- 11*11
...
As my friend George pointed out, this is basically all the numbers sans
multiples of two, three, and four. At one point I used to have a lot more to
say about the sequence, for instance I think there is some sort of pattern
to when the next non-primes will appear. Let's make some observations:
- Observe that all non-prime numbers which are combinations of the
primes are in this list, and in order (i.e. the first primes
generated are 5,7,11,13 and all combinations of these will be in
the list, necessarily in order of magnitude, i.e. 5*5, 5*7, 7*7,
5*11, 5*13, ...)
- Consider the second list. The first multiple of 5 is 5*5. 5 more
entries down the list is 5*11. Five more down is 5*17. (We have
to skip every other prime). How about 7? Sure enough, 7 away from
7*7 is 7*13. A similar observation holds for the first list.
This means that you could apply a sieve to this list as well.
- There are 'list crossovers' -- 11 belongs to the first list, but
11*11 is in the second list. (A naive sieve would miss it.)
- On the other hand, all perfect squares will lie in the second
list. Squares of primes in the first list will be at position
(6n^2 - 2n) and squares of primes in the second list will be
the (6n^2 + 2n)th element in the seond list, where n is the
position of the prime to be squared.
- If you mash the lists together, there is still some sort of ordering
to the appearance of non-primes. Consder 5: the next multiple will
three away in one direction, and seven away in the other direction.
Seven: five away in one direction, and nine in the other.
Eleven: seven and fifteen.
- Some day, like after PhD qualifiers, I will sit down and formalize
these results.