Want to read Slashdot from your mobile device? Point it at m.slashdot.org and keep reading!


Forgot your password?
User Journal

Journal HarryatRock's Journal: 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
        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
        ' now start looking for genp
        found = False
        genp = seed
                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.

This discussion has been archived. No new comments can be posted.

primes solved

Comments Filter:

We can found no scientific discipline, nor a healthy profession on the technical mistakes of the Department of Defense and IBM. -- Edsger Dijkstra