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

Re: [PrimeNumbers] GB sequences

Expand Messages
  • Joshua Zucker
    I don t know much, but: Record-setters (in terms of # of steps to reach 7) appear to be the following pairs (prime, # of steps to reach 7) ... and I say
    Message 1 of 3 , Dec 12, 2006
    • 0 Attachment
      I don't know much, but:
      Record-setters (in terms of # of steps to reach 7) appear to be the
      following pairs (prime, # of steps to reach 7) ... and I say "appear
      to be" because some of the larger numbers encountered are not proved
      prime, but only probable primes by miller-rabin:
      (3 2)
      (5 3)
      (13 5)
      (19 8)
      (31 21)
      (59 22)
      (61 24)
      (103 29)
      (181 60)
      (359 61)
      (691 72)
      (1367 73)
      (1381 97)
      (2749 100)
      (3691 184)
      (4021 216)
      (5737 239)
      (6481 451)
      (9241 469)
      (12211 1194)
      (16963 3166)
      (33871 3379)
      (67699 3388)
      (135367 3391)
      (255457 4434)
      (290473 13676) (wow!)
      (580927 13683) (largest number reached:
      217382548130563796883806696581834453219357254158048222693}

      Interestingly, sometimes the primes just after a record also takes an
      exceptionally long time, as in 33889 which takes 3377 steps and 33893
      and 33911 each taking 3167 steps. Wow. There seems to be some kind
      of bigger pattern going on, where the # of steps decreases steadlily
      for a while and then suddenly jumps up at 33871? Hm. Look at this
      list:
      (33871 3379)
      (33889 3377)
      (33893 3167)
      (33911 3167)
      (33923 3167)
      (33931 3165)
      (33937 3163)
      (33941 41)
      (33961 3161)
      (33967 3151)
      (33997 3145)

      and from 33000 through 33870 there's nothing more than a couple
      hundred, and then again for several thousand after that.

      This kind of pattern shows up a lot, as around 48733 where all the
      sequences have length around 1000. Makes me think they're all heading
      on the same trajectory after a few initial terms that differ a bit.
      Indeed, the thing runs a LOT faster if I store previously-visited
      numbers with the length of the trajectory following that number, so
      several things must be hitting the same big long lists.



      So far, all of them appear to end in the loop by reaching 7. I
      checked all primes up to 1,000,000. anyway.

      It should be like a random walk, doubling and halving, so it should
      return to small numbers with probability 1 ... treating primes as
      random, of course, which is usually valid but not a proof. I would
      guess that a good approximation to the length of these things could be
      made by treating them all as random walks.

      But it looks from some of your pictures that maybe you already know
      more than what I found here. Wow, you found one that takes over 60000
      iterations!

      I'd also like to find out (as you hint, but don't say, in your
      pictures) whether 2501833 ever returns to 7 ... right now I lack the
      patience to wait for my (admittedly slow) program to tell me (it took
      my program about 40 minutes to check all the primes up to a million,
      and even then it was only checking for pseudoprimes in its next-prime
      hunt -- how fast is your program?)

      --Joshua Zucker


      On 12/12/06, Brougnard <jacques.tramu@...> wrote:
      > Does anyone know something about Georges Brougnard prime gb-
      > sequences ?
      >
      > Definition :
      >
      > -- gb[0] := any prime > 2
      > -- if gb[n] = 2 (mod 3)
      > then gb[n+1] : = next prime > (gb[n]-1)/2
      > else gb[n+1] := next prime > gb[n]*2
      >
      > Example :
      > {23 ,13 ,29 ,17 ,11 ,7 ,17, 11 ,7 ...}
      > {281 ,149,79,163,331,673,1361,683,347,179,97,197,101,53,29,17,11,7,..
      > .}
      >
      > Pictures :
      >
      > http://www.echolaliste.com/gbnums/gb1.jpg
      > http://www.echolaliste.com/gbnums/gb2.jpg
      > http://www.echolaliste.com/gbnums/gb3.jpg
      > http://www.echolaliste.com/gbnums/gb4.jpg
      >
      >
      > -- does every sequence ends in the loop 7,17,11,7,.. ??
      > -- are there other loops than 7,17,11,7,17,... ?
      > -- are there divergent sequences ? (not ending in a loop)
      > -- could you give a prime Pmax such as for every gb[0] <= Pmax the
      > sequences ends in a loop .?
      >
      > and other questions you could ask
      > Regards,
      > et merci.
      >
      > JT
      > --------------------------------------------------------------
      > http://www.echolaliste.com
      > --------------------------------------------------------------
    • Joshua Zucker
      Here s Adam s post by his request. I surely don t want to get involved in the reply-to-group vs reply-to-sender debate! There are good arguments on both
      Message 2 of 3 , Dec 13, 2006
      • 0 Attachment
        Here's Adam's post by his request.

        I surely don't want to get involved in the "reply-to-group" vs
        "reply-to-sender" debate! There are good arguments on both sides and
        I'm happy to provide links to them if people are interested in having
        that debate here. I'd prefer to just live with whichever side the
        moderator chooses for whatever reason.

        To reply to Adam's post:

        In a 1D random walk, starting at any point, the probability of
        visiting any other point is 1 -- not that it's certain, just that it's
        likely. So I expect (even if it's probability of 1/2 of going
        doubling or halving) that you'd eventually hit 7.

        --Joshua Zucker

        On 12/13/06, Adam <a_math_guy@...> wrote:
        > I wonder what your reasoning is behind "return to small numbers with
        > probability=1." At the first level of analysis (using 1/2*2=1) it
        > should return to the size of its initial seed. So if you start with a
        > large seed (like 100s of digits) then it might return to around that
        > size before "walking away" again, with a lot of room between 10^100
        > and 7 for a few extra halvings to fall in.
        >
        > When I analyzed it further (using a small modulus - 120), I found a
        > reason to suggest that it would eventually head towards small numbers
        > (and the 7-17-11 cycle).
        >
        > Suppose you have a seed that is 1 mod 120, so you double to 2 mod 120
        > (or 2 mod 240 if you want), the next prime won't be 3,4,5,6 mod 120,
        > so the first "good" candidate for the next prime is 7 mod 120.
        > Suppose you started with a seed that was 23 mod 120, then (x-1)/2 is
        > 11 mod 60 and the next good candidate for the next prime is 13 mod
        > 60.
        >
        > I analyzed the 31 residues mod 120 which are relatively prime to 120.
        > 14 of these 31 are 2 mod 3. However, if you look at where they lead
        > to for the next residue, only 10 of the 31 are not 2 mod 3. So the
        > next stage should have halving about 21 out of 31 times, while it
        > should have doubling 10 out of 31 times. So a slight emphasis towards
        > halving and thus a probabilistic expectation that it will head towards
        > O(1).
        >
        > Perhaps I should have used a large modulus and maybe also several runs
        > of the function, like modulus=2^10*3*5*7*11*13*17 and then see what
        > happens after 9 turns at the function.
        >
        > Adam
        >
        > snip>
        >
        > > It should be like a random walk, doubling and halving, so it should
        > > return to small numbers with probability 1 ... treating primes as
        > > random, of course, which is usually valid but not a proof. I would
        > > guess that a good approximation to the length of these things could
        > be
        > > made by treating them all as random walks.
        >
        > <snip
        >
        >
      Your message has been successfully submitted and would be delivered to recipients shortly.