On the 3x + 1 problem
By
SUMMARY: The socalled 3x+1 problem is to prove that all 3x+1
sequences eventually converge. The sequences themselves however and their
lengths display some interesting properties and raise unanswered questions.
These pages supply numerical data and propose some conjectures
on this innocent looking problem.
This page contains the following sections:
This page was last modified on November 6 2014
For any positive integer N a sequence
S_{i} can be defined by putting
S_{0} = N
and for all
i > 0:
S_{i} = S_{i1} / 2 
if S_{i1} is even

S_{i} = S_{i1} * 3 + 1 
if S_{i1} is odd

This latter formula usually gives the sequence its name,
the
3x + 1 problem, sometimes also referred to as the Collatz problem,
the Syracuse problem or some other name.
Thus for N = 13 we find
S_{0} = 13, S_{1} = 40, S_{2} = 20, S_{3} = 10, S_{4} = 5
S_{5} = 16, S_{6} = 8, S_{7} = 4, S_{8} = 2, S_{9} = 1, S_{10} = 4
and from now on the sequence will repeat itself.
Note : although the sequence is equally well defined when the process is
applied to negative integers this page deals with
positive integers only, also known as the Natural Numbers.
Therefore all results on this page shall always be understood to refer to
natural numbers only.
We now define
 Mx(N)
 Mx(N) = lim k → ∞ Max(S_{0},
S_{1}, ..., S_{k})
 Mn(N)
 Mn(N) = lim k → ∞ Min(S_{0},
S_{1}, ..., S_{k})
Thus we will call any positive integer
 Convergent
 if Mn(N) = 1
 Divergent
 if Mx(N) does not exist
 Cyclic
 otherwise
No positive integer N is known which may possibly be divergent, and we therefore
reach the widely believed yet still unproven:
 Conjecture 1a : (weak 3x+1 conjecture)
 No integer N is divergent.
Serious indications exist however that no other cycle but the simple 421
cycle exists. In fact it is already known that any other cycle must
contain at least a very large number of elements.
See the
cycles page to find out the exact numbers
and how they follow from the current status of the problem.
It is therefore not unreasonable to state
 Conjecture 1b : (strong 3x+1 conjecture)
 All positive integers N are convergent.
This conjecture remains unproven to this day.
While most authors on the subject have concerned themselves mainly with proving
conjecture 1b, on these pages we will from here on assume that conjecture 1b holds
and look into a number of other properties of the 3x+1 sequences.
 Glide
 for any positive integer N > 1 let k be the lowest index for which
S_{k} < N.
We shall call k the Glide of N and write this as G(N).
Calculating the Glide for any positive integer is tantamount to showing it is
convergent, as long as all smaller numbers are known to be convergent as well.
Thus we may restate conjecture 1b as follows:
 Conjecture 1b : (strong 3x+1 conjecture, restated)
 All positive integers N > 1 have a finite Glide
This conjecture is obviously unproven as well.
However
Terras proved a very important though weaker theorem:
 Theorem (Terras) :
 Almost all positive integers N have finite Glide.
For an informal proof of this theorem look at the
Terras theorem page
It may not be immediately obvious from the definition of the sequence that
arbitrarily high Glides must exist. But observe that any number of the form
N = 2^{p}  1 with
p > 1 will have
S_{2} = 3 * 2^{p1}  1 and, since
S_{2} is odd :
S_{4} = 3 * 3 * 2^{p2}  1 and eventually
S_{2p} = 3^{p}  1.
Hence S_{i} will not be below N
for at least 2p steps, and therefore G(N) > 2p.
Although Glides are thus unbounded it is a far different proposition to find
the smallest number for which G(N) > k
for any given k.
 Glide Record
 a positive integer N is called a Glide Record
if for all M < N we have G(M) < G(N)
Skipping the trivial numbers 1 and 2 the first Glide Records are
N = 3 G(N) = 6
N = 7 G(N) = 11
N = 27 G(N) = 96
N = 703 G(N) = 132
and so on.
The author calculated Glides over a substantial interval,
and the Glide Records found so far are given in the
Glide Records Table.
 Delay
 for any positive integer N let k be the lowest index for which
S_{k} = 1.
We shall call k the Delay of N and write this as D(N).
 Delay Record
 A positive integer N is called a Delay Record
if for all M < N we have D(M) < D(N).
Lengthy calculations have been made in trying to find Delay Records.
All currently known Delay Records are given in the
Delay Records Table.
Note: to calculate the delay of any number yourself try the
3x + 1 calculator page.
 Residue
 for any positive integer N let E(N) and O(N) denote the number of
elements from S_{0} to S_{D(N)1} which are even or odd,
respectively. Obviously O(N) + E(N) = D(N).
Now due to the construction of the sequence we may write
2^{E(N)} = 3^{O(N)} * N * Res(N)
where Res(N) is a factor equal to the product of
(1 + 1 / ( 3 * S_{i} ) )
taken over the odd elements S_{i} for 0 ≤ i < D(N).
We will call Res(N) the Residue of N.
It turns out that Res(N) is usually small and typically lies
between 1.10 and 1.25. Therefore it appears reasonable to propose
 Conjecture 2a : (weak residue conjecture)
 A number Res_{max} exists such that for every positive integer
Res(N) < Res_{max}.
There are serious indications though that a much more explicit
conjecture can be made:
 Conjecture 2b : (strong residue conjecture)
 For all N : Res(N) ≤ Res(993).
For the evidence to support this conjecture look at the
residues page.
Whether conjecture 2b is true or not, we will from now on assume that at
least conjecture 2a holds, and also that
Res_{max} << 6.
 Completeness
 for all integers N > 1 the Completeness
of N, C(N), is defined by C(N) = O(N) / E(N).
 Theorem 1 :
 For all N > 1: C(N) < ln(2)/ln(3) = 0.63092975...
 Proof :
 From the previous paragraph we had, by definition
2^{E(N)} = 3^{O(N)} * N * Res(N)
Taking the logarithm and regrouping yields
O(N) / E(N) = ln(2) / ln(3)  (ln(N) + ln(Res(N))) / (E(N).ln(3) )
The final term is often small, but always > 0.
This leads to the rather more complex question of how close C(N) can
get to its theoretical limit. If the final term could get infinitesimally close to
zero then the completeness would get infinitesimally close to this limit.
For large N the final term is proportional to
ln(N) / E(N).
The reciprocal of this quantity is usually defined as
Gamma.
 Gamma
 for all integers N > 1 Gamma(N)
is defined by E(N) / ln(N).
There is ample evidence to suggest that Gamma(N) will
not reach
arbitrary large values, and so we reach
 Conjecture 3 :
 A number C_{max} exists such that
for all N > 1 : C(N) < C_{max}.
with C_{max} < ln(2) / ln(3).
Or, in simpler terms: C(N) will
not get infinitesimally
close to its theoretical limit. For the evidence to support this
conjecture look at the
completeness page.
 Completeness Record
 A number N > 1 is called a Completeness Record
if for all M < N we have C(M) < C(N).
Similarly we have
 Gamma Record
 A number N > 1 is called a Gamma Record
if for all M < N we have Gamma(M) < Gamma(N).
From the similarity of their definitions it should come as no surprise that
the tables of known Completeness and Gamma records are virtually the same.
All Completeness and Gamma Records currently known are given in the
Completeness and Gamma Records Table.
Assuming Conjecture 1b holds we can partition the positive integers into
Delay Classes DC_{k} (k=0,1,2,3...) where an integer N is said
to belong to class D(N).
We note that no class is empty as for N = 2^{k}
we have D(N) = k.
 Class Record
 The lowest element of a Delay Class DC_{k}
is called its Class Record, indicated by R_{k}.
Class Records of consecutive classes are often 'related',
the lower one occurring in the sequence of the higher one.
Assuming Conjecture 2a holds, with Res
_{max} < 6 we have:
 Theorem 2 :
 Let R_{k} and R_{k+1} be the records of
Delay Classes k and k + 1, respectively.
Then O(R_{k}) <= O(R_{k+1})
and E(R_{k}) <= E(R_{k+1}).
 Proof :
 Let R_{k} and R_{k+1}
be the records of classes k and k+1 respectively.
Assume O(R_{k})  O(R_{k+1}) = x,
x > 0.
Then R_{k+1} / R_{k} is equal to
2^{x+1} * 3^{x} *
Res(R_{k}) / Res(R_{k+1})
which for positive x is definitely >> 2.
Since N = 2 * R_{k} has a delay of
k + 1 and is smaller than R_{k+1},
this would imply that R_{k+1} would be no class record.
Therefore O(R_{k}) <= O(R_{k+1}).
Assume that E(R_{k})  E(R_{k+1}) = x,
x > 0.
Then R_{k} / R_{k+1}
is equal to 2^{x} * 3^{x+1} *
Res(R_{k+1}) / Res(R_{k})
which for positive x is definitely >> 3.
Since either N = 3 * R_{k+1} + 1 or
N = R_{k+1} / 2 has delay k,
and both are smaller than R_{k} this would imply
that R_{k} would be no class record.
Therefore E(R_{k}) <= E(R_{k+1}).
From the above result we may easily derive
 Theorem 3 :
 Let N be any Completeness Record.
Then N is a Class Record as well.
 Proof :
 Assume a number M < N exists with D(M) = D(N).
• If O(M) = O(N), and thus E(M) = E(N),
then C(M) = C(N) and thus N would be no Completeness Record.
• If O(M) > O(N) then C(M) > C(N) and again
N would be no Completeness Record.
• Finally if O(M) < O(N) then, still assuming
conjecture 2a holds, M would not be < N.
Therefore such an M does not exist and N is therefore a Class Record.
Theoretically a Completeness Record does not necessarily have to be a
Delay Record as well, since a lower number with a higher Delay but
lower Completeness might exist. All currently known
Completeness Records are Delay Records as well though.
The 2000 problem, solved!
In 2008 the candidate record for class 2000 was eventually confirmed.
Therefore it is now known that R_{2000} = 67457,283406,188652
All Class Records currently known are given in the
Class Records Table.
If Conjecture 2a holds, with Rmax << 6, this also implies that
the elements of a Delay Class occur at discrete levels,
which roughly lie a factor 6 apart.
The elements of class 13 for example are 34, 35, 192, 208, 212, 213, 226,
227, 1280, 1344, 1360, 1364, 1365 and 8192. The grouping into four
different "subclasses" is obvious.
In order to work with levels we first define a more basic parameter called the Strength:
 Strength
 For all positive integers N with D(N) = k
the Strength S(N) is defined by
S(N) = 5 * O(N)  3 * E(N).
The Strength of most numbers is well below zero, and positive Strengths are quite rare.
It would appear though that arbitrarily high Strengths should exist.
 Strength Record
 A positive integer N is called a Strength Record
if for all M < N we have S(M) < S(N).
Strength records are extremely rare. Only five nontrivial records are known, and the highest
of those has 15 digits already. They can be found on the
Strength page
together with a few numbers that are currently the best known candidates for the next records.
Based on the Strength it is easy to define the Level. Note that for all numbers
N with D(N) = k we have necessarily
S(N) ≡ 5k (mod 8)
 Level
 For all positive integers N with D(N) = k
the Level L(N) is defined by
L(N) =  [S(N) / 8 ]
(where [x] is meant to be the largest integer ≤ x)
Thus
S(34) = 5 * 3  3 * 10 = 15. Therefore
L(34) = [15/8] = 2.
Similarly
L(192) = 3, L(1280) = 4 and L(8192) = 5.
For any delay k the highest possible level occurs at
N = 2^{k}, as
this is the highest number with this delay.
Level 0 can be seen as the highest level for which
C(N) >= 0.60.
With lower numbers the 'limited availability' of numbers makes statistics a risky approach, but
with higher numbers we may say that the level yields information about the relative 'exclusiveness'
of the record. From a statistical point of view with levels 'close to 0' we find that the lower the
level, the less numbers are found at that level. Although numbers with negative levels do exist they
are quite rare. The only number below 10,000,000,000 for which L(N) < 0
occurs at N = 63,728,127, for which L(N) = 1.
The next ones are L(12,235,060,455) = 1 (D(N) = 1184) and L(13,371,194,527) = 1
(D(N) = 1210). Up to 21,000,000,000 three more level 1 numbers exist, but then
surprisingly the next one does not appear until R_{1408} = 1,444,338,092,271,
a number almost 70 times larger than its predecessor. Only 9 numbers of level 1 exist before the
first number of level 2 occurs: R_{1549} = 3,743,559,068,799. This number shows
a surprisingly high delay, surpassing the previous Delay Record by no less than over one hundred.
Up to 100,000,000,000,000 (10^{14}) one finds approximately 100 numbers of
level 1 and just a single one of level 2, which gives a fair indication of their rarity.
Thus it is rather unexpected the first number of level 3 is found just outside this interval
at N = 100,759,293,214,567. With a Delay of 1820 this number is
not only a Delay Record, surpassing the previous record with no fewer than 158 steps, but a Strength
and Completeness Record as well. Remarkably a further level 3 number pops up almost immediately as
R_{1789} is found at N = 104,797,092,792,063.
A total of 15 level 3 numbers exist between 100 * 10^{12} and 531 * 10^{12}
but no others appear quickly thereafter. In fact no further level 3 numbers exist below 10^{16}.
The next one is N = 12769,884180,266527, over 20 times larger than
the previous one.
Still lower levels are ever harder to come by. As the numbers increase searches become slower and search
intervals get wider. The lowest level 4 number, now confirmed as a Delay and Strength record, has 18
digits. The smallest number of level 5 found so far has 21 digits and the lowest number currently
known of level 10 has no less than 38 digits. Reactions from anybody who might have found stronger
candidates are very welcome!
Any positive integer N can be completely defined by the delay, the level and the residue, i.e. from these
three data N can be calculated exactly. Neither of these however give any information about the path of the
sequence S_{i}. In particular no information is available of Mx(N), the highest number occurring in
the 3x+1sequence. This number is of practical importance as well, since it indicates the minimum number
of bits needed for a computer algorithm to calculate a particular sequence without overflows occurring.
Note: to calculate the maximum of any number yourself try the 3x + 1 calculator page.
 Path Record
 a positive integer N is called a Path Record
if for all M < N we have Mx(M) < Mx(N)
The first Path Records are
N = 2 Mx(N) = 2
N = 3 Mx(N) = 16
N = 7 Mx(N) = 52
N = 15 Mx(N) = 160
N = 27 Mx(N) = 9232
and so on. Path records can be conveniently numbered in the order in
which they occur. Thus P
_{1} = 2, P
_{2} = 3, etc.
A curious observation about the values of Mx(N) is
 Theorem 4 :
 Let N be any odd number > 2. If Mx(N) > 3N + 1
then Mx(N) ≡ 16 (mod 36).
 Proof :
 Let x be Mx(N), where x ≡ a (mod 36).
We note that a can not be odd, since x must be even. We also note that
we can not have a ≡ 2 (mod 4) or else x/2 would be odd which would
yield a higher number than x. Therefore a ≡ 0 (mod 4).
Since x must be produced by a 3n+1 iteration we have a ≡ 1 (mod 3).
This leaves just 4, 16 and 28 as possible values for a.
Assume a = 4. Then let x = 36n+4. The predecessor of x must have been
12n+1. Then its predecessor was 24n+2. Since this number is
not ≡ 4 (mod 6) it must have had 48n+4 as its predecessor.
But this number is greater than x, which contradicts the assumption that x is Mx(N).
Similarly for a = 28 we find predecessors 12n+9, 24n+18 and 48n+36,
which again contradicts the assumption that x is Mx(N).
Therefore we can only have a = 16, and therefore Mx(N) ≡ 16 (mod 36)
(and its predecessors in the sequence are 12n+5, 24n+10 and 8n+3).
For all Path Records
P_{i} ≥ 3 we indeed have
Mx(P_{i} ) > 3.P_{i} + 1,
therefore for
i ≥ 2 all
Mx(P_{i} ) ≡ 16 (mod 36).
A list of all currently known Path Records can be found in the
Path Records Table.
 Expansion
 The Expansion with respect to Q, X_{Q} of N is defined as
X_{Q}(N) = Mx(N) / N^{Q}
It is easily seen that
X_{1}(N) is unbounded, since if
N = 2^{p}  1 then, as we saw earlier,
S_{2p} = 3^{p}  1
and
Mx(N) / N is at least approximately equal to
3^{p} / 2^{p}.
A more interesting question arises when we ask for which
p X_{p}
might stay bounded. The following result is well known:
 Theorem 5 :
 X_{Q} is unbounded for Q < ln(3) / ln(2)
 Proof :
 We saw earlier that for N = 2^{p}  1
Mx(N) will be at least 3^{p}  1.
Thus for p towards infinity
ln(X_{Q}( N )) = ln( Mx(N) )  Q * ln( N ) >=
p * ( ln(3)  Q * ln(2) )
So for Q < ln(3) / ln(2) the limit does not exist.
When
^{2}log( Mx(P_{i} )) is depicted graphically against
^{2}log( P_{i} ) the
curve
shows a tendency to become linear with an approximate slope of 2.
It is not currently known whether or not this tendency is likely to persist.
If it does it implies that
X_{Q}(N) is bounded for
Q > 2.
 Open Question 1 :
 Does a number C exist for which X_{2}(N) < C
for all N ?
And if it does, what is the value of C ?
For many years the highest
X_{2}(N) known was that of
P_{62}
(± 15.054) and it looked unlikely a higher one would be found in the near future.
In 2005 however
Tomás Oliveira e Silva
found
P_{88} which has an expansion of ± 16.315.
As can be seen from the
Path Records Table record expansions
are very rare. The function
X_{2}(N) reaches a temporary maximum of
12.66 at
N = 27, which holds until
P_{43} = 319,804,831
is reached, a number over 10,000,000 times larger.
Again, the value of
13.83 reached by
P_{43}
is not surpassed until
P_{62}, which scores
15.05.
P_{62} is over 10,000 times larger than
P_{43}.
Finally the highest expansion currently known is that of
P_{88} which
reaches
16.32.
P_{88} is well over 500,000 times larger than
its predecessor.
If successive gaps between ever higher values of the function
X_{2}(N) continue to be of this magnitude it looks unlikely
we will ever know more than a handful of Expansion Records.
•
In August 1999 the
first conference on the 3x+1 problem took place in Eichstätt.
•
Here's a nice picture of the Eichstätt conference
participants.
•
Lagarias overview of the 3x+1 problem.
•
SuperIndex of the 3x+1 Problem and its generalizations.
•
Gary T. Leavens and Mike Vermeulen : 3x+1 search programs
Computers Math. Applic. Vol. 24, No 11, pp. 7999 (1992)
•
Tomás Oliveira e Silva
was the first to find all Path and Glide Records up to 100.2
^{50}.
He has extended his search well beyond 2
^{60}.
•
MathWorld page
on the collatz Problem
•
The
OnLine
Encyclopedia of Integer Sequences contains many sequences related to the 3x+1 problem;
for instance
A6370,
A6884,
A600412,
A6577,
A6877 and
A6878.
•
This
French page
allows you to do calculations yourself.
•
Eric Farin has developed a number of
very interesting models.
•
Ken Conrow's
3x+1 problem structure page.
•
This excellent
online 3x+1 calculator by Alfred Wassermann can handle really big numbers as well.
•
Marc Lapierre's page to
calculate the delay and paths of arbitrary big numbers.
•
Darrell Cox is
researching 3x+1 and 3x1 loops.
•
Peter Schorer believes he might have a proof of the 3x + 1 Conjecture.
Take a look at his papers
here.
•
Thanks to some hard working Chinese translators you can also view this page in
Chinese.
All numbers up to 2^{60}
( ± 1153 * 10^{15} ) have been double checked for convergence. 
All numbers up to 213,800 * 10^{12}
have been checked for class records. ( View progress ) 

Number of Glide Records 
32 
Highest known Glide Record 
1575  at N = 
180352,746940,718527 
Highest known Residue 
1.253142  at N = 
993 
Number of Class Records 
2088  
Number of Delay Records 
131  
Highest known Delay Record 
2255  at N = 
209798,591621,802462 
Number of Completeness Records 
16  
Highest known Completeness Record 
0.605413  at N = 
104899,295810,901231 
Number of Gamma Records 
15  
Highest known Gamma Record 
35.823841  at N = 
104899,295810,901231 
Number of confirmed Path Records 
87  
Highest confirmed Path Record 
± 319,391 E+30  at N = 
1,038743,969413,717663 
Highest known Expansion (for Q=2) 
16.315  at N = 
1,980976,057694,848447 
To find out more on the programming techniques used to obtain these results
please consult this page on technical details.
Whenever (computer) time is available the quest for new records still continues!
But with numbers getting ever larger, more and more CPU time is needed
to make any progress.
The program runs totally unattended, so anyone with lots of idle time on a PC can
join the 3x+1 search! Just look at the 3x+1 search page to see
how to join, or take a look at the Class record progress map.
Special thanks to Luigi Morelli from Italy who was first to join
and to Kevin Hebb from Canada for the time and effort he took for many
years to make two entire classrooms of PC's work day and night on the problem.
Please mail any offers for additional help to
of these pages.
You are visitor number: