A378375 Number of ways to go from n to 1 by the minimum number of steps of x -> 3x-1 if x odd, x -> 3x-1 or x/2 if x even.

1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 1, 1, 2, 2, 1, 1, 22, 2, 2, 2, 3, 1, 1, 1, 15, 1, 2, 2, 1, 1, 3, 1, 15, 34, 2, 4, 8, 2, 1, 2, 2, 7, 1, 1, 2, 2, 3, 1, 11, 22, 2, 2, 1, 2, 8, 2, 5, 1, 1, 1, 1, 3, 4, 1, 10, 30, 2, 1, 1, 2, 1, 4, 6, 15, 2, 2, 1, 1, 1, 2, 1, 3, 6, 11

Offset: 1

Author

Kevin Ryde, Nov 25 2024

Keywords

• nonn

Comments

The minimum number of steps is A261870(x).

For odd n > 1, a(n) = a(3*n-1) since the first step must be n -> 3n-1.

For even n, a(n) = a(3*n-1) or a(n/2) or their sum a(3*n-1) + a(n/2), depending on which one or both of 3n-1 or n/2 are the minimum steps.

a(2^k) = 1 since the minimum number of steps for 2^k is k steps of x/2..

a(n) = 0 if there's no way to go from n to 1 (if any such n exists).

Examples

			For n=20, the a(20) = 2 ways to go from 20 to 1, by the minimum A261870(20) = 12 steps, are
  20, 59, 176, 88, 44,  22, 11, 32, 16, 8, 4, 2, 1
  20, 10,  29, 86, 43, 128, 64, 32, 16, 8, 4, 2, 1
This is a case where n is even and 3n-1 and n/2 are the same number of steps so that a(n) = a(3*n-1) + a(n/2).
For n=7, the a(7) = 2 ways are by the sole possible step 7 -> 20 since 7 is odd, followed by each of the a(20) = 2 ways shown above.
		

Links

• Kevin Ryde, Table of n, a(n) for n = 1..10000
• Kevin Ryde, C Code

Crossrefs

Cf. A261870.

Programs

C

/* See links. */