# PDF Archive

Easily share your PDF documents with your contacts, on the Web and Social Networks.

## Proven .pdf

Original filename: Proven.pdf

This PDF 1.4 document has been generated by Google / , and has been sent on pdf-archive.com on 24/10/2016 at 00:09, from IP address 86.133.x.x. The current document download page has been viewed 349 times.
File size: 1.5 MB (15 pages).
Privacy: public file

### Document preview

Proving
the
collatz
conjecture
Indaend

10/23/2016

Introduction to the problem
The collatz conjecture can be defined as a simple
algorithm:
•If the number is even, divide it by two.
•If the number is odd, triple it and add one.
The conjecture asks, If we kept doing this as an iterative
sequence, would we eventually reach 1, for all integers?

Examples
3 is odd, so we multiply it by 3 and add 1, to get 10
10 is even, so we divide by 2 to get 5
5 is odd, so we multiply it by 3 and add 1, to get 16
16 is even, so we divide by 2 to get 8
8 is even, so we divide by 2 to get 4
4 is even, so we divide by 2 to get 2
2 is even, so we divide by 2 to get 1
We can represent this chain as the following:
3, 10, 5, 16, 8, 4,
2, 1.
Other examples:
21, 64, 32 ,16, 8, 4,
256, 128 , 64, 32 ,16, 8, 4, 2,
2, 1.
1.
14, 7 , 22, 11 , 34, 17 , 52, 26 , 13 , 40 , 20 , 10 , 5 ,16,
8, 4, 2, 1.

Structure and Tree (1)
From the algorithm, we can start to plot backwards to
make a tree, and we start from the number 1 going
outwards.
The number 2 can divide by 2 to reach
1
The number 4 can divide by 2 to reach
2
This continues on to 16, where we
meet a fork, where we have 2 numbers
go into 1.
The fork happens because there
are numbers that can be written as
both 3 times an odd number, plus 1
, and an even number divided by 2
These numbers have the form (6x-2)
The number 4 is of form (6x-2) , The 2 numbers below it
are 8 and 1, Note that 1 can loop itself by going:
1,4,2,1,4,2,1.
This is evidence of a loop within the tree, it is conjectured
that this the only loop in the tree, otherwise a number
within the loop would not reach 1:
For example, if we were to allow negative numbers, the
number -5 would go:
-5,-14,-7,-20,-10,-5

Structure and Tree (2)
Expanding the tree even further grants a more visual
understanding of the problem, From the diagram below, we
can see a very distinct pattern. Each (6x-2) can multiply by 4
to create another number of form (6x-2) , Thus forks are
plentiful.
Below is the expanded tree up to 19 orbits:

Note that the multiples of 3 don’t have any forks, This is
because No multiple of 3 can be expressed in the form
(6x-2) , So it just multiplies by 2 forever. This brought an
idea forward that could shape my understanding of the
tree itself.

Colour coding
Given the properties of the multiples of 3 (3x), I decided to
colour code the tree to see what would happen for the
numbers (3x-1) and (3x-2)
All (3x) are Yellow ,All (3x-1) are Green, All (3x-2) are Red

3 things to note:
• All the numbers that start the forks are of form
(6x-2), which are always of form (3x-2)
• Multiplying a (3x-1) by 2 will grant a number form
(3x-2), Multiplying a (3x-2) by 2 will grant a number
form (3x-1).
• Hence a pattern (3x-1), (3x-2), (3x-1), (3x-2) is created

Sub-Trees (1)

Looking at the odd numbers within the tree, I noticed that the
odd numbers of each class shared the same properties.
a number of form (3x-1) below
them before moving on to the
number of form (6x-2) below.

All numbers (6x-1) didn’t have this
problem, They would reach the
(6x-2) number below like normal.

As I mentioned earlier, all multiples
of 3 would never reach a (6x-2), so
the sub tree stood as this.

These 3 sub-trees are the building blocks that make up
the tree itself, and can be used to make generalizations,
As I will discuss on the next page.

*The odd values of the sequence (3x-2), I.e. if we have 3x-2
as 1,4,7,10,13… , and only want the odd numbers, we would
jump 2 steps at a time, Giving us 1,7,13. Or (6x-5). This also
works for (3x-1) and (6x-1).

Sub-Trees (2)
From the observations , We can fill in the sub-trees with
the forms of the odd numbers.
A purple arrow denotes a multiplication by 2
A pink arrow denotes a the number subtract 1, and divided
by 3.
When going in the opposite direction, apply the inverse.
18n-2

Starting with (6x-1) , we can use
the formulae to get the forms of
the numbers above and to the
left.

6x-1

36n-4
18x-14

Starting with (6x-5) , we can use
the formulae to get the forms of
the numbers above , to the left
and below.

Starting with (6x-3) , we can use
the formulae to get the forms of
the numbers above and to the
left.

12x-10

18x-8

36x-16

From these structures, we have accounted
for all number forms* , Therefore I can
safely assume that there are no numbers
that do not follow these sub trees.
* (36x-a) from a=1 to a
=36)

6x-5

36x-28

6x-3

12x-6

The 4n+1 rule
Each odd number has the ability to move up the sub-tree
with 3x+1, but instead of dividing by 2 like the algorithm
instructs us to, we are going to move down to the left

From the left , we have to multiply by 2 again, we
know from earlier that a (6x-2) multiplied by 4 will
reach another number form (6x-2), therefore, it will
reach the top of another sub-tree with an odd of
unknown form.

The 4x+1 rule showed that we could move to another
odd by going up and around the tree, but what if we
went downwards?
The (6x-1) sub tree reaches the
top of the next tree immediately
when multiplying by 2, From here
we can just do (x-1)/3 to get the
odd.

6x-1

For all (6x-1), we can reach the
next odd downwards by iterating
(2x-1)/3
The (6x-5) sub tree reaches
the 12x-10 below it when
multiplying by 2, From here new
need to multiply by 2 again to
reach the top of the next
sub-tree, Then we do (x-1)/3 to
get the odd.

6x-5

For all (6x-5), we can reach the
next odd downwards by
iterating (4x-1)/3
The (6x-3) sub tree will never
reach an odd number going
downwards.
Now that we are able to obtain odds in both directions, It is
possible to create a tree for all of the odd numbers.