A375495 -id:A375495 - 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]))

A375496 Nonnegative integers k which have a unique minimum length construction starting from 1 and choosing operations f(x) = 3x+1 or g(x) = floor(x/2).

Original entry on oeis.org

0, 1, 2, 4, 6, 7, 9, 11, 13, 17, 19, 20, 22, 26, 28, 29, 33, 34, 40, 42, 44, 51, 52, 58, 60, 61, 63, 67, 78, 79, 85, 87, 88, 90, 92, 100, 101, 103, 117, 119, 121, 127, 128, 132, 133, 135, 150, 152, 154, 155, 157, 175, 179, 181, 182, 184, 190, 191, 198, 200, 202, 225, 231, 233, 235

Offset: 0

Russell Y. Webb, Aug 31 2024

nonn

A375495(k) is the number of ways to reach k by the minimum length construction and the present sequence is those k for which A375495(k) = 1.
This sequence is infinite, since k = f(f(f(...(1)))) (A003462) is always a unique minimum construction.
Experimentally, it is observed that many of the integers with unique smallest constructions have one or more g(x) steps in their construction and the position of those g(x) operations does not follow an obvious pattern; meaning that these unique constructions are complex and may be related to the complexity of the Hailstone sequences (A127933).

			9 is a term since the shortest sequence of f and g to reach 9 (length A375494(9) = 5) is unique g(f(g(f(f(1))))) = 9.
Here are some of the unique, smallest constructions. All other positive integers smaller than 28 do not have unique, smallest constructions.
0 = g(1)
1 = 1
2 = g◦f(1)
4 = f(1)
6 = g◦f◦f(1)
7 = f◦g◦f(1)
9 = g◦f◦g◦f◦f(1)
11 = g◦f◦f◦g◦f(1)
13 = f◦f(1)
17 = g◦f◦g◦f◦f◦g◦f(1)
19 = f◦g◦f◦f(1)
20 = g◦f◦f◦f(1)
22 = f◦f◦g◦f(1)
26 = g◦f◦g◦f◦g◦f◦f◦g◦f(1)
28 = f◦g◦f◦g◦f◦f(1)

Cf. A375494 (minimum steps), A375495 (ways attained).

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(i) for i,x in enumerate(num) if x==1]))

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