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

Re: GB sequences

Expand Messages
  • 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 1 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.