3x-1 problem

This article page is a stub, please help by expanding it.

The

3 x  −  1

problem is a variation on the 3 x + 1 problem (or Collatz problem).
The Collatz problem, named after Lothar Collatz who first proposed it in 1937, asks whether the iterated Collatz function

f  (n)

always reaches 1 when

n > 0

, with the Collatz function defined as

$f(n)={\begin{cases}n/2&{\mbox{if }}n\equiv 0{\pmod {2}},\\3n+1&{\mbox{if }}n\equiv 1{\pmod {2}}.\end{cases}}\,$

The

3 x  −  1

problem instead uses the iterated function

$f(n)={\begin{cases}n/2&{\mbox{if }}n\equiv 0{\pmod {2}},\\3n-1&{\mbox{if }}n\equiv 1{\pmod {2}}.\end{cases}}\,$

The 3 x  −  1 problem trajectories

The

3 x  −  1

problem trajectories might be of 3 kinds

• Trajectories heading towards infinity;
• Trajectories that eventually become nontrivially (1, 2, 1, 2, 1, 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, 2, 1, 2, 1, 2, ...).

Trajectories heading towards infinity

Do

3 x  −  1

problem trajectories heading towards infinity exist or not?

Eventually nontrivially cyclic trajectories

The

3 x  −  1

problem does have eventually nontrivially cyclic trajectories!
A003124 One of the basic cycles (of length 18) in the

x ↦ 3 x  −  1

( 

x

odd) or

x / 2

( 

x

even) problem.

{17, 50, 25, 74, 37, 110, 55, 164, 82, 41, 122, 61, 182, 91, 272, 136, 68, 34}

&

{17, 50, 25, 74, 37, 110, 55, 164, 82, 41, 122, 61, 182, 91, 272, 136, 68, 34}

& ...

Trajectories that eventually hit a power of 2

But just like the 3 x + 1 problem, the

3 x  −  1

problem also has trajectories that eventually hit a power of 2 (thus falling straight down to 1, like hailstones). The easiest examples to find (besides the obvious) are numbers of the form

${\frac {2^{2n+1}+1}{3}}\cdot 2^{k},\quad n\geq 0,\ k\geq 0,\,$

which always hit

2 2n +1

.

Table of trajectories

“

3 x  −  1

problem” trajectories

n	A-number	Trajectory (until known)	Comment
1	—	{1, 2, 1, ...}	Trivial cycle {1, ..., 1} with length 2
3	—	{3, 8, 4, 2, 1, ...}	Hits 2 3
5	A003079	{5, 14, 7, 20, 10, 5, ...}	Cyclic {5, ..., 5} with length 5
6	—	{6, 3, ...}	Hits 2 3
9	—	{9, 26, 13, 38, 19, 56, 28, 14, ...}	Eventually cyclic {14, ..., 14} with length 5
11	—	{11, 32, 16, 8, ...}	Hits 2 5
12	—	{12, 6, ...}	Hits 2 3
15	—	{15, 44, 22, 11, ...}	Hits 2 5
17	A003124	{17, 50, 25, 74, 37, 110, 55, 164, 82, 41, 122, 61, 182, 91, 272, 136, 68, 34, 17, ...}	Cyclic {17, ..., 17} with length 18
18	—	{18, 9, ...}	Eventually cyclic {14, ..., 14} with length 5
21	—	{21, 62, 31, 92, 46, 23, 68, ...}	Eventually cyclic {68, ..., 68} with length 18
24	—	{24, 12, ...}	Hits 2 3
27	—	{27, 80, 40, 20, ...}	Eventually cyclic {20, ..., 20} with length 5
29	—	{29, 86, 43, 128, 64, 32, ...}	Hits 2 7
30	—	{30, 15, ...}	Hits 2 5
33	—	{33, 98, 49, 146, 73, 218, 109, 326, 163, 488, 244, 122, ...}	Eventually cyclic {122, ..., 122} with length 18
35	—	{35, 104, 52, 26, ...}	Eventually cyclic {14, ..., 14} with length 5
36	A008894	{36, 18, ...}	Eventually cyclic {14, ..., 14} with length 5

See also

• 3 x + 1 problem