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.