OFFSET
0,3
COMMENTS
The Collatz problems (related problems known by various names, see references) involve iterating the Collatz Mapping (A006370) which applies either 3n+1 or n/2 iteratively when n is odd or even respectively. Considering f(x)=3x+1 and g(x)=x/2 as integer operations of interest, we ask what is the shortest sequence of these operation that produces the nonnegative integers starting with x_0=1. One is chosen as the starting value since producing the number one is the stopping condition for the Hailstone sequences (A006577). The number of distinct shortest sequences of operations (A375495) and the numbers with unique, shortest constructions (A375496) are also of interest.
Seems likely there is a sequence of f and g starting from 1 to reach each nonnegative integer, but a proof has not been proposed.
LINKS
Eric Weisstein's World of Mathematics, Collatz Problem
EXAMPLE
For example, to start with 1 and produce the number 7. The shortest sequence is unique and length 3: (3*x+1, floor(x/2), 3*x+1) = f(g(f(x_0))), which follows the trajectory x_0=1, x_1=4, x_2=2, x_3=7.
PROG
(Python)
from itertools import product
seq = [None for _ in range(200)]
num = [ 0 for _ in range(len(seq))]
for L in range(0, 23):
for P in product((True, False), repeat=L):
x = 1
for upward in P:
x = 3*x+1 if upward else x//2
if x < len(seq):
if num[x] == 0 or L < seq[x]:
seq[x], num[x] = L, 1
elif L == seq[x]:
num[x] += 1
print(', '.join([str(x) for x in seq]))
CROSSREFS
KEYWORD
nonn
AUTHOR
Russell Y. Webb, Aug 18 2024
STATUS
approved