A378847 Smallest starting x which takes n tripling steps to reach the minimum of a cycle in the 3x-1 iteration.

1, 3, 15, 13, 9, 37, 25, 33, 45, 57, 145, 97, 65, 87, 159, 165, 225, 273, 391, 261, 647, 465, 741, 529, 353, 471, 921, 837, 865, 577, 385, 257, 343, 229, 153, 407, 543, 721, 481, 321, 855, 1141, 761, 1015, 677, 903, 1209, 1605, 2149, 1433, 1911, 2529, 3397, 2265

Offset: 0

Author

Kevin Ryde, Dec 15 2024

Keywords

• nonn

Comments

Each step is x -> 3x-1 if x odd, or x -> x/2 if x even (A001281) and here only the tripling steps 3x-1 are counted.

The number of tripling steps is A378833(x) so that a(n) = x is the smallest x for which A378833(x) = n.

All terms are odd since any even x takes a first step to x/2 which is a smaller start for the same number of tripling steps.

a(n) >= L(n) = (2*a(n-1) + 1)/3 is a lower bound since a(n) = x must at least have a first step 3x-1 and halve to (3x-1)/2, then n-1 further tripling steps, so (3x-1)/2 >= a(n-1).

Equality a(n) = L(n) occurs iff L(n) is an integer and not a cycle minimum.

A large upper bound for n>=1, showing a(n) always exists, is a(n) <= U(n) = (4^(3^n) - 1)*2^n/3^n + 1, since U(n) is a candidate for a(n) by taking n steps of (3x-1)/2 to reach 4^(3^n) which is a power of 2.

Tighter upper bounds on a(n) can be found by taking predecessor steps back from a(n-c) seeking c tripling steps to reach a(n-c) if that's possible (which for instance it's not if a(n-c) == 0 (mod 3)).

Such predecessors are candidates for a(n), but the actual a(n) might have a trajectory which does not go through any previous a(n-c).

Examples

			For n=4, a(4) = 9 has 4 tripling steps on its way to 5 which is the minimum of a cycle:
  9 -> 26 -> 13 -> 38 -> 19 -> 56 -> 28 -> 14 -> 7 -> 20 -> 10 -> 5
    ^            ^           ^                      ^
This a(4) = 9 is an example where a(n) is at its lower bound L(n), in this case a(3) = 13 has L(4) = (2*a(3)+1)/3 = 9 which is an integer and not a cycle minimum.
		

Links

• Kevin Ryde, Table of n, a(n) for n = 0..625
• Kevin Ryde, C Code (set count type TRIPLE)

Crossrefs

Cf. A001281 (step), A378833 (number of triplings).

Cf. A378845 (with all steps), A378846 (with halving steps).

Programs

C

/* See links. */