cp's OEIS Frontend

A375494 a(n) = minimum number of operations chosen from f(x) = 3x+1 and g(x) = floor(x/2) needed to reach n when starting from 1.

%I A375494 #33 Sep 11 2024 15:23:17
%S A375494 1,0,2,4,1,6,3,3,8,5,5,5,10,2,7,7,7,7,12,4,4,9,4,9,9,9,9,14,6,6,6,6,
%T A375494 11,6,6,11,11,11,11,11,3,16,8,8,8,8,8,8,13,8,8,8,8,13,13,13,13,13,5,
%U A375494 13,5,5,18,10,10,10,10,5,10,10,10,10,15,10,10,10,10,10,10,10
%N A375494 a(n) = minimum number of operations chosen from f(x) = 3x+1 and g(x) = floor(x/2) needed to reach n when starting from 1.
%C A375494 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.
%C A375494 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.
%H A375494 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/CollatzProblem.html">Collatz Problem</a>
%e A375494 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.
%o A375494 (Python)
%o A375494 from itertools import product
%o A375494 seq = [None for _ in range(200)]
%o A375494 num = [   0 for _ in range(len(seq))]
%o A375494 for L in range(0, 23):
%o A375494    for P in product((True, False), repeat=L):
%o A375494       x = 1
%o A375494       for upward in P:
%o A375494          x = 3*x+1 if upward else x//2
%o A375494       if x < len(seq):
%o A375494          if num[x] == 0 or L < seq[x]:
%o A375494             seq[x], num[x] = L, 1
%o A375494          elif L == seq[x]:
%o A375494             num[x] += 1
%o A375494 print(', '.join([str(x) for x in seq]))
%Y A375494 Cf. A375495 (number of ways), A375496 (with unique way).
%Y A375494 Cf. A125731.
%K A375494 nonn
%O A375494 0,3
%A A375494 _Russell Y. Webb_, Aug 18 2024