Collatz
Introduction
Welcome to an Analysis of the Collatz Algorithm.
I am a retired Air Traffic Controller and software programmer. I was introduced to the Collatz conjecture during a Maths Foundation course with the Open University in 1973 and have played with it, on and off, ever since. I hope you find this site useful and I would appreciate any feedback.
Alan Tyte, BA
The structure described in this paper is based on the following operation. Take any non-negative integer, multiply it by 3 add 1 and divide by 2 until an odd integer is obtained. This is a 'step'. If step(x) = y , then y = (3x+1)/2^k where k>=0 is such that y is odd. The conjecture is that repeating such steps will eventually produce a step for which y = 1. The standard Collatz conjecture is a sub-set of this conjecture as Collatz effectively only tests odd positive integers* and fails for one even integer, i.e. 0 . The paper describes how it is possible to construct the complete graph of integers which converge to a given integer. It was not until even start velues were handled in the way described that a coherent structure for the graph could be produced.
*Some Collatz threads starting with an even number are just part of the calculation of a step, e.g. 16 8 4 2 1 is part of step(5), 56 28 14 7 is part of step(37). The other cases occur when the start value is h.3^n,2^k which Collatz immediately reduces to h.3^n.
The analysis is divided into three papers:
Paper 1: A view of the structure resulting from the Collatz algorithm
Paper 2: A discussion of the implications of the findings in Paper 1
Paper 3: A comparison of 3x+1 and 3x-1
Outline
- The structure of integers which converge to 1 appears to be chaotic, it is, however, possible to see an order in this structure.
- Every integer steps down through a thread of nodes (odd integers prime to 3). Integers which take the same number of steps to converge to a node are at the same level.
- At n levels above each node there is an infinite set of integers which take exactly n steps to converge to that node. It is possible to arrange these integers in an ordered sequence in which each term is expressed as a function of the preceding term. This sequence is an n-chain. The first value in an n-chain is its pivot, subsequent values are links.
- For every n there is an infinite number of n-chains, each of which is constructed using the same set of equations.
- One equation defines all 1-chains, two define all 2-chains, six define all 3-chains and, thereafter, 2 x 3^(n-2) equations are required.
- The threads for n steps from each integer in an n-chain, have no value in common until the node to which they converge.
- No link in an n-chain can be part of a (greater than n)-chain. The proportion of integers available to construct n-chains decreases by a factor of 13/16 for each increment of n.
- Every value in an n-chain is the pivot of an (n-1)-chain, an (n-2)-chain, etc.
- Although the methodology is clear, calculating the equation sequence becomes an increasingly large task as n increases.
- For each n, the n-chain which converges to 1 has a pivot of 0.
- If even integers are excluded from the structure described, then the majority of n-chains would be lost as there are more even pivots than odd pivots. The structure would be incomplete and a majority of odd integers would not appear in the structure.
- Every integer is part of an n-chain structure (even if more than one graph exists). For example : 27 takes 41 steps to converge to 1. 27 is the second term in a 29-chain whose pivot, 59339, is the second term of a 33-chain whose pivot, 3911993580, is the second term of a 40-chain whose pivot, 3569835538891, is the second term of a 41-chain whose pivot is 0. Well no-one expected the structure to be simple !
Summary
An infinite graph of integers converges to every node. The graph of such integers is constructed using the same set of iterative formulae for every node. At each level above a node there is one value, the pivot, from which all the integers at that level may be calculated.