## Re: GB sequences

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

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

> probability=1." At the first level of analysis (using 1/2*2=1) it
> 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.
>
>
> 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.