A378376 Smallest starting x which requires n steps to reach 1 under the map x -> 3x-1 if x odd, x -> 3x-1 or x/2 if x even.

1, 2, 4, 8, 3, 6, 11, 22, 43, 15, 29, 10, 20, 7, 14, 5, 9, 18, 35, 13, 23, 46, 91, 31, 61, 21, 41, 81, 161, 55, 109, 37, 73, 25, 49, 17, 33, 65, 129, 257, 87, 173, 341, 117, 225, 455, 153, 305, 607, 209, 405, 809, 273, 543, 185, 369, 721, 1433, 481, 961, 321

Offset

0,2

Comments

The number of steps required is A261870(x) so that a(n) = x is the smallest x where A261870(x) = n.

a(n) <= 2^n is a simple upper bound, since x = 2^n requires n steps to reach 1.

But 2*a(n-1) = x is not an upper bound on a(n), since although x/2 = a(n-1) requires a further n-1 steps, x can also step to 3x-1 and doing so might be fewer steps (which it is for example at n=45).

a(n) >= (a(n-1)+1)/3 is a lower bound since a(n) = x must have 3x-1 >= a(n-1) so as to reach somewhere requiring n-1 further steps.

If a(n-1) == 2 (mod 6), then equality a(n) = (a(n-1)+1)/3 holds since then a(n) is odd and its first step must be 3x-1 (as for example at n=4).

Links

Kevin Ryde, Table of n, a(n) for n = 0..120

Kevin Ryde, C Code

Example

For n=4, a(4) = 3 is the smallest x requiring n=4 steps to reach 1 (by trajectory 3 -> 8 -> 4 -> 2 -> 1).
a(4) = 3 is also an example where a(n) is its lower bound (a(n-1)+1)/3 (with a(3) = 8).

Prog

(C) /* See links. */

Crossrefs

Cf. A261870.

Sequence in context: A243062 A341993 A232645 * A257470 A139080 A036118

Adjacent sequences: A378372 A378373 A378375 * A378377 A378378 A378379

Keyword

nonn,new

Author

Kevin Ryde, Nov 25 2024

Status

approved