> For the complete documentation index, see [llms.txt](https://erhany96.gitbook.io/collatz-prefixes/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://erhany96.gitbook.io/collatz-prefixes/theory/operation-table/shrinking-numbers.md).

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