2022.03.30 MATH 3600 3n+1 Parity

94 days ago by calkin

If we define $f(n)$ and $g(n)$ as before, and consider the parity of the iterates, do we see any patterns?
def f(n): if is_even(n): return(n/2) else: return(3*n+1) def g(n): if is_even(n): return(n/2) else: return((3*n+1)/2) 
       
n=10344350000884301 odd_count=0 even_count=0 while n>1: n=f(n) if is_even(n): even_count+=1 else: odd_count+=1 print(even_count,odd_count) 
        
(326, 172)
(326, 172)
odd_count=0 even_count=0 for i in srange(10000): if is_even(f(i)): even_count+=1 else: odd_count+=1 print(even_count,odd_count) 
        
(7500, 2500)
(7500, 2500)

If the input to $f(n)$ is chosen uniformly in [1,4N] then exactly 75\% of the time, f(n) will be even.

This is not a surprise in retrospect!

What about the same questions for $g(n)$?
n=10344350647373563783846894695895898878000884301 odd_count=0 even_count=0 while n>1: n=g(n) if is_even(n): even_count+=1 else: odd_count+=1 print(even_count,odd_count) 
        
(363, 359)
(363, 359)

This appears to suggest that our intuition for $g(n)$ being even about half the time in a trajectory to 4,2,1 is probably correct.

What about if $n$ is chosen uniformly in $[1,4N]$?
odd_count=0 even_count=0 for i in srange(10000): if is_even(g(i)): even_count+=1 else: odd_count+=1 print(even_count,odd_count) 
        
(5000, 5000)
(5000, 5000)

It appears that in this case the odds are exactly 50% that the output is even.

Let's see how many evens and odds we get if we look at all trajectories starting in [1,N]
N=10000 odd_count=0 even_count=0 for i in srange(1,N+1): n=i while n>1: n=f(n) if is_even(n): even_count+=1 else: odd_count+=1 print(even_count,odd_count) 
        
(562644, 287022)
(562644, 287022)

It appears that for $f(n)$ about 2/3 of the outputs are even.  How do we reconcile this with the fact that on an interval, 75\% of the outputs are even?
N=100000 odd_count=0 even_count=0 for i in srange(1,N+1): n=i while n>1: n=g(n) if is_even(n): even_count+=1 else: odd_count+=1 print(even_count,odd_count) 
        
(3574056, 3614892)
(3574056, 3614892)

Last time we predicted that the average number of steps in the trajectory of $g$ starting at $n$ should be about $\log(n)/\log(4/3)$

So we might expect that the sum of the lengths of $t(n)$ for $n\leq N$ should be like 

\[ \frac{N\log(n)-\log(N) + 1/2 \log(N) +1/2\log(2\pi)}{\log(4/3)}   \]
def s(N): return(((N*log(N)-log(N) + 1/2* log(N) +1/2*log(2*pi))/(log(4/3.))).n()) 
       
s(100000) 
        
4.00194457430361e6
4.00194457430361e6

Doesn't look like a great match: can we see why?