×

Welcome to the Slashdot Beta site -- learn more here. Use the link in the footer or click here to return to the Classic version of Slashdot.

Thank you!

Before you choose to head back to the Classic look of the site, we'd appreciate it if you share your thoughts on the Beta; your feedback is what drives our ongoing development.

Beta is different and we value you taking the time to try it out. Please take a look at the changes we've made in Beta and  learn more about it. Thanks for reading, and for making the site better!

primes solved

HarryatRock (1494393) writes | more than 2 years ago

User Journal 0

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 a

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.

0 comment

Check for New Comments
Slashdot Account

Need an Account?

Forgot your password?

Don't worry, we never post anything without your permission.

Submission Text Formatting Tips

We support a small subset of HTML, namely these tags:

  • b
  • i
  • p
  • br
  • a
  • ol
  • ul
  • li
  • dl
  • dt
  • dd
  • em
  • strong
  • tt
  • blockquote
  • div
  • quote
  • ecode

"ecode" can be used for code snippets, for example:

<ecode>    while(1) { do_something(); } </ecode>
Sign up for Slashdot Newsletters
Create a Slashdot Account

Loading...