0
$\begingroup$

It can be shown that the output of the Collatz algorithm (3n + 1)/2^k where n is 1 mod 2 and k is a natural number is 1 or 5 mod 6. Does this mean that all Collatz orbits begin with 3 mod 6?

New contributor
Javier Taylor is a new contributor to this site. Take care in asking for clarification, commenting, and answering. Check out our Code of Conduct.
$\endgroup$
4
  • 1
    $\begingroup$ An orbit (or trajectory) starts with a given number which can be any positive integer. It is possible that we can reduce Collatz to a proof for all numbers of the form $6k+3$. I do not know which such reductions have been established. $\endgroup$
    – Peter
    Sep 22 at 18:16
  • 1
    $\begingroup$ And obviously, there are trajectories having no number of the form $6k+3$ , for example if we begin with a power of $2$. $\endgroup$
    – Peter
    Sep 22 at 18:39
  • $\begingroup$ Only the first element of a trajectory can be divisible by 3. In your style of transformation-rule (often called "syracuse style") indeed each iterate (except the initial value) is moreover of the form $6x \pm 1$. $\endgroup$ Sep 22 at 22:37
  • $\begingroup$ @Peter - reading your first comment: just tried to put together the reduction-argument, just composed as draft, but I think it's working. Pls see my answer-box. $\endgroup$ Sep 22 at 23:12

1 Answer 1

0
$\begingroup$

This is to @Peter's hint towards the possibility of proof on a reduced set of numbers, namely $6k+3$. I think, this is a simple proof for such a reducibility. We want to show, that not only all numbers divisible by $3$ are in the branches of the tree of trajectories, but even that no number of the form $6k \pm 1$ exists which has no $6j+3$-precedessor on its branch of the tree.

The reverse operation of the Syracuse-transformation is $$ a_1 = {2^A a_2 -1 \over 3} $$ where $A$ must be of the form such that the numerator becomes divisible by $3$. The following table shall show that all numbers $6k \pm 1$ must have a $6j+3$-precedessor applying some $A \in \{1,2,3,4,...\}$: $$\small \begin{array} {rl|rl} (6k+1) \cdot 2^1 - 1 &= 12k+1 & (6k+1) \cdot 2^2 - 1 &= 24k+3 \\ (6k+1) \cdot 2^3 - 1 &= 36k+7 & (6k+1) \cdot 2^4 - 1 &= 64k+15 \\ \vdots && \vdots \\ (6k-1) \cdot 2^1 - 1 &= 12k-3 &(6k-1) \cdot 2^2 - 1 &= 24k-5 \\ (6k-1) \cdot 2^3 - 1 &= 36k-9 &(6k-1) \cdot 2^4 - 1 &= 36k-17 \\ \vdots && \vdots \\ \end{array} $$ So every number of the form $a_2=6k \pm1 $ has a predecessor of the form $3j$, so

every odd number not of the form $6k+3$ has a predecessor of the form $6j+3$ and this implies that there are no odd numbers $6k+3$ which are not in a (branch of a) trajectory with a leading number $6j+3$ and so proving Collatz only for all odd numbers divisible by $3$ suffices to prove Collatz for all odd numbers.

Comment: this does not interfere with the question of divergent trajectories: whether a trajectory is divergent or not does not affect the question of existence of branches having heads divisible by $3$.

$\endgroup$

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