[pdx.st] Meeting tonight!

[Andres Valloud]

On 7/29/14 16:58 , markus wrote:
> The Math Club kids spent a few weeks on 3x+1 and closely related
> problems last fall.  It's a wonderful area to explore, with lots of
> interesting nooks and crannies.  Some that I recall they had fun with:
>
>        * What does it look like mod 6, mod 18, and in general in mod
>          2^x*3^y

Some people did this I remember, and they found a state machine that 
describes the behavior.  Unfortunately, they found no end states (which 
might lead to cycles and/or divergent trajectories).

>        * What bounds can you set on the smallest y that will lead to a
>          given x?  y<=2*x is immediate, but can you do better?

Generally, the asymptotic behavior seems to be x = O(y^2).  It's unclear 
whether it's O(y^2) or O(y^2 ln y).

>        * If we call f(x) = even(x) ? x/2 : 3x+1, and g(x) = f(f(x)), what
>          do we see?  Likewise for h(x) = f(f(f(x))) and so forth.

It's more rewarding to define

T(odd x) = (3x+1) / 2
T(even x) = x / 2

Then,

T^n(2^n - 1) = 3^n - 1

Moreover, suppose you split a number x this way,

x = q 2^n + r

according to the division algorithm (you divide by 2^n, q is the 
quotient, r is the remainder, where 0 <= r < |2^n|).  Then,

T^n(q 2^n + r) = q 3^j + T^n(r)

where j is the number of times T^n(r) chooses the odd branch.

And on... http://blogten.blogspot.com/2013/08/about-3x1.html

and on... 
http://blogten.blogspot.com/2013/09/about-3x1-hash-table-scavenging.html

and on... http://blogten.blogspot.com/2013/12/3x1-update.html

>        * Can we find anything like mandlebrot in the convergence times?

See Lagarias' book, there are some results kind-of, sort-of like that.

>        * If some x doesn't dominate 1, it must either grow without bound
>          or be part of some cycle which does not include 1.  Can we say
>          anything about these possibilities?

Oh yes, a lot.  As the minimum bound for a counter example increases, 
the minimum cycle length also increases.  The current minimum cycle 
length is O(10^9).

> And it looks like you've found a whole slew of similarly interesting
> questions to ask about it.

Yes :)... with some answers!  See the blog posts, there's a nice proof 
re: parity matrices.

> Hope you get to feeling better soon!

Thank you, it should take a couple days.

Andres.