Shrinking Numbers

Do we always get smaller numbers in our sequence?

We can analyze the table to determine at which point a cell value is an integer less than it's row number. What that means is that, for such a cell, using the trajectory defined by the column ECF and starting from the number of that row, we will reach a smaller number. We can then re-iterate this logic until we go all the way down to one, if possible.

When we look at the shrinking numbers, there is a pattern with respect to the powers of two.

2k+0 vs 2k + 1$

It is trivial to see that number of the form $2k$ are even, and thus they will immediately shrink within a single iteration of Collatz Function.

• Numbers of the form $2k+0$ shrink with ECF $\{1\}$, bijectively mapped to 2.

We do not have an immediate proof for odd numbers though. So, let us split the odd numbers in two as $4k+1$ and $4k+3$.

4k+1 vs 4k+3

There is actually a neat proof that numbers of the form $4k+1$ shrink with ECF $\{0, 2\}$.

$$4k+1 = n' \frac{2^2}{3^1} - \frac{2^0}{3^1}$$

$$n' = (12k + 3 + 1)/4 = 3k+1$$

Indeed, $3k + 1 < 4k + 1$ for positive integers $k$.

• Numbers of the form $4k+1$ shrink with ECF $\{0, 2\}$, bijectively mapped to 5.

Again, we don’t know what is the case for $4k+3$. So we go one more level beyond, and look at numbers $8k+3$ and $8k + 7$.

8k+3 vs 8k+7

Candidates: 1 → 0, 2 → 0, 1, 3 (add 1 and prepend 0). Or, look at their bijective mappings: 2 → 5 → 11? Well, 11 would give ECF $\{0, 1, 3\}$ so that fits our previous guess!

$$8k+3 = n'\frac{2^4}{3^2} - \frac{2^1}{3^2} -\frac{2^0}{3^1}$$

$$9(8k+3) + 9(5) = n'16$$

$$9(8(k+1)) = n'16$$

$$n' = 4.5k + 4.5$$

Yeah, indeed this shrinks the same way!

• Numbers of the form $8k+3$ shrink with ECF $\{0, 1, 3\}$, bijectively mapped to 11.

Generalization of shrinking proofs

We will use proof by induction. Let us see the first few results:

n	Numbers	ECF	Bijective Map
1	$2k+0$	$\{1\}$	2
2	$4k+1$	$\{0, 2\}$	5
3	$8k + 3$	$\{0, 1, 3\}$	11
4	$16k+7$	$\{0, 1, 2, 4\}$	23
5	$32k+15$	$\{0, 1, 2, 3, 5\}$	47

A general form for the numbers w.r.t $n$ can be written as $2^nk + (2^{n-1} - 1)$. As for the ECFs, we can define them by the following recursion:

• $a_1 = 2$
• $a_n = 2a_{n-1} + 1$

This gives the sequence 2, 5, 11, 23, 47, 95, 191, …; and is a perfect opportunity to see if OEIS has it! Indeed it has: OEIS A083329.

$$a_n = 3\times2^{n-1} - 1$$

There is also OEIS A055010 but only the leading term $a_0$ is different, which we do not consider since we start with $a_1$.

The ECFs follow the pattern:

• $n=1 \implies \{1\}$
• $n > 1 \implies \{0, 1, \ldots, n-2, n\}$

Let us write the ICF for some number $2^nk + (2^{n-1}-1)$ for ECF $\{0, 1, \ldots, n-2, n\}$.

$$2^nk + (2^{n-1}-1) = n'\frac{2^n}{3^{n-1}} - \frac{2^{n-2}}{3^{n-1}} - \frac{2^{n-3}}{3^{n-2}} - \frac{2^{n-4}}{3^{n-3}} - \ldots - \frac{2^0}{3^1}$$

$$2^nk + (2^{n-1}-1) = n'\frac{2^n}{3^{n-1}} - \frac{1}{2}\sum_{i = 1}^{n-1}\frac{2^i}{3^i}$$

I had to use Wolfram|Alpha to see that:

$$\sum_{i = 1}^{n-1}\frac{2^i}{3^i} = 2 - \frac{2^n}{3^{n-1}}$$

So, what we have is:

$$2^nk + (2^{n-1}-1) = n'\frac{2^n}{3^{n-1}} - \frac{1}{2}\left(2 - \frac{2^n}{3^{n-1}}\right)$$

$$2^nk + (2^{n-1}-1) = n'\frac{2^n}{3^{n-1}} - 1 + \frac{2^{n-1}}{3^{n-1}}$$

$$2^nk + 2^{n-1} = n'\frac{2^n}{3^{n-1}} + \frac{2^{n-1}}{3^{n-1}}$$

$$2k + 1 = n'\frac{2}{3^{n-1}} + \frac{1}{3^{n-1}}$$

$$\frac{2k+1}{3^{n-1}} = 2n'+ 1$$

That is cool and all, but sadly $\alpha$ does not turn out to be an integer each time. When it does, it does show that the number is shrinking though!