Relation between Collatz Conjecture and the Fibonacci-sequence

 

The two Collatz transformations are as follows: an even number must be divided by 2 (n/2), an odd number must be multiplied by 3 followed by subtraction of 1 (3n-1).

 

Restrict the two Collatz-transformations to just E (even) and O (odds).

An odd number will always be succeeded by one even number, and an even number will be succeeded by either an even or an odd number.

 

Starting off with O will yield {E}, starting off with E will yield {E O}.

This is known as a Context Free rewrite grammar.

This can be represented as a tree, in which an O node always directly and exhaustively dominates {E}, whereas E always directly and exhaustively dominates {E O}.

The first six applications of the two transformations will form a path through the following tree:

 

O

E

E                                                                                                                          O

E                                                                    O                                                  E

E                                O                                E                                                  E                                O

E              O              E                                E              O                                E              O              E

EO          E              EO                            EO          E                                EO          E              EO         

 

Counting the number of E's and O's on each row, top-down, yields the following sequence:

Even-Odd

0-1

1-0

1-1

2-1

3-2

5-3

8-5

 

The next rows (not in the tree) would be like this:

13-8

21-13

34-21

and so on.

 

These numbers constitute the Fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21. 34. 55. 89 and so on. The even numbers are always one step ahead of the odd numbers as far as the amount of E and O nodes is concerned.

 

A path through this tree bottom up is formed by going one level up and choosing the first node directly (in a straight line) above it or else the first node on the left. These vertical paths are similar in form to the horizontal linear sequences.

The following 13 paths represent all possible combinations of even and odd numbers for the first six applications, starting off with the leftmost E bottom up:

 

01. EEEEEEO

02. OEEEEEO

03. EOEEEEO

04. EEOEEEO

05. OEOEEEO

06. EEEOEEO

07. OEEOEEO

08. EOEOEEO

09. EEEEOEO

10. OEEEOEO

11. EOEEOEO

12. EEOEOEO

13. OEOEOEO

 

This set of paths covers all possible combinations of even and odd numbers produced by the first 6 applications of the two Collatz transformations.

 

[]