A375496 -id:A375496 - 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.

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, 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, 13, 5, 5, 18, 10, 10, 10, 10, 5, 10, 10, 10, 10, 15, 10, 10, 10, 10, 10, 10, 10

Offset: 0

Russell Y. Webb, Aug 18 2024

nonn

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.

			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.

Eric Weisstein's World of Mathematics, Collatz Problem

Cf. A375495 (number of ways), A375496 (with unique way).

Cf. A125731.

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]))

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

Original entry on oeis.org

1, 1, 1, 2, 1, 4, 1, 1, 6, 1, 3, 1, 14, 1, 2, 5, 5, 1, 28, 1, 1, 4, 1, 9, 5, 9, 1, 48, 1, 1, 2, 3, 10, 1, 1, 15, 5, 23, 12, 2, 1, 131, 1, 3, 1, 4, 6, 3, 20, 5, 2, 1, 1, 27, 5, 43, 34, 25, 1, 4, 1, 1, 332, 1, 5, 5, 2, 1, 10, 8, 12, 3, 37, 5, 5, 4, 10, 2, 1, 1, 39, 5, 63, 68, 67

Offset: 0

Russell Y. Webb, Aug 18 2024

nonn

The minimum number of operations is A375494(n) and that minimum is attained by a(n) different sequences of operations.

Cf. A375494 (number of operations), A375496 (indices of 1's).

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 num]))

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python