Catch up on stories from the past week (and beyond) at the Slashdot story archive

typodupeerror
What's the story with these ads on Slashdot? Check out our new blog post to find out. ×

## JournalJournal: primes solved

After many false dawns, I think that I have solved the problem of discovering the underlying structure in the natural numbers that leads to the fascinating sequence of the primes, and the answer turns out to be cyclic groups, so simple that the basic idea is taught at primary level as clock arithmetic.
The primes are generated by a set of cyclic groups. Start by setting all the groups to zero, and move along the number line clocking all of the groups for each step. When all of the groups are at non-zero values, then the number of steps is prime. In practice we only need to use those groups corresponding to primes greater than 1 and less than or equal to the square root of the next prime (which we need to guess and add a safety margin). If we wish to avoid checking even numbers, we drop prime group 2, and "double clock" the groups.
Here is a VBA function of the basic algorithm A public array "primes" is used to hold the primes available to set up clocks, this can easily be loaded on the fly by calling the function, or just pull the body of the code and make a routine to generate all the primes you want by keeping the cycle states from one target to the next.
===================
Public Function genp(seed As Long) As Long
'needs primes list upto sqr of target
'seed must be odd, non prime works, if prime result is next prime NOT seed
Dim limit As Long
Dim cycles() As Long
Dim i As Long, k As Long, l As Long
Dim found As Boolean
'find index to largest cycle in play
l = Sqr(2 * seed) ' bigger than needed
limit = 1
While primes(limit) l
limit = limit + 1
Wend
limit = limit - 2 'twiddle to avoid 1&2
'set up cyclic groups in play for prime
ReDim cycles(1 To limit, 1 To 2) 'two arrays might be faster
' set groups to states at prime
For i = 1 To limit
k = primes(i + 2)
cycles(i, 1) = k
cycles(i, 2) = seed Mod k
Next
' now start looking for genp
found = False
genp = seed
Do
genp = genp + 2 'skip evens by double clocking cycles
found = True
For i = 1 To limit 'loop goes on after zero to keep sync
' cycles(i, 2) = icinc(cycles(i, 2), cycles(i, 1)) '2 calls for clarity
' cycles(i, 2) = icinc(cycles(i, 2), cycles(i, 1)) ' a faster in line method
cycles(i, 2) = cycles(i, 2) + 2
If (cycles(i, 2) = cycles(i, 1)) Then cycles(i, 2) = 0
If (cycles(i, 2) = cycles(i, 1) + 1) Then cycles(i, 2) = 1
If (cycles(i, 2) = 0) Then found = False ' this is the primality test
Next i
Loop Until (found)
End Function

================
I think that this could be recoded to optimise multi-thread hardware, and I have variations which avoid the need to use modulus to get start clock settings. For instance a function which generates a list of primes starting from 1 (all clocks are 1) and if we start with a factorial then all clocks are zero.

I would be grateful for any comments on this idea, and if anybody implements the idea as a excel binary addin I would love a copy.

I was playing poker the other night... with Tarot cards. I got a full house and 4 people died. -- Steven Wright

Working...