This site is supported by donations to The OEIS Foundation.

3x+1 problem

From OeisWiki
(Redirected from Collatz trajectories)
Jump to: navigation, search

The 3x+1 problem concerns an iterated function and the question of whether it always reaches 1 when starting from any positive integer. It is also known as the Collatz problem or the hailstone problem.

The function is

For example, . And . This leads to the sequence 3, 10, 5, 16, 4, 2, 1, 4, 2, 1, ... which indeed reaches 1. A sequence obtained by iterating the function from a given starting value is sometimes called "the trajectory" of that starting value.

Obviously there can be no consecutive odd numbers in any trajectory, but there may certainly be consecutive even numbers, especially when the trajectory reaches a power of 4, in which the trajectory quickly plummets to 1 after passing through all the intervening powers of 2. (Note that since the odd-indexed powers of 2 are congruent to 2 modulo 3, they are only reachable from halving a power of 4).

What is not so obvious is whether every trajectory eventually reaches a power of 4.

See also reduced Collatz function.

Collatz trajectories

Pure hailstone numbers are those which do not occur in the trajectories of smaller numbers, while impure hailstone numbers are those which do occur in the trajectories of smaller numbers.

The 3x+1 problem trajectories might be of 3 kinds

  • Trajectories heading towards infinity
  • Trajectories that eventually become nontrivially (1, 4, 2, 1, 4, 2, ... excluded) cyclic
  • Trajectories that eventually hit a power of 2 (thus falling straight down to 1, like hailstones, and then going through the trivial cycle 1, 4, 2, 1, 4, 2, ...)

Trajectories heading towards infinity

According to the Collatz conjecture, no 3x+1 problem trajectories heading towards infinity exist!

Eventually nontrivially cyclic trajectories

According to the Collatz conjecture, no 3x+1 problem eventually nontrivially cyclic trajectories exist!

But the 3x-1 problem does have eventually nontrivially cyclic trajectories!

Trajectories that eventually hit a power of 2

The Collatz conjecture stipulates that all 3x+1 problem trajectories eventually hit a power of 2 (thus falling straight down to 1, like hailstones.)

Table of trajectories

The number of halving and tripling steps for to reach 1 in 3x+1 problem (Cf. A006577) is

{0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20, 7, 7, 15, 15, 10, 23, 10, 111, 18, 18, 18, 106, 5, 26, 13, 13, 21, 21, 21, 34, 8, 109, 8, 29, 16, 16, 16, 104, 11, 24, 24, 24, 11, 11, 112, 112, 19, 32, 19, 32, ...}

The pure hailstone numbers , i.e. those which do not occur in the trajectories of smaller numbers, (Cf. A061641) are

{0, 1, 3, 6, 7, 9, 12, 15, 18, 19, 21, 24, 25, 27, 30, 33, 36, 37, 39, 42, 43, 45, 48, 51, 54, 55, 57, 60, 63, 66, 69, 72, 73, 75, 78, 79, 81, 84, 87, 90, 93, 96, 97, 99, 102, 105, 108, 109, 111, 114, 115, 117, 120, 123, ...}

The number of halving and tripling steps for pure hailstone numbers to reach 1 in 3x+1 problem (i.e. A006577(k), k = pure hailstone numbers from A061641). (Cf. A127933) is

{0, 0, 7, 8, 16, 19, 9, 17, 20, 20, 7, 10, 23, 111, 18, 26, 21, 21, 34, 8, 29, 16, 11, 24, 112, 112, 32, 19, 107, 27, 14, 22, 115, 14, 35, 35, 22, 9, 30, 17, 17, 12, 118, 25, 25, 38, 113, 113, 69, 33, 33, ...}

The impure hailstone numbers , i.e. those which occur in the trajectories of smaller numbers, (Cf. A134191) are

{2, 4, 5, 8, 10, 11, 13, 14, 16, 17, 20, 22, 23, 26, 28, 29, 31, 32, 34, 35, 38, 40, 41, 44, 46, 47, 49, 50, 52, 53, 56, 58, 59, 61, 62, 64, 65, 67, 68, 70, 71, 74, 76, 77, 80, 82, 83, 85, 86, 88, 89, 91, 92, 94, 95, 98, ...}

The following table gives the sequences resulting from iterating the Collatz function starting with the first few pure hailstone numbers (see A061641)

"3x+1 problem" trajectories
A-number Trajectory

until known

Trajectory

until 1

Steps

to 1

(A127933)

1 Trivial cycle {1, 4, 2, 1, ...} {1, ...} 0
3 A033478 {3, 10, 5, 16, 8, 4, 2, 1, ...} {3, 10, 5, 16, 8, 4, 2, 1, ...} 7
6 {6, 3, ...} {6, 3, 10, 5, 16, 8, 4, 2, 1, ...} 8
7 {7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, ...} (see n = 3) {7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, ...} 16
9 {9, 28, 14, 7, ...} {9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, ...} 19
12 {12, 6, ...} {12, 6, 3, 10, 5, 16, 8, 4, 2, 1, ...} 9
15 {15, 46, 23, 70, 35, 106, 53, 160, 80, 40, ...} (see n = 7) {15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, ...} 17
18 {18, 9, ...} {18, 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, ...} 20
19 {19, 58, 29, 88, 44, 22, ...} (see n = 9) {19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, ...} 20
21 A033481 {21, 64, 32, 16, ...} (see n = 3) {21, 64, 32, 16, 8, 4, 2, 1, ...} 7
24 {24, 12, ...} {24, 12, 6, 3, 10, 5, 16, 8, 4, 2, 1, ...} 10
25 {25, 76, 38, 19, ...} {25, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, ...} 23
27 A008884 {27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, ...} (see n = 15) {27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, ...} 111
30 {30, 15, ...} {30, 15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, ...} 18
33 A008880 {33, 100, 50, 25...} {33, 100, 50, 25, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, ...} 26
36 {36, 18, ...} {36, 18, 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, ...} 21
37 {37, 112, 56, 28, 14, 7, ...} {37, 112, 56, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, ...} 21
39 A008878 {39, 118, 59, 178, 89, 268, 134, 67, 202, 101, 304, 152, 76, ...} (see n = 25) {39, 118, 59, 178, 89, 268, 134, 67, 202, 101, 304, 152, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, ...} 34
42 {42, 21, ...} {42, 21, 64, 32, 16, 8, 4, 2, 1, ...} 8
43 {43, 130, 65, 196, 98, 49, 148, 74, 37, ...} {43, 130, 65, 196, 98, 49, 148, 74, 37, 112, 56, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, ...} 29
45 {45, 136, 68, 34, ...} (see n = 7) {45, 136, 68, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, ...} 16
48 {48, 24, ...} {48, 24, 12, 6, 3, 10, 5, 16, 8, 4, 2, 1, ...} 11
51 A008883 {51, 154, 77, 232, 116, 58, ...} (see n = 19) {51, 154, 77, 232, 116, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, ...} 24
54 {54, 27, ...} {54, 27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, ...} 112
55 A008873

(for n = 97)

{55, 166, 83, 250, 125, 376, 188, 94, ...} (see n = 27) {55, 166, 83, 250, 125, 376, 188, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079, 3238, 1619, 4858, 2429, 7288, 3644, 1822, 911, 2734, 1367, 4102, 2051, 6154, 3077, 9232, 4616, 2308, 1154, 577, 1732, 866, 433, 1300, 650, 325, 976, 488, 244, 122, 61, 184, 92, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, ...} 112
57 A008877 {57, 172, 86, 43, ...} {57, 172, 86, 43, 130, 65, 196, 98, 49, 148, 74, 37, 112, 56, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1, ...} 32
60 {60, 30, ...} {60, 30, 15, 46, 23, 70, 35, 106, 53, 160, 80, 40, 20, 10, 5, 16, 8, 4, 2, 1, ...} 19


A008908 gives the number of steps needed for to reach 1, while A006666 and A006667 give the number of halving steps and the number of tripling steps respectively. The numbers with a record number of steps are given by A006877.

A135282 records the largest exponent such that appears in the trajectory started with . It is believed that these exponents are only odd when itself is odd. That would mean, if the "conjecture" is true, that a given odd-indexed power of 2 is unreachable by iteration of the Collatz function, if you don't start with that given odd-indexed power of 2 initially. If we call the powers of 2, , the trivial argument values of the Collatz function (which trivially fall down to 1 in steps,) the "conjecture" would imply that for every nontrivial argument values of the Collatz function we must reach a power of 4 (even-indexed power of 2) for the Collatz conjecture to be true.

For the limited list provided in A135282, i.e. [1..105], if we consider only the non-trivial argument values of , thus not 2, it seems that the largest is predominantly 4, a few times 6 for {21, 42, 84} (is it continuing as 126, 168, ...?) and 8 for {75, 85} (is it continuing as 155, 165, ...?). In A135282, Masahiko Shin mentions that most of the first ten thousand terms are 4, and there only appear 4,6,8,and 10 in the extent (there are few exceptional terms, for example a(10920)=12, a(10922)=14,) unless is a power of 2, and it seems all terms are even, unless is an odd-indexed power of 2. For non-trivial argument values, it thus seems that the hailstones' final fall is essentially the result of hitting very low powers of 4 (even-indexed powers of 2.) It would be interesting to know, for a typical non-trivial argument value, whether the hailstone went through few big drops big hitting numbers with high evenness or went through many small drops big hitting numbers with low evenness, before it ended up hitting one of those very low powers of 4. Or it might be that for each non-trivial argument we obtain a hailstone history containing both situations in a very intricate way.

Sequences generated by iterating the Collatz function seemingly reach unpredictable heights.[1] Some starting values give sequences that jump up sharply, then come down and fluctuate in the neighborhood of the starting value before hitting a power of 2 and then proceeding predictably towards 1.


Collatz from 37.png


Thus the term "hailstone" is sometimes used to refer to this problem. But there are also starting values that don't jump up significantly until much later on, closer to the final fall. A025586 gives the largest value encountered in such sequences starting with each in turn, while A033493 gives the sum of all values in such a sequence from to the first instance of 1.

Since the powers of two give an element of predictability, it is natural that a tree graph of Collatz sequences put the powers of two on the central axis, or at least line them up.

Collatz Tree Section.png

In the tree graph above, halving steps are denoted by black lines, while blue lines signify tripling steps (plus the addition of 1). The top numbers of each column above can be found in A033491, though of course going from forward rather than backwards from .

Reduced Collatz trajectories

"3x+1 problem" reduced trajectories
A-number Reduced trajectory

until known

Reduced trajectory

until 1

Steps

to 1

(A??????)

1 Trivial cycle {1, ...} {1, ...} 0
3 {3, 5, 1, ...} {3, 5, 1, ...} 2
5 {5, 1, ...} {5, 1, ...} 1
7 {7, 11, 17, 13, 5, ...} {7, 11, 17, 13, 5, 1, ...} 5
9 {9, 7, ...} {9, 7, 11, 17, 13, 5, 1, ...} 6
11 {11, 17, 13, 5, ...} {11, 17, 13, 5, 1, ...} 4
13 {13, 5, ...} {13, 5, 1, ...} 2
15 {15, 23, 35, 53, 5, ...} {15, 23, 35, 53, 5, 1, ...} 5
17 {17, 13, ...} {17, 13, 5, 1, ...} 3
19 {19, 29, 11, ...} {19, 29, 11, 17, 13, 5, 1, ...} 6
21 {21, 1, ...} {21, 1, ...} 1
23 {23, 35, 53, 5, ...} {23, 35, 53, 5, 1, ...} 4
25 {25, 19, ...} {25, 19, 29, 11, 17, 13, 5, 1, ...} 7
27 {27, 41, 31, 47, 71, 107, 161, 121, 91, 137, 103, 155, 233, 175, 263, 395, 593, 445, 167, 251, 377, 283, 425, 319, 479, 719, 1079, 1619, 2429, 911, 1367, 2051, 3077, 577, 433, 325, 61, 23, ...} {27, 41, 31, 47, 71, 107, 161, 121, 91, 137, 103, 155, 233, 175, 263, 395, 593, 445, 167, 251, 377, 283, 425, 319, 479, 719, 1079, 1619, 2429, 911, 1367, 2051, 3077, 577, 433, 325, 61, 23, 35, 53, 5, 1, ...} 41
29 {29, 11, ...} {29, 11, 17, 13, 5, 1, ...} 5
31 {31, 47, 71, 107, 161, 121, 91, 137, 103, 155, 233, 175, 263, 395, 593, 445, 167, 251, 377, 283, 425, 319, 479, 719, 1079, 1619, 2429, 911, 1367, 2051, 3077, 577, 433, 325, 61, 23, ...} {31, 47, 71, 107, 161, 121, 91, 137, 103, 155, 233, 175, 263, 395, 593, 445, 167, 251, 377, 283, 425, 319, 479, 719, 1079, 1619, 2429, 911, 1367, 2051, 3077, 577, 433, 325, 61, 23, 35, 53, 5, 1, ...} 39
33 {33, 25...} {33, 25, 19, 29, 11, 17, 13, 5, 1, ...} 8
35 {35, 53, 27, ...} {35, 53, 27, 41, 31, 47, 71, 107, 161, 121, 91, 137, 103, 155, 233, 175, 263, 395, 593, 445, 167, 251, 377, 283, 425, 319, 479, 719, 1079, 1619, 2429, 911, 1367, 2051, 3077, 577, 433, 325, 61, 23, 35, 53, 5, 1, ...} 43
37 {37, 7, ...} {37, 7, 11, 17, 13, 5, 1, ...} 6
39 {39, 59, 89, 67, 101, 19, ...} {39, 59, 89, 67, 101, 19, 29, 11, 17, 13, 5, 1, ...} 11
41 {41, 31, ...} {41, 31, 47, 71, 107, 161, 121, 91, 137, 103, 155, 233, 175, 263, 395, 593, 445, 167, 251, 377, 283, 425, 319, 479, 719, 1079, 1619, 2429, 911, 1367, 2051, 3077, 577, 433, 325, 61, 23, 35, 53, 5, 1, ...} 40
43 {43, 65, 49, 37, ...} {43, 65, 49, 37, 7, 11, 17, 13, 5, 1, ...} 9
45 {45, 17, ...} {45, 17, 13, 5, 1, ...} 4
47 {47, 71, 107, 161, 121, 91, 137, 103, 155, 233, 175, 263, 395, 593, 445, 167, 251, 377, 283, 425, 319, 479, 719, 1079, 1619, 2429, 911, 1367, 2051, 3077, 577, 433, 325, 61, 23, ...} {47, 71, 107, 161, 121, 91, 137, 103, 155, 233, 175, 263, 395, 593, 445, 167, 251, 377, 283, 425, 319, 479, 719, 1079, 1619, 2429, 911, 1367, 2051, 3077, 577, 433, 325, 61, 23, 35, 53, 5, 1, ...} 38
49 {49, 37, ...} {49, 37, 7, 11, 17, 13, 5, 1, ...} 7
51 {51, 77, 29, ...} {51, 77, 29, 11, 17, 13, 5, 1, ...} 7
53 {53, 27, ...} {53, 27, 41, 31, 47, 71, 107, 161, 121, 91, 137, 103, 155, 233, 175, 263, 395, 593, 445, 167, 251, 377, 283, 425, 319, 479, 719, 1079, 1619, 2429, 911, 1367, 2051, 3077, 577, 433, 325, 61, 23, 35, 53, 5, 1, ...} 42
55 {55, 83, 125, 47, ...} {55, 83, 125, 47, 71, 107, 161, 121, 91, 137, 103, 155, 233, 175, 263, 395, 593, 445, 167, 251, 377, 283, 425, 319, 479, 719, 1079, 1619, 2429, 911, 1367, 2051, 3077, 577, 433, 325, 61, 23, 35, 53, 5, 1, ...} 41
57 {57, 43, ...} {57, 43, 65, 49, 37, 7, 11, 17, 13, 5, 1, ...} 10
59 {59, 89, 67, 101, 19, ...} {59, 89, 67, 101, 19, 29, 11, 17, 13, 5, 1, ...} 10


Collatz conjecture

In 1937, Lothar Collatz proposed the conjecture

Conjecture (Collatz conjecture, 1937). (Collatz)

In the 3x+1 problem, no matter what number you start with, you will always eventually reach 1.
Paul Erdős said about the Collatz conjecture: "Mathematics is not yet ready for such problems." He offered $500 USD for its solution.[2] A generalization of the problem has been shown to be a computationally unsolvable problem.[3]

Computers, being generally unable to recognize an infinite loop, usually have f(1) := 1 hard-coded in investigations of this problem,[4] or they might get stuck in the 4, 2, 1 cycle.

Collatz 421 Cycle.png

But of course in the search for a counterexample to the Collatz conjecture, they would have to be programmed to keep track of previous numbers encountered in the sequence to compare them against new values. Regardless, the computer would first have to be directed to a specific number after a human mathematician determined the properties the counterexample would need to have.

Obviously a counterexample, if it exists, must not be a power of 2. But how can we know a given number's sequence will not reach a power of 2? By allowing to be negative, some possibilities are suggested: not all sequences for negative values of reach . Sequences for some values, such as , eventually enter this loop:

Collatz Neg51472010 Cycle.png

(Allowing is equivalent to changing the "tripling step" to while maintaining the restriction to positive numbers; see A008894).

Generalizations

M/n sequences

Cf. M/n sequences.

Other generalizations?

A possible generalization of the Collatz function for the  th prime, would be

The Collatz function would thus correspond to

See also

Notes

  1. P. Giblin, Primes and Programming: An Introduction to Number Theory with Computing, Cambridge University Press (1993) p. 32.
  2. Lagarias (1985.)
  3. Lagarias (1985.)
  4. Or f[1] := 1 in Mathematica or f(1) = 1 in C, Java, etc.

External links