Loading ...
Sorry, an error occurred while loading the content.

Easy formula for next prime

Expand Messages
  • Victor Reijkersz
    Ok.... working on what stmaddox found and what i found out myself its possible to determine in an easy way without sieving if a number is prime or not. If
    Message 1 of 16 , Jul 26, 2010
    • 0 Attachment
      Ok.... working on what stmaddox found and what i found out myself its possible to determine in an easy way without sieving if a number is prime or not.

      If (((LastPTot * n)*(LastPSize*(LastP-1)) /n) mod n)>0 then the n is prime.

      But let me explain:

      The number 3 has a pattern-size of 1 and a pattern-total of 6.
      The number 5 has a pattern-size of 2 and a pattern-total of 30
      The number 7 has a pat.size of 8 and a pat-total of 210
      etc.. see previous posts by stmaddox and me about how to calculate pattern size and pattern-total. (or see VB code below)

      What this new formula does is basicly start at number 3 knowing thats a prime and then trying the next number.

      the next number has a pattern size of (last pattern size * (last prime-1))

      the next number has a pattern total of (last pattern total * next number).

      In case of 4 that is a pattern total of 24 and a pattern size of 2.
      we then do 24*2=48, 48/4= 12, 12/4 = 3.0 (no remainder => thus not prime)

      then we try 5. pattern total of 30, pattern size of 2
      we do 30*2= 60. 60/5= 12 , 12/5 =2.x (remainder => thus prime)

      then we try 6. pattern total of 180, pattern size of 8
      we do 180*6=1440. 1440/6=240, 240/6=40.0 (no remainder, not prime)

      then we try 7. pattern total of 210, patsize of 8
      210*8=1680. 1680/7= 240. 240/7=34.x (remainder.. thus prime)

      It works all the way the first 100 primes or so. Though of course the numbers get awfully big.

      prime: 3, time needed: 00:00:00
      prime: 5, time needed: 00:00:00
      prime: 7, time needed: 00:00:00
      prime: 11, time needed: 00:00:00
      prime: 13, time needed: 00:00:00
      prime: 17, time needed: 00:00:00.0156250
      prime: 19, time needed: 00:00:00
      prime: 23, time needed: 00:00:00.0312500
      prime: 29, time needed: 00:00:00.0312500
      prime: 31, time needed: 00:00:00.0156250
      prime: 37, time needed: 00:00:00.0937500
      prime: 41, time needed: 00:00:00.0625000
      prime: 43, time needed: 00:00:00.0468750
      prime: 47, time needed: 00:00:00.0937500
      prime: 53, time needed: 00:00:00.1875000
      prime: 59, time needed: 00:00:00.2343750
      prime: 61, time needed: 00:00:00.0937500
      prime: 67, time needed: 00:00:00.3281250
      prime: 71, time needed: 00:00:00.2500000
      prime: 73, time needed: 00:00:00.1562500
      prime: 79, time needed: 00:00:00.4531250
      prime: 83, time needed: 00:00:00.3906250
      prime: 89, time needed: 00:00:00.7031250
      prime: 97, time needed: 00:00:01.0312500
      prime: 101, time needed: 00:00:00.5781250
      prime: 103, time needed: 00:00:00.2968750
      prime: 107, time needed: 00:00:00.6406250
      prime: 109, time needed: 00:00:00.3437500
      prime: 113, time needed: 00:00:00.7656250
      prime: 127, time needed: 00:00:02.9687500
      prime: 131, time needed: 00:00:00.9375000
      etc...

      basicly in formula shape the prime check is as follows:

      LastPtot = Last Pattern Total
      LastPSize = Last Pattern Size
      LastP = Last Prime (and pattern)
      n = current number being tested

      If (((LastPTot * n)*(LastPSize*(LastP-1)) /n) mod n)>0 then the n is prime.

      here is the code i used to test the formula:
      s = ""
      p = "3"
      curpatsize = "1"
      curtot = "6"
      tim1 = Now
      TextBox1.Text = ""
      For i = 1 To 99
      tsp = Now.Subtract(tim1)
      TextBox1.Text += "prime: " + p + ", time needed: " + tsp.ToString() + vbCrLf
      tim1 = Now
      Application.DoEvents()
      lasttot = curtot
      lastp = p
      curpatsize = Module1.IntMultiply(curpatsize, IntSubtract(lastp, 1))
      ok = 0
      Do
      p = IntAddition(p, 1)
      curtot = IntMultiply(lasttot, p)
      test = IntDivide(IntMultiply(curtot, curpatsize), p)
      If InStr(test, "r0") > 0 Then test = Mid$(test, 1, Len(test) - 2)
      test = IntDivide(test, p)
      If InStr(test, "r0") = 0 Then ok = 1
      Loop While ok = 0
      Next i

      bottom line: seems to work as a charm.

      kind regards,
      Victor Reijkersz
    • Yann GUIDON
      Hi all ! ... I will try to take the time to examine your works. Before I can, there is at least a good news : the article that I wrote about my version is now
      Message 2 of 16 , Jul 26, 2010
      • 0 Attachment
        Hi all !

        >Le lun 26/07/10 22:35 , "Victor Reijkersz" a écrit::
        >Ok.... working on what stmaddox found and what i found out myself its possible to determine in an easy way without sieving if a number is prime or not.
        I will try to take the time to examine your works.

        Before I can, there is at least a good news : the article that I wrote about my version is now public under Creative Commons 2.0 !
        http://www.unixgarden.com/index.php/programmation/un-algorithme-additif-et-iteratif-pour-construire-les-nombres-premiers
        I know that the text is french but the numbers and sequences will look familiar.

        >here is the code i used to test the formula:
        I don't recognize the language :-/

        >bottom line: seems to work as a charm.
        fine, I'll have to check.


        >kind regards,
        thanks for sharing,

        >Victor Reijkersz
        yg
      • Victor Reijkersz
        Or to put it even more simply.... without references to the patterns.... which just seem to confuse a lot of people: IF ((multiplication_of_all_primes_found *
        Message 3 of 16 , Jul 27, 2010
        • 0 Attachment
          Or to put it even more simply.... without references to the patterns.... which just seem to confuse a lot of people:

          IF ((multiplication_of_all_primes_found * n ) * ( multiplication_of_all_primes_found_minus_one * (n -1)) mod n^2 > 0 THEN n=prime

          axioma: 2 is prime

          examples

          n=3 => ((2 * 3 ) * ( 1 * 2 )) mod 9 = 0.333 => is prime
          n=4 => ((6 * 4) * ( 2 * 3)) mod 16 = 0
          n=5 => ((6 * 5) * (2 * 4)) mod 25 = 0.6 => is prime
          n=6 => ((30 * 6) * (8 * 5)) mod 36 = 0
          n=7 => ((30 * 7) * (8 * 6)) mod 49 =0.714.. => is prime
          n=8 => ((210 * 8) * (48 * 7) mod 64 = 0
          etc..
          ect..
          until infinity i strongly belief.

          best,
          Vic
          vic@...

          notes on above forumla
          at n=4 the 6 in (6*4) = [2*3], the 2 in (2*3) = [1*2]
          at n=6 the 30 in (30*6) = [2*3*5], the 8 in (8*5) = [1*2*4]
          at n=8 the 210 in (210*8) = [2*3*5*7], the 48 in (48*7) = [1*2*4*6]

          --- In primenumbers@yahoogroups.com, "Victor Reijkersz" <vic@...> wrote:
          >
          > Ok.... working on what stmaddox found and what i found out myself its possible to determine in an easy way without sieving if a number is prime or not.
          >
          > If (((LastPTot * n)*(LastPSize*(LastP-1)) /n) mod n)>0 then the n is prime.
          >
          > But let me explain:
          >
          > The number 3 has a pattern-size of 1 and a pattern-total of 6.
          > The number 5 has a pattern-size of 2 and a pattern-total of 30
          > The number 7 has a pat.size of 8 and a pat-total of 210
          > etc.. see previous posts by stmaddox and me about how to calculate pattern size and pattern-total. (or see VB code below)
          >
          > What this new formula does is basicly start at number 3 knowing thats a prime and then trying the next number.
          >
          > the next number has a pattern size of (last pattern size * (last prime-1))
          >
          > the next number has a pattern total of (last pattern total * next number).
          >
          > In case of 4 that is a pattern total of 24 and a pattern size of 2.
          > we then do 24*2=48, 48/4= 12, 12/4 = 3.0 (no remainder => thus not prime)
          >
          > then we try 5. pattern total of 30, pattern size of 2
          > we do 30*2= 60. 60/5= 12 , 12/5 =2.x (remainder => thus prime)
          >
          > then we try 6. pattern total of 180, pattern size of 8
          > we do 180*6=1440. 1440/6=240, 240/6=40.0 (no remainder, not prime)
          >
          > then we try 7. pattern total of 210, patsize of 8
          > 210*8=1680. 1680/7= 240. 240/7=34.x (remainder.. thus prime)
          >
          > It works all the way the first 100 primes or so. Though of course the numbers get awfully big.
          >
          > prime: 3, time needed: 00:00:00
          > prime: 5, time needed: 00:00:00
          > prime: 7, time needed: 00:00:00
          > prime: 11, time needed: 00:00:00
          > prime: 13, time needed: 00:00:00
          > prime: 17, time needed: 00:00:00.0156250
          > prime: 19, time needed: 00:00:00
          > prime: 23, time needed: 00:00:00.0312500
          > prime: 29, time needed: 00:00:00.0312500
          > prime: 31, time needed: 00:00:00.0156250
          > prime: 37, time needed: 00:00:00.0937500
          > prime: 41, time needed: 00:00:00.0625000
          > prime: 43, time needed: 00:00:00.0468750
          > prime: 47, time needed: 00:00:00.0937500
          > prime: 53, time needed: 00:00:00.1875000
          > prime: 59, time needed: 00:00:00.2343750
          > prime: 61, time needed: 00:00:00.0937500
          > prime: 67, time needed: 00:00:00.3281250
          > prime: 71, time needed: 00:00:00.2500000
          > prime: 73, time needed: 00:00:00.1562500
          > prime: 79, time needed: 00:00:00.4531250
          > prime: 83, time needed: 00:00:00.3906250
          > prime: 89, time needed: 00:00:00.7031250
          > prime: 97, time needed: 00:00:01.0312500
          > prime: 101, time needed: 00:00:00.5781250
          > prime: 103, time needed: 00:00:00.2968750
          > prime: 107, time needed: 00:00:00.6406250
          > prime: 109, time needed: 00:00:00.3437500
          > prime: 113, time needed: 00:00:00.7656250
          > prime: 127, time needed: 00:00:02.9687500
          > prime: 131, time needed: 00:00:00.9375000
          > etc...
          >
          > basicly in formula shape the prime check is as follows:
          >
          > LastPtot = Last Pattern Total
          > LastPSize = Last Pattern Size
          > LastP = Last Prime (and pattern)
          > n = current number being tested
          >
          > If (((LastPTot * n)*(LastPSize*(LastP-1)) /n) mod n)>0 then the n is prime.
          >
          > here is the code i used to test the formula:
          > s = ""
          > p = "3"
          > curpatsize = "1"
          > curtot = "6"
          > tim1 = Now
          > TextBox1.Text = ""
          > For i = 1 To 99
          > tsp = Now.Subtract(tim1)
          > TextBox1.Text += "prime: " + p + ", time needed: " + tsp.ToString() + vbCrLf
          > tim1 = Now
          > Application.DoEvents()
          > lasttot = curtot
          > lastp = p
          > curpatsize = Module1.IntMultiply(curpatsize, IntSubtract(lastp, 1))
          > ok = 0
          > Do
          > p = IntAddition(p, 1)
          > curtot = IntMultiply(lasttot, p)
          > test = IntDivide(IntMultiply(curtot, curpatsize), p)
          > If InStr(test, "r0") > 0 Then test = Mid$(test, 1, Len(test) - 2)
          > test = IntDivide(test, p)
          > If InStr(test, "r0") = 0 Then ok = 1
          > Loop While ok = 0
          > Next i
          >
          > bottom line: seems to work as a charm.
          >
          > kind regards,
          > Victor Reijkersz
          >
        • Yann Guidon
          ... notes : - multiplication_of_all_primes_found = primorial = p# cf http://en.wikipedia.org/wiki/Primorial -
          Message 4 of 16 , Jul 27, 2010
          • 0 Attachment
            Victor Reijkersz wrote:
            > Or to put it even more simply.... without references to the patterns.... which just seem to confuse a lot of people:
            > IF ((multiplication_of_all_primes_found * n ) * ( multiplication_of_all_primes_found_minus_one * (n -1)) mod n^2 > 0 THEN n=prime

            notes :

            - "multiplication_of_all_primes_found" = "primorial" = p#
            cf http://en.wikipedia.org/wiki/Primorial

            - "multiplication_of_all_primes_found_minus_one" = EulerPhi(p#)
            (Euler's Phi function)

            However I think that your primality "formula" is hiding the inherent computational
            complexity of a brute-force prime search because the primorial and EulerPhi(p#)
            are much more difficult (together) to compute than trial division.
            As such, your post is not a breakthrough.
            However it can have interesting properties.
            Have fun finding them !

            > best,
            > Vic
            > vic@...
            yg
            --
            http://ygdes.com / http://yasep.org
          • Martin Aaronson
            Reply to Victor Reijkersz and Prime Numbers Group. Why are people still looking for patterns in prime numbers? If there were patterns, prime numbers would come
            Message 5 of 16 , Jul 27, 2010
            • 0 Attachment
              Reply to Victor Reijkersz and Prime Numbers Group.
              Why are people still looking for patterns in prime numbers? If there
              were patterns, prime numbers would come to an end and then start again ­ a
              true paradox. If 2 follows 1, and 3 follows 2, how can there possibly be a
              pattern? Marty Aaronson

              ------ Forwarded Message
              > From: Victor Reijkersz <vic@...>
              > Date: Tue, 27 Jul 2010 07:13:39 -0000
              > To: <primenumbers@yahoogroups.com>
              > Subject: [PrimeNumbers] Re: Easy formula for next prime... cant make it any
              > easier.
              >
              > Or to put it even more simply.... without references to the patterns.... which
              > just seem to confuse a lot of people:
              >
              > IF ((multiplication_of_all_primes_found * n ) * (
              > multiplication_of_all_primes_found_minus_one * (n -1)) mod n^2 > 0 THEN
              > n=prime
              >
              > axioma: 2 is prime
              >
              > examples
              >
              > n=3 => ((2 * 3 ) * ( 1 * 2 )) mod 9 = 0.333 => is prime
              > n=4 => ((6 * 4) * ( 2 * 3)) mod 16 = 0
              > n=5 => ((6 * 5) * (2 * 4)) mod 25 = 0.6 => is prime
              > n=6 => ((30 * 6) * (8 * 5)) mod 36 = 0
              > n=7 => ((30 * 7) * (8 * 6)) mod 49 =0.714.. => is prime
              > n=8 => ((210 * 8) * (48 * 7) mod 64 = 0
              > etc..
              > ect..
              > until infinity i strongly belief.
              >
              > best,
              > Vic
              > vic@... <mailto:vic%40xs4all.nl>
              >
              > notes on above forumla
              > at n=4 the 6 in (6*4) = [2*3], the 2 in (2*3) = [1*2]
              > at n=6 the 30 in (30*6) = [2*3*5], the 8 in (8*5) = [1*2*4]
              > at n=8 the 210 in (210*8) = [2*3*5*7], the 48 in (48*7) = [1*2*4*6]
              >
              > --- In primenumbers@yahoogroups.com <mailto:primenumbers%40yahoogroups.com> ,
              > "Victor Reijkersz" <vic@...> wrote:
              >> >
              >> > Ok.... working on what stmaddox found and what i found out myself its
              >> possible to determine in an easy way without sieving if a number is prime or
              >> not.
              >> >
              >> > If (((LastPTot * n)*(LastPSize*(LastP-1)) /n) mod n)>0 then the n is prime.
              >> >
              >> > But let me explain:
              >> >
              >> > The number 3 has a pattern-size of 1 and a pattern-total of 6.
              >> > The number 5 has a pattern-size of 2 and a pattern-total of 30
              >> > The number 7 has a pat.size of 8 and a pat-total of 210
              >> > etc.. see previous posts by stmaddox and me about how to calculate pattern
              >> size and pattern-total. (or see VB code below)
              >> >
              >> > What this new formula does is basicly start at number 3 knowing thats a
              >> prime and then trying the next number.
              >> >
              >> > the next number has a pattern size of (last pattern size * (last prime-1))
              >> >
              >> > the next number has a pattern total of (last pattern total * next number).
              >> >
              >> > In case of 4 that is a pattern total of 24 and a pattern size of 2.
              >> > we then do 24*2=48, 48/4= 12, 12/4 = 3.0 (no remainder => thus not prime)
              >> >
              >> > then we try 5. pattern total of 30, pattern size of 2
              >> > we do 30*2= 60. 60/5= 12 , 12/5 =2.x (remainder => thus prime)
              >> >
              >> > then we try 6. pattern total of 180, pattern size of 8
              >> > we do 180*6=1440. 1440/6=240, 240/6=40.0 (no remainder, not prime)
              >> >
              >> > then we try 7. pattern total of 210, patsize of 8
              >> > 210*8=1680. 1680/7= 240. 240/7=34.x (remainder.. thus prime)
              >> >
              >> > It works all the way the first 100 primes or so. Though of course the
              >> numbers get awfully big.
              >> >
              >> > prime: 3, time needed: 00:00:00
              >> > prime: 5, time needed: 00:00:00
              >> > prime: 7, time needed: 00:00:00
              >> > prime: 11, time needed: 00:00:00
              >> > prime: 13, time needed: 00:00:00
              >> > prime: 17, time needed: 00:00:00.0156250
              >> > prime: 19, time needed: 00:00:00
              >> > prime: 23, time needed: 00:00:00.0312500
              >> > prime: 29, time needed: 00:00:00.0312500
              >> > prime: 31, time needed: 00:00:00.0156250
              >> > prime: 37, time needed: 00:00:00.0937500
              >> > prime: 41, time needed: 00:00:00.0625000
              >> > prime: 43, time needed: 00:00:00.0468750
              >> > prime: 47, time needed: 00:00:00.0937500
              >> > prime: 53, time needed: 00:00:00.1875000
              >> > prime: 59, time needed: 00:00:00.2343750
              >> > prime: 61, time needed: 00:00:00.0937500
              >> > prime: 67, time needed: 00:00:00.3281250
              >> > prime: 71, time needed: 00:00:00.2500000
              >> > prime: 73, time needed: 00:00:00.1562500
              >> > prime: 79, time needed: 00:00:00.4531250
              >> > prime: 83, time needed: 00:00:00.3906250
              >> > prime: 89, time needed: 00:00:00.7031250
              >> > prime: 97, time needed: 00:00:01.0312500
              >> > prime: 101, time needed: 00:00:00.5781250
              >> > prime: 103, time needed: 00:00:00.2968750
              >> > prime: 107, time needed: 00:00:00.6406250
              >> > prime: 109, time needed: 00:00:00.3437500
              >> > prime: 113, time needed: 00:00:00.7656250
              >> > prime: 127, time needed: 00:00:02.9687500
              >> > prime: 131, time needed: 00:00:00.9375000
              >> > etc...
              >> >
              >> > basicly in formula shape the prime check is as follows:
              >> >
              >> > LastPtot = Last Pattern Total
              >> > LastPSize = Last Pattern Size
              >> > LastP = Last Prime (and pattern)
              >> > n = current number being tested
              >> >
              >> > If (((LastPTot * n)*(LastPSize*(LastP-1)) /n) mod n)>0 then the n is prime.
              >> >
              >> > here is the code i used to test the formula:
              >> > s = ""
              >> > p = "3"
              >> > curpatsize = "1"
              >> > curtot = "6"
              >> > tim1 = Now
              >> > TextBox1.Text = ""
              >> > For i = 1 To 99
              >> > tsp = Now.Subtract(tim1)
              >> > TextBox1.Text += "prime: " + p + ", time needed: " + tsp.ToString() +
              >> vbCrLf
              >> > tim1 = Now
              >> > Application.DoEvents()
              >> > lasttot = curtot
              >> > lastp = p
              >> > curpatsize = Module1.IntMultiply(curpatsize, IntSubtract(lastp, 1))
              >> > ok = 0
              >> > Do
              >> > p = IntAddition(p, 1)
              >> > curtot = IntMultiply(lasttot, p)
              >> > test = IntDivide(IntMultiply(curtot, curpatsize), p)
              >> > If InStr(test, "r0") > 0 Then test = Mid$(test, 1, Len(test) - 2)
              >> > test = IntDivide(test, p)
              >> > If InStr(test, "r0") = 0 Then ok = 1
              >> > Loop While ok = 0
              >> > Next i
              >> >
              >> > bottom line: seems to work as a charm.
              >> >
              >> > kind regards,
              >> > Victor Reijkersz
              >> >
              >
              >
              >
              >
              >
              >
              > Reply to sender <mailto:vic@...?subject=Re: Easy formula for next
              > prime... cant make it any easier.> | Reply to group
              > <mailto:primenumbers@yahoogroups.com?subject=Re: Easy formula for next
              > prime... cant make it any easier.> | Reply via web post
              > <http://groups.yahoo.com/group/primenumbers/post;_ylc=X3oDMTJxcXZpNDRyBF9TAzk3
              > MzU5NzE0BGdycElkAzI2MDc2MTIEZ3Jwc3BJZAMxNzA1MDgzMzg4BG1zZ0lkAzIxNjU1BHNlYwNmdH
              > IEc2xrA3JwbHkEc3RpbWUDMTI4MDIxNDgzMQ--?act=reply&messageNum=21655> | Start a
              > New Topic
              > <http://groups.yahoo.com/group/primenumbers/post;_ylc=X3oDMTJldWhsc3BxBF9TAzk3
              > MzU5NzE0BGdycElkAzI2MDc2MTIEZ3Jwc3BJZAMxNzA1MDgzMzg4BHNlYwNmdHIEc2xrA250cGMEc3
              > RpbWUDMTI4MDIxNDgzMQ-->
              > Messages in this topic
              > <http://groups.yahoo.com/group/primenumbers/message/21651;_ylc=X3oDMTM2b3NldWd
              > qBF9TAzk3MzU5NzE0BGdycElkAzI2MDc2MTIEZ3Jwc3BJZAMxNzA1MDgzMzg4BG1zZ0lkAzIxNjU1B
              > HNlYwNmdHIEc2xrA3Z0cGMEc3RpbWUDMTI4MDIxNDgzMQR0cGNJZAMyMTY1MQ--> (3)
              >
              > Recent Activity:
              > * New Members
              > <http://groups.yahoo.com/group/primenumbers/members;_ylc=X3oDMTJmN2cwanFtBF9TA
              > zk3MzU5NzE0BGdycElkAzI2MDc2MTIEZ3Jwc3BJZAMxNzA1MDgzMzg4BHNlYwN2dGwEc2xrA3ZtYnJ
              > zBHN0aW1lAzEyODAyMTQ4MzE-?o=6> 1
              > * New Photos
              > <http://groups.yahoo.com/group/primenumbers/spnew;_ylc=X3oDMTJmZmtkZ2g3BF9TAzk
              > 3MzU5NzE0BGdycElkAzI2MDc2MTIEZ3Jwc3BJZAMxNzA1MDgzMzg4BHNlYwN2dGwEc2xrA3ZwaG90B
              > HN0aW1lAzEyODAyMTQ4MzE-> 2
              >
              > Visit Your Group
              > <http://groups.yahoo.com/group/primenumbers;_ylc=X3oDMTJlYWhxdTE3BF9TAzk3MzU5N
              > zE0BGdycElkAzI2MDc2MTIEZ3Jwc3BJZAMxNzA1MDgzMzg4BHNlYwN2dGwEc2xrA3ZnaHAEc3RpbWU
              > DMTI4MDIxNDgzMQ-->
              >
              > Unsubscribe by an email to: primenumbers-unsubscribe@yahoogroups.com
              > The Prime Pages : http://www.primepages.org/
              >
              >
              >
              >
              > MARKETPLACE
              >
              >
              >




              [Non-text portions of this message have been removed]
            • Chris Caldwell
              ... there ... - a I think folks are using different definitions of pattern here. Clearly a simple repetition is not possible (such as the period of a decimal
              Message 6 of 16 , Jul 27, 2010
              • 0 Attachment
                > Why are people still looking for patterns in prime numbers? If
                there
                > were patterns, prime numbers would come to an end and then start again
                - a

                I think folks are using different definitions of pattern here. Clearly
                a
                simple repetition is not possible (such as the period of a decimal
                fraction),
                but there are many obvious patterns to the primes such as all primes
                larger
                than 3 are of the form 6n+1 or 6n-1; and in a sense Dirichlet's theorem
                implies a distribution (a vague pattern) to the numbers of the form
                an+b.

                I agree with you than no naive repetition will give an infinite string
                of primes, but there are very simple formulas that do such as Mill's
                floor(A^3^n)? Is not the range of a function a pattern? (And I think
                one
                argue the sequence of primes is itself a pattern.)

                CC

                From Wikipedia:

                A pattern, from the French patron, is a type of theme of recurring
                events or objects, sometimes referred to as elements of a set. These
                elements repeat in a predictable manner. It can be a template or model
                which can be used to generate things or parts of a thing, especially if
                the things that are created have enough in common for the underlying
                pattern to be inferred, in which case the things are said to exhibit the
                unique pattern. Pattern matching is the act of checking for the presence
                of the constituents of a pattern, whereas the detecting for underlying
                patterns is referred to as pattern recognition. The question of how a
                pattern emerges is accomplished through the work of the scientific field
                of pattern formation.

                The most basic patterns are based on repetition and periodicity. A
                single template, or cell, is combined with duplicates without change or
                modification. For example, simple harmonic oscillators produce repeated
                patterns of movement.
                Pattern recognition is more complex when templates are used to generate
                variants. For example, in English, sentences often follow the "N-VP"
                (noun - verb phrase) pattern, but some knowledge of the English language
                is required to detect the pattern. Computer science, ethology, and
                psychology are fields which study patterns.

                "A pattern has an integrity independent of the medium by virtue of which
                you have received the information that it exists. Each of the chemical
                elements is a pattern integrity. Each individual is a pattern integrity.
                The pattern integrity of the human individual is evolutionary and not
                static."

                R. Buckminster Fuller (1895-1983), U.S.American philosopher and
                inventor, in Synergetics: Explorations in the Geometry of Thinking
                (1975), Pattern Integrity 505.201
              • Martin Aaronson
                Chris ­ Thank you for your reply to my question on prime patterns. You assert that it is obvious that 6n+1 or 6n-1 is a pattern. I agree that it is ŠŠbut is
                Message 7 of 16 , Jul 28, 2010
                • 0 Attachment
                  Chris ­ Thank you for your reply to my question on prime patterns. You
                  assert that it is obvious that 6n+1 or 6n-1 is a pattern. I agree that it is
                  ŠŠbut is it really a remarkable pattern?

                  Given sequence of all odd numbers only, mark off the multiples of 3 (x)

                  x 5 7 x 11 13 x 17 19 x 23 25 x 29 31 . . . .
                  .>>inf.
                  In pairs 5 7, 11 13, and 17 19, 6n is 6, 12, and18 respectively, where all
                  adjacent integers +1 -1 are prime.
                  In pair 23 25, where 6n is 24, only 23 is prime
                  In pair 29 31, where 6n is 30, both 29 and 31 are prime
                  and so it goes to infinity -- all prime numbers do appear at one or another
                  of sets 6n+1, 6n-1. Clearly, this is not to say that all sets have an
                  adjacent prime.

                  But, while this construction is remarkable from a base of 6n, from a base of
                  3n it is not, for reason that sets (3n+2, 3n+4) and (6n+1, 6n-1) are one and
                  the same. Thus, in the infinite base of sets (3n+2+4), all primes ( and
                  twin primes for that matter,) do appear at one set or another, but this is
                  quite unremarkable since it is obvious from the very beginning.
                  MA

                  From: Chris Caldwell <caldwell@...>
                  Date: Tue, 27 Jul 2010 17:24:32 -0500
                  To: <primenumbers@yahoogroups.com>
                  Subject: RE: [PrimeNumbers] Re: Easy formula for next prime... cant make it
                  any easier.

                  MA Why are people still looking for patterns in prime numbers? If
                  there were patterns, prime numbers would come to an end and then start again

                  CC I think folks are using different definitions of pattern here. Clearly
                  a simple repetition is not possible (such as the period of a decimal
                  fraction), but there are many obvious patterns to the primes such as
                  all primes larger than 3 are of the form 6n+1 or 6n-1; and in a sense
                  Dirichlet's theorem implies a distribution (a vague pattern) to the
                  numbers of the form an+b.
                  I agree with you than no naive repetition will give an infinite string
                  of primes, but there are very simple formulas that do such as Mill's
                  floor(A^3^n)? Is not the range of a function a pattern? (And I think
                  one can argue the sequence of primes is itself a pattern.)
                  CC




                  [Non-text portions of this message have been removed]
                • Martin Aaronson
                  Gentlemen ­ Thanks much for your interesting replies to my question ³Why are people still looking for patterns of prime numbers?², to which the response
                  Message 8 of 16 , Jul 30, 2010
                  • 0 Attachment
                    Gentlemen ­ Thanks much for your interesting replies to my question ³Why are
                    people still looking for patterns of prime numbers?², to which the response
                    from Chris Caldwell that ³there are many obvious patterns to the primes such
                    as all primes larger than 3 are of the form 6n+1 or 6n-1,² set up a flurry
                    of activity.
                    But your responses indicate to me that I did not make my intent clear
                    in my reply to Chris so please bear with me with me while I clarify my
                    remarks.

                    In sequence 3 5 7 9 11 13 15 17 19.......>>inf, all
                    primes 5 7, 11 13, 17 19 certainly do fall on coordinates (6n+1-1). But
                    note that these coordinates may also be defined as (3n+2+4), which actually
                    is one and the same as (6n+1-1). So clearly, in the context of sieving for
                    primes, the first step of which is marking off the multiples of 3, as in
                    sequence above, it must have been immediately obvious even to the ancients
                    that all primes >3 exist at 3n+2 or 3n+4, emphasis on immediately.
                    So why is this fact not mentioned in the texts? Why is only 6n+1-1
                    treated as if it were a profound discovery of the distribution of the
                    primes, when actually it is an obvious unremarkable fact when defined in the
                    context of its natural reference (3n+2+4).
                    Ergo, if (3n+2+4) or its complement (3n-2-4) have not appeared in the
                    literature in this context till now, I hereby lay claim to the copyright of
                    this significant bit of ³intellectual property.²
                    MA





                    [Non-text portions of this message have been removed]
                  • Martin Aaronson
                    Lelio – Regardless how you cut it, ALL PRMES are referenced to 3n+2+4 or 6n+-1, which are actually the same two integers. . So you will find patterns at all
                    Message 9 of 16 , Jul 31, 2010
                    • 0 Attachment
                      Lelio � Regardless how you cut it, ALL PRMES are referenced to 3n+2+4 or
                      6n+-1, which are actually the same two integers. . So you will find patterns
                      at all multiples of 3n, not only at the 4 places you mention, all the way to
                      infinity. Marty

                      From: L�lio Ribeiro de Paula <lelio73@...>
                      Date: Sat, 31 Jul 2010 08:16:19 -0300
                      To: Martin Aaronson <martyaa@...>
                      Subject: Re: [PrimeNumbers] Re: Easy formula for next prime... cant make it
                      any easier.

                      Next step is modulus 30

                      Notice that all primes follow one of four patterns: (30+-1)� (30+-7)�
                      (30+-11) and (30+-13) but I'm affraid Erathostenes
                      (http://en.wikipedia.org/wiki/Eratosthenes) knew about it.

                      L�lio



                      2010/7/31 Martin Aaronson <martyaa@...>
                      > �
                      > Gentlemen � Thanks much for your interesting replies to my question �Why are
                      > people still looking for patterns of prime numbers?�, to which the response
                      > from Chris Caldwell that �there are many obvious patterns to the primes such
                      > as all primes larger than 3 are of the form 6n+1 or 6n-1,� set up a flurry
                      > of activity.
                      > But your responses indicate to me that I did not make my intent clear
                      > in my reply to Chris so please bear with me with me while I clarify my
                      > remarks.
                      >
                      > In sequence 3 5 7 9 11 13 15 17 19.......>>inf, all
                      > primes 5 7, 11 13, 17 19 certainly do fall on coordinates (6n+1-1). But
                      > note that these coordinates may also be defined as (3n+2+4), which actually
                      > is one and the same as (6n+1-1). So clearly, in the context of sieving for
                      > primes, the first step of which is marking off the multiples of 3, as in
                      > sequence above, it must have been immediately obvious even to the ancients
                      > that all primes >3 exist at 3n+2 or 3n+4, emphasis on immediately.
                      > So why is this fact not mentioned in the texts? Why is only 6n+1-1
                      > treated as if it were a profound discovery of the distribution of the
                      > primes, when actually it is an obvious unremarkable fact when defined in the
                      > context of its natural reference (3n+2+4).
                      > Ergo, if (3n+2+4) or its complement (3n-2-4) have not appeared in the
                      > literature in this context till now, I hereby lay claim to the copyright of
                      > this significant bit of �intellectual property.�
                      > MA
                      >
                      > [Non-text portions of this message have been removed]
                      >
                      >





                      [Non-text portions of this message have been removed]
                    • Peter Kosinar
                      Marty, ... Could you, please, provide five examples of primes which are of the form 3n+2+4 (as you call it) and which are not of either of Lelio s forms 30n
                      Message 10 of 16 , Jul 31, 2010
                      • 0 Attachment
                        Marty,

                        > Lelio ? Regardless how you cut it, ALL PRMES are referenced to
                        > 3n+2+4 or 6n+-1, which are actually the same two integers. So you
                        > will find patterns at all multiples of 3n, not only at the 4 places
                        > you mention, all the way to infinity. Marty

                        Could you, please, provide five examples of primes which are of
                        the form 3n+2+4 (as you call it) and which are not of either of
                        Lelio's forms 30n +/- 1, 30n +/- 7, 30n +/- 11 and 30n +/- 13?

                        Peter

                        Lelio said:
                        > Next step is modulus 30
                        >
                        > Notice that all primes follow one of four patterns: (30+-1)? (30+-7)?
                        > (30+-11) and (30+-13) but I'm affraid Erathostenes
                        > (http://en.wikipedia.org/wiki/Eratosthenes) knew about it.
                      • Martin Aaronson
                        Peter ­ In 3n+2+4, the variable is n and +2+4 are the constants. In 6n+-1, again n is the variable, and +- 1 are the constants. Lelio may not realize it, but
                        Message 11 of 16 , Jul 31, 2010
                        • 0 Attachment
                          Peter ­ In 3n+2+4, the variable is n and +2+4 are the constants. In 6n+-1,
                          again n is the variable, and +- 1 are the constants. Lelio may not realize
                          it, but his 30n is actually 6n, where n is 5, so declaring it as 30n is a
                          misnnomer‹shd be 30± 1, ±7, ±11, ±13 etc. True, all of these examples hit on
                          the prime numbers, but it does fail at 30+19 where 49 is not prime. No big
                          surprise ‹ most odd numbers in this low range are prime numbers.
                          Secondly you misunderstand something -- all primes are 6n±1, not the
                          other way around that all 6n±1 are prime. Folks out there including yourself
                          and Lelio don¹t seem to understand that 6n±1 represents ALL integers that
                          are not multiples of 3, so of course every single prime to infinity is
                          either 6n+1, or 6n-1, or as Lelio found out, since 6n is the variable it
                          could represent 12, 18, 24, and his favorite 30......etc.
                          Now examine closely this sequence ( x 5 7 x 11 13 x 17 19.....) where x
                          is a multiple of 3 --- is not 6n±1 the coordnates for 5 7?, and is not
                          3n+2+4 the coordnates for the same 5 7? Summary: 3n+2+4 and 6n+1-1 are
                          one and the same. 3n is the base set, and all others are simply multiples
                          at 6,9,12,15......
                          Peter ­ Please forward to Lelio. Good luck in your research. Marty




                          From: Peter Kosinar <goober@...>
                          Date: Sun, 1 Aug 2010 01:23:59 +0200 (CEST)
                          To: <primenumbers@yahoogroups.com>
                          Subject: Re: [PrimeNumbers] Re: Easy formula for next prime... cant make it
                          any easier.

                          > Lelio ? Regardless how you cut it, ALL PRMES are referenced to
                          > 3n+2+4 or 6n+-1, which are actually the same two integers. So you
                          > will find patterns at all multiples of 3n, not only at the 4 places
                          > you mention, all the way to infinity. Marty

                          Could you, please, provide five examples of primes which are of
                          the form 3n+2+4 (as you call it) and which are not of either of
                          Lelio's forms 30n +/- 1, 30n +/- 7, 30n +/- 11 and 30n +/- 13?

                          Peter

                          Lelio said:
                          > Next step is modulus 30
                          >
                          > Notice that all primes follow one of four patterns: (30+-1)? (30+-7)?
                          > (30+-11) and (30+-13) but I'm affraid Erathostenes
                          > (http://en.wikipedia.org/wiki/Eratosthenes) knew about it.







                          [Non-text portions of this message have been removed]
                        • Peter Kosinar
                          Marty, ... So far, we re in agreement. ... Actually, it might be you not realizing that Lelio most likely made a typo and wrote 30 +/- 1 instead of 30n +/-
                          Message 12 of 16 , Aug 1, 2010
                          • 0 Attachment
                            Marty,

                            > In 3n+2+4, the variable is n and +2+4 are the constants. In 6n+-1, again
                            > n is the variable, and +- 1 are the constants.

                            So far, we're in agreement.

                            > Lelio may not realize it, but his 30n is actually 6n, where n is 5, so
                            > declaring it as 30n is a misnnomer - shd be 30+/-1, +/-7, +/-11, +/-13
                            > etc.

                            Actually, it might be you not realizing that Lelio most likely made a typo
                            and wrote "30 +/- 1" instead of "30n +/- 1" (and similarly for 7, 11 and
                            13). That's why my question included the expressions explicitly, rather
                            than referring to those from his post. So, no, it's not a misnomer.

                            > True, all of these examples hit on the prime numbers, but it does fail
                            > at 30+19 where 49 is not prime.

                            Formally, in order to match Lelio's form, it should be written as 49 =
                            2*30 - 11, rather than 1*30 + 19; but that's just an irrelevant formality.
                            As far as "failing" goes, read further.

                            > Secondly you misunderstand something -- all primes are 6n+/-1, not the
                            > other way around that all 6n+/-1 are prime.

                            Rest assured that I don't think so and I doubt that anyone in this group
                            thinks so.

                            > Folks out there including yourself and Lelio don't seem to understand
                            > that 6n+/-1 represents ALL integers that are not multiples of 3, so of
                            > course every single prime to infinity is either 6n+1, or 6n-1,

                            Wrong. 6n+/-1 represents all -odd- integers not divisible by 3 and,
                            consequently, it represents all primes with the exception of 2 and 3. This
                            is where it differs from your form 3n+2+4, which guarantees the "not
                            divisible by 3" condition, but not the "is odd" one.

                            As such, the form 3n+2+4 tells us very little about the primes -- just
                            that they're not divisible by 3. Yes, I believe that the ancient Greeks
                            knew this, so no patentable, copyrightable or otherwiseable claim here,
                            I'm afraid, unless you're going to reinvent the wheel [*].

                            So, if you're trying to sieve for primes, your form allows you to cross
                            out just one third of the numbers. This is actually worse than the even
                            simpler form 2n+1 which tells us that primes (apart from 2, of course) are
                            not even, allowing us to cross out one half of all the numbers. Shouldn't
                            this latter form be seen as being even more "profound" than yours? Taken
                            even further, the form "n" would be even more profound... since it cover
                            -all- primes, without exceptions :-)

                            The form 6n +/- 1 is interesting precisely because it's less trivial (or
                            obvious, whichever you prefer) than the two mentioned in previous
                            paragraph. It is also stronger than each of them -- since it combines the
                            information from both. When sieving, it allows one to cross out two thirds
                            of the numbers outright... which is better than the "one half" provided by
                            the 2n+1 form and twice "better" than yours.

                            Lelio's post just hinted that even the 6n +/- 1 form can be improved
                            further. His example, 30n +/- 1, 7, 11, 13, is based on three primes, 2, 3
                            and 5, guaranteeing non-divisibility by all of them. As a result, it
                            allows us to cross out more than 73% of all numbers outright.

                            The disadvantage of this form is that it is more complex, requiring one to
                            remember four different constants (1, 7, 11, 13), rather than just one
                            (1). Going further would make the situation even worse, forcing one to
                            know more and more constants and the relative gain in the "quality" of the
                            sieve would be lower and lower.

                            All in all, the forms like 2n+1 and your 3n+2+4 (or 3n +/-1, which is the
                            same) are easy to remember, but provide very little information, while
                            Lelio's 30n +/- ... provide more information at the cost of more
                            complexity. The 6n +/- 1 just seems like a nice compromise in between,
                            making it a nice example of a not-completely-obvious "pattern" in primes.
                            Other than that, there is very little "special" about it.

                            My previous post was actually prompted by your statement "So you will find
                            patterns at all multiples of 3n, not only at the 4 places you mention, all
                            the way to infinity." which suggested that you considered Lelio's pattern
                            to be invalid due to not covering all the primes; unlike your pattern,
                            which covers all of them (with the exception of prime 3). In order to help
                            you see that this is not so, I asked you to provide five primes which
                            would be covered by your pattern, but not by Lelio's. For now, I'll assume
                            that this misunderstanding was only caused by Lelio's typo -- omission of
                            "n" in "30n +/- ..." and that you weren't actually suggesting that the
                            expressions 30n +/- 1, +/- 7, +/- 11, +/- 13 cover all the primes apart
                            from 2, 3 and 5.

                            Peter

                            [*] Pun not intended, but there actually -is- a wheel-relevant article in
                            Wikipedia: http://en.wikipedia.org/wiki/Wheel_factorization

                            > > Lelio ? Regardless how you cut it, ALL PRMES are referenced to
                            > > 3n+2+4 or 6n+-1, which are actually the same two integers. So you
                            > > will find patterns at all multiples of 3n, not only at the 4 places
                            > > you mention, all the way to infinity. ��Marty
                            >
                            > Could you, please, provide five examples of primes which are of
                            > the form 3n+2+4 (as you call it) and which are not of either of
                            > Lelio's forms 30n +/- 1, 30n +/- 7, 30n +/- 11 and 30n +/- 13?
                            >
                            > Peter
                            >
                            > Lelio said:
                            > > Next step is modulus 30
                            > >
                            > > Notice that all primes follow one of four patterns: (30+-1)? (30+-7)?
                            > > (30+-11) and (30+-13) but I'm affraid Erathostenes
                            > > (http://en.wikipedia.org/wiki/Eratosthenes) knew about it.

                            [Non-text portions of this message have been removed]
                          • Matteo Mattsteel Vitturi
                            Peter, ... I don t thing i understand very well what you re saying about 6n+/-1 that should represent all primes. When n=20 then 6n-1=119 and 6n+1=121 and both
                            Message 13 of 16 , Aug 3, 2010
                            • 0 Attachment
                              Peter,

                              > > Folks out there including yourself and Lelio don't seem to understand

                              > > that 6n+/-1 represents ALL integers that are not multiples of 3, so of

                              > > course every single prime to infinity is either 6n+1, or 6n-1,

                              >

                              > Wrong. 6n+/-1 represents all -odd- integers not divisible by 3 and,

                              > consequently, it represents all primes with the exception of 2 and 3. This

                              > is where it differs from your form 3n+2+4, which guarantees the "not

                              > divisible by 3" condition, but not the "is odd" one.

                              >



                              I don't thing i understand very well what you're saying about 6n+/-1 that should represent all primes.
                              When n=20 then 6n-1=119 and 6n+1=121 and both aren't primes since 121 is 11x11 and 119 is 7x17.

                              Matteo.




                              [Non-text portions of this message have been removed]
                            • Peter Kosinar
                              Matteo, ... An expression (e.g. 2n+1) represents a set S if every number from set S can be written in the form prescribed by the expression. It s not necessary
                              Message 14 of 16 , Aug 3, 2010
                              • 0 Attachment
                                Matteo,

                                > > Wrong. 6n+/-1 represents all -odd- integers not divisible by 3 and,
                                > > consequently, it represents all primes with the exception of 2 and 3. This
                                > > is where it differs from your form 3n+2+4, which guarantees the "not
                                > > divisible by 3" condition, but not the "is odd" one.
                                >
                                > I don't thing i understand very well what you're saying about 6n+/-1 that
                                > should represent all primes.

                                An expression (e.g. 2n+1) represents a set S if every number from set S
                                can be written in the form prescribed by the expression. It's not
                                necessary for all the numbers of that form to belong to set S.

                                For example, the form 2n+1 represents all odd integers. Thus, it can also
                                be used to represent each and every odd prime, odd square or odd perfect
                                number -- since all of these are just subsets of the set of odd numbers.

                                Peter
                              • Martin Aaronson
                                Peter Thanks for your comment. I admit I am wrong technically in that since 2 is the only even prime, I usually skirt around that issue by always prefacing
                                Message 15 of 16 , Aug 3, 2010
                                • 0 Attachment
                                  Peter Thanks for your comment. I admit I am wrong technically in that since
                                  2 is the only even prime, I usually skirt around that issue by always
                                  prefacing my remarks by stating ³in the set of odd numbers only,² which I
                                  neglected to do in this case. I do that because prime 2 always obfuscates
                                  the issue, as it is doing in this very instance. Thanks for your interest.
                                  Marty



                                  From: Matteo Mattsteel Vitturi <mattsteel@...>
                                  Date: Tue, 3 Aug 2010 23:25:54 +0200
                                  To: <primenumbers@yahoogroups.com>
                                  Subject: RE: [PrimeNumbers] Re: Easy formula for next prime... cant make it
                                  any easier.







                                  Peter,

                                  > > Folks out there including yourself and Lelio don't seem to understand

                                  > > that 6n+/-1 represents ALL integers that are not multiples of 3, so of

                                  > > course every single prime to infinity is either 6n+1, or 6n-1,

                                  >

                                  > Wrong. 6n+/-1 represents all -odd- integers not divisible by 3 and,

                                  > consequently, it represents all primes with the exception of 2 and 3. This

                                  > is where it differs from your form 3n+2+4, which guarantees the "not

                                  > divisible by 3" condition, but not the "is odd" one.

                                  >

                                  I don't thing i understand very well what you're saying about 6n+/-1 that
                                  should represent all primes.
                                  When n=20 then 6n-1=119 and 6n+1=121 and both aren't primes since 121 is
                                  11x11 and 119 is 7x17.

                                  Matteo.



                                  [Non-text portions of this message have been removed]








                                  [Non-text portions of this message have been removed]
                                • Martin Aaronson
                                  Peter Thanks for your comment. I admit I am technically wrong in that since 2 is the only even prime, I usually skirt around that special case by always
                                  Message 16 of 16 , Aug 3, 2010
                                  • 0 Attachment
                                    Peter Thanks for your comment. I admit I am technically wrong in that
                                    since 2 is the only even prime, I usually skirt around that special case by
                                    always prefacing my remarks with ³in the set of odd numbers only,² which
                                    I neglected to do, much to my regret since I am getting flak from around
                                    the world. I do that because prime 2 always obfuscates the issue, as it is
                                    doing in this very instance.
                                    So, to correct, the locus for ALL primes except 2 is 6n+1 or 6n-1,
                                    which of course is not to say that all 6n+-1 are prime. Another way to
                                    define 6n+-1 is 3n+2+4, where both are one and the same. The distinction I
                                    am making is that 3n+2+4 is descriptive (to me) of all non-multiples >3 to
                                    infinty, while 6n+-1, makes it appear that there is something profound and
                                    revealing about this infinite set when in fact it has been staring us in the
                                    face from the very outset as 3n+2+4. If you look at in this light, it will
                                    all come together. Thus, the search for a pattern in 6n+1-1 is all in vain.
                                    A list of prime numbers (go primes.utm.edu ) has provided this information
                                    forever. Thanks for your interest. Regards. Marty



                                    From: Peter Kosinar <goober@...>
                                    Date: Wed, 4 Aug 2010 00:08:38 +0200 (CEST)
                                    To: Matteo Mattsteel Vitturi <mattsteel@...>
                                    Cc: <primenumbers@yahoogroups.com>
                                    Subject: RE: [PrimeNumbers] Re: Easy formula for next prime... cant make it
                                    any easier.






                                    Matteo,

                                    > > Wrong. 6n+/-1 represents all -odd- integers not divisible by 3 and,
                                    > > consequently, it represents all primes with the exception of 2 and 3. This
                                    > > is where it differs from your form 3n+2+4, which guarantees the "not
                                    > > divisible by 3" condition, but not the "is odd" one.
                                    >
                                    > I don't thing i understand very well what you're saying about 6n+/-1 that
                                    > should represent all primes.

                                    An expression (e.g. 2n+1) represents a set S if every number from set S
                                    can be written in the form prescribed by the expression. It's not
                                    necessary for all the numbers of that form to belong to set S.

                                    For example, the form 2n+1 represents all odd integers. Thus, it can also
                                    be used to represent each and every odd prime, odd square or odd perfect
                                    number -- since all of these are just subsets of the set of odd numbers.

                                    Peter







                                    [Non-text portions of this message have been removed]
                                  Your message has been successfully submitted and would be delivered to recipients shortly.