0
$\begingroup$

$$ T(n) = \begin{cases} \frac{n}{2} & n \equiv 0 \pmod{2}\\\\[2ex] \frac{3n + 1}{2} & n \equiv 1 \pmod{2} \end{cases} $$

Starting with an arbitrary positive integer $k$, you can build a map showing the possible values it can have after applying the function $T$ repeatedly. Connect the node of the $\frac{n}{2}$ step first, then the $\frac{3n + 1}{2}$ node T function tree map

Notice that as we are using the shortcut version of the Collatz function, each node is connected to two other nodes, making the number of nodes on each row grow as $2^n$, unlikely the original function, which grow in the same rate as the Fibonnaci numbers

If you look at the numerators of the first fraction on each node, you will see that it is converging to a sequence

On the first row you have $1$, on the second you have $1, 3$, on the third, $1, 3, 3, 9$, and so on. This also applies to the others sequences, except for the first fraction denominators.


$A_n =$ $n$th value on the limit sequence of the numerators of the 1st fraction $(1, 3, 3, 9, 3, 9, 9, 27, 3, 9, 9, 27, 9, 27, 27, 81, ...)$

It is the same as $3^{H_n}$, where $H_n$ is the Hamming weight of $n$ (conjectured)


$A'_r = $ The denominator of the 1st fractions of the nodes of the $r$th row $(1, 2, 4, 8, 16, 32, 64, ...)$

As you start with $1$ and divides by two on each step, it's easy to see that you get the powers of $2$ as denominators


$B_n =$ $n$th value on the limit sequence of the numerators of the 2nd fraction $(0, 1, 1, 5, 1, 7, 5, 19, 1, 11, 7, 29, 5, 23, 19, 65, ...)$

This one is pretty hard, because here you have the effects of the $+1$, and when you add $1$ to a fraction, you are adding the denominator to the numerator, so this sequence is somehow related to $B'_n$


$B'_n =$ $n$th value on the limit sequence of the denominators of the secon 2nd fraction $(1, 2, 4, 4, 8, 8, 8, 8, 16, 16, 16, 16, 16, 16, 16, 16, ...)$

Except for $1$, $2^x$ appears $2^{x - 1}$ times (A062383). This sequence also appear as being denominators on the Van der Corput sequence


Python script to compute these sequences:

from fractions import Fraction


class CollatzNode:
    def __init__(self, first_fraction=Fraction(1), second_fraction=Fraction(0)):
        # The one that is multiplying
        self.first_fraction = first_fraction
        # The one that is adding
        self.second_fraction = second_fraction

    def __str__(self):
        first = f"({self.first_fraction.numerator}/{self.first_fraction.denominator})"
        second = f"{self.second_fraction.numerator}/{self.second_fraction.denominator}"
        return f"{first}k + {second}"

    def __repr__(self):
        return str(self)

    def odd_step(self):
        new_first_fraction = (3 * self.first_fraction) / 2
        new_second_fraction = (3 * self.second_fraction + 1) / 2
        return CollatzNode(new_first_fraction, new_second_fraction)

    def even_step(self):
        new_first_fraction = self.first_fraction / 2
        new_second_fraction = self.second_fraction / 2
        return CollatzNode(new_first_fraction, new_second_fraction)


def next_row(row):
    new_row = []
    for node in row:
        new_row.append(node.even_step())
        new_row.append(node.odd_step())
    return new_row


def nth_collatz_row(n):
    row = [CollatzNode()]  # that's the 0th one
    for _ in range(n):
        row = next_row(row)
    return row

row = nth_collatz_row(5)
A = []
Ap = []
B = []
Bp = []
for node in row:
    A.append(node.first_fraction.numerator)
    Ap.append(node.first_fraction.denominator)
    B.append(node.second_fraction.numerator)
    Bp.append(node.second_fraction.denominator)

print(f"A: {A}")
print(f"A': {Ap}")
print(f"B: {B}")
print(f"B': {Bp}")
  1. How to prove that $A_n = 3^{H_n}$?
  2. Is there a closed form for $B_n$?

Note: the fractions are always already in the simplest form, in the first fraction, the denominator is a power of 2 and the denominator is a power of 3, and on the second fraction, the denominator is also some power of 2, and for the numerator, it starts at 0 then goes to 1, and then the only things that can happen is that you multiply by 3 or you add the denominator to it, which will keep the number odd as the denominator is even and odd + even is always odd.

$\endgroup$
1
  • $\begingroup$ $A_n = 3^{H_n}$ is linked to the way you arrange your tree. If you represent a division by 2 on the left by a binary 0, and a multiplication by 3 on the right by a binary 1, the last row end up being "0, 1, 2, 3, 4, 5...." in binary form. And since the number of bit at 1 is the number of multiplication by 3... $\endgroup$
    – Collag3n
    Oct 29, 2023 at 9:11

1 Answer 1

1
$\begingroup$

Consider the sequence of odd integers $x_i$ where $$x_{i+1} = \frac{3x_i + 1}{2^{n_i}}$$ Define $$N_i = \sum\limits_{j=1}^i n_j \textrm{ for } i \gt 0 \textrm{ and } N_0 = 0$$ $$S = \sum\limits_{i=0}^{L-1} 3^{L - 1 - i}2^{N_{i}}$$ Then $$x_{L+1} = {x_1 3^L + S \over 2^{N_L}}$$ If the graph consists of odd numbers only, $A_n=3^L$, $B_n = S$ and $A'_n=B'_n = 2^{N_L}$. The possible values of $S$ depend on $L$. Note that $0=N_0 \lt N_1 \lt N_2 ...$. $$L=1 : S = \sum\limits_{i=0}^{0} 3^{1 - 1 - i}2^{N_{i}} = 1$$ $$L=2 : S = \sum\limits_{i=0}^{1} 3^{2 - 1 - i}2^{N_{i}} = 3 + 2^{N_1} = 5,7,11,19,..$$ $$L=3 : S = 3^22^{N_0} + 3^12^{N_1} + 3^02^{N_2} = 9 + 3\cdot2^{N_1} + 2^{N_2}$$ $$L=3, N_1 = 1, N_2 > 1, S = 19,23,31,...$$ $$L=3, N_1 = 2, N_2 > 2, S = 29,37,53,...$$ $$L=3, N_1 = 3, N_2 > 3, S = 49,65,97,...$$ and so on.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .