4
$\begingroup$

My kid asked me a question and I'm finding it hard to answer: if every number under repeated application of the Collatz transformation1 eventually reaches $1$, then it must be true for both even and for odd numbers. Why, then, for numbers of a given "height" (the number of divisions before reaching $1$, A00666 in the OEIS) are there so many more even numbers than odd numbers? If you halve an even number then $50$% of the time the result should be odd. And if there are more even numbers than odd ones at every given height, won't you run out of even numbers more quickly?

In fact the ratio of even:odd numbers of a given height is approximately $3:1$ (Pari/GP code below).2 My answer wasn't satisfactory: there are an infinite amount of both odd and even numbers, so you won't run out of either; and transforming an odd number can only lead to a subset of even numbers ($x: x= 3k+1$) so the other ones don't really count.

Is there a more intuitive way to explain it?

1 $C(x)= \begin{cases} \frac{x}{2}&\text{when x is even; and}\\ {3x+1}&\text{when x is odd.} \end{cases}$

2 heights(n)= if(n==0,return([1]), n==1, return([2]), n==2, return([4]), my(h=heights(n-1)); my(l=List()); for(x=1,#h, listput(l,h[x]*2); if(h[x]%3==2, listput(l,(h[x]*2-1)/3)));return(Vec(l))) \\ Returns a vector of numbers with a given Collatz height

$\endgroup$
  • $\begingroup$ Perhaps it has to do with the fact that when $C(x)$ gets smaller when $x$ is even, and $C(x)$ grows when $x$ is even (even when using the modified Collatz function). $\endgroup$ – JavaMan Aug 8 '18 at 2:02
1
$\begingroup$

When you write the trajectory or height of any given number $n$, the trajectory "skips" a lot of numbers, therefore creating the illusion that there are more even numbers than odd numbers.

When writing out the trajectory, more even numbers show up because it is required to divide the even result at least once after performing $3n+1$ and some even numbers require multiple divisions of 2 before becoming odd again. For every time the $3n+1$ step is performed, 50% of the time it only takes one division, 25% of the time it takes two divisions, 12.5% of the time it only takes 3 divisions, so on and so forth causing all trajectories except for 1 and 2 to have more even numbers.

The Collatz function creates gaps between the numbers after every step. For example, the trajectory 52,26,13,40,20,10,5,16,8,4,2,1,... skips a lot of numbers less than 52. The only way to reach those numbers is to start with those values for $n$ or find a value of $n$ that contains those values in their trajectory, which ends up skipping even more numbers and capitalizing on the illusion that there are more even numbers than odd numbers. When n = 27, only 111 numbers out of 9232 numbers are connected into one trajectory, the majority of the skipped numbers being odd.

Another way of looking at this is to create a Collatz tree given a sample size, and only connecting numbers according to the Collatz Function when those numbers exist. For example, if the sample size is 10, then the trajectory of 8-4-2-1 will be complete, but there will be a 6-3-10-5 "chunk", and the numbers 7 and 9 won't connect to anything at all. As the sample size increases, the smaller odd numbers will connect to more numbers faster while large odd number "chunks" will grow slowly. There will also be several odd numbers that won't have their multiples of 2 yet because those values exceed the sample size limit.

Another example: n=100 (I do $n$= 100-70) I put repeats in [].

100-50-25-76-38-19-58-29-88-44-22-11-34-17-52-26-13-40-20-10-5-16-8-4-2-1-...
99
98-49
97
96-48-24-12-6-[3...]
95
94-47
93
92-46-23-70-35
91
90-45
89
88-44-22-[11...]
87
86-43
85
84-42-21-64-32-[16...]
83
82-41
81
80-[40...]
79
78-39
77
[76...]
75
74-37
73
72-36-18-9-28-14-7-[22...]
71
[70...]

...
| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

Note that for an odd $n$ the number $3n+1$ is always an even number.

Therefore even if you start with a set of equal odds and evens, after you first iteration you have more even numbers than odd numbers.

For example $$\{3,5,6,8\} \to \{10,16,3,4\}\to \{5,8,10,2\}\to \{16,4,5,1\}$$

To remedy this pattern, you may redefine your function as $$ C(x)= \begin{cases} \frac{x}{2}&\text{when x is even; and}\\ {(3x+1)/2}&\text{when x is odd.} \end{cases}$$

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ True, yes, but that doesn't really explain why there's a difference in ratio. After all, the Collatz sequence does eventually end up at $4,2,1$ repeated. However, this is an interesting approach. $\endgroup$ – Don Thousand Aug 8 '18 at 1:52
0
$\begingroup$

The reason why one would expect more even numbers to appear at a given height rather than odd numbers is the following: the number of even numbers of height $n$ should be equivalent to the number of odd numbers of height$<n$. Why is that? Let the height of odd $g$ be $k<n$. Hence, $g\cdot 2^{n-k}$ will have height $n$.

And under most circumstances, we expect the number of odd numbers of height less than $n$ to be higher than the number of odd numbers of height exactly $n$, especially for large $n$.

I do believe your discovery of a $3:1$ ratio to be coincidence.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ The 3:1 ratio is in fact expected: if there are $k$ numbers at height $n$, and their value modulo $3$ is equally distributed, then there will be $k/3$ numbers equal to $2$ modulo $3$. Consequently, at height $n+1$ there will be $k$ even numbers (all the numbers of height $n$, doubled) and $k/3$ odd numbers (all the numbers at height $n$ equal to $2$ modulo $3$, doubled, then subtract one and divide by three). So assuming a normal distribution – which experimentally seems to be the case – the 3:1 ratio is preserved. $\endgroup$ – Joe Slater Aug 8 '18 at 4:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.