# 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?