A127885 a(n) = minimal number of steps to get from n to 1, where a step is x -> 3x+1 if x is odd, or x -> either x/2 or 3x+1 if x is even; or -1 if 1 is never reached.

0, 1, 7, 2, 5, 8, 16, 3, 11, 6, 14, 9, 9, 17, 17, 4, 12, 12, 20, 7, 7, 15, 15, 10, 23, 10, 23, 10, 18, 18, 31, 5, 18, 13, 13, 13, 13, 21, 26, 8, 21, 8, 21, 16, 16, 16, 29, 11, 16, 16, 24, 11, 11, 24, 24, 11, 24, 19, 24, 19, 19, 32, 32, 6, 19, 19, 27, 14, 14, 14, 27, 14, 27, 14, 14, 22, 22, 27, 27, 9, 22, 22, 22, 9, 9, 22, 22, 17, 22, 17, 30, 17, 17, 30, 30, 12, 30, 17, 17, 17

Offset: 1

Author

David Applegate and N. J. A. Sloane, Feb 04 2007

Keywords

• nonn

Comments

In contrast to the "3x+1" problem (see A006577), here you are free to choose either step if x is even.

See A125731 for the number of steps in the reverse direction, from 1 to n.

Examples

			Several early values use the path:
6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.
The first path where choosing 3x+1 for even x helps is:
9 -> 28 -> 85 -> 256 -> 128 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1.
		

References

• M. J. Halm, Sequences (Re)discovered, Mpossibilities 81 (Aug. 2002), p. 1.

Links

• David Applegate, Table of n, a(n) for n = 1..1000
• Index entries for sequences related to 3x+1 (or Collatz) problem

Crossrefs

A127886 gives the difference between A006577 and this sequence.

Cf. A006577, A125731, A127887, A125195, A125686, A125719, A261870.

Cf. A290100 (size of the final set when using Alekseyev's algorithm).

Cf. also A257265.

Programs

Maple

# Code from David Applegate: Be careful - the function takes an iteration limit and returns the limit if it wasn't able to determine the answer (that is, if A127885(n,lim) == lim, all you know is that the value is >= lim). To use it, do manual iteration on the limit.
A127885 := proc(n,lim) local d,d2; options remember;
if (n = 1) then return 0; end if;
if (lim <= 0) then return 0; end if;
if (n > 2 ^ lim) then return lim; end if;
if (n mod 2 = 0) then
d := A127885(n/2,lim-1);
d2 := A127885(3*n+1,d);
if (d2 < d) then d := d2; end if;
else
d := A127885(3*n+1,lim-1);
end if;
return 1+d;
end proc;

Mathematica

Table[-1 + Length@ NestWhileList[Flatten[# /. {k_ /; OddQ@ k :> 3 k + 1, k_ /; EvenQ@ k :> {k/2, 3 k + 1}}] &, {n}, FreeQ[#, 1] &], {n, 126}] (* Michael De Vlieger, Aug 20 2017 *)

PARI

{ A127885(n) = my(S,k); S=[n]; k=0; while( S[1]!=1, k++; S=vecsort( concat(apply(x->3*x+1,S), apply(x->x\2, select(x->x%2==0,S) )),,8);  ); k } /* Max Alekseyev, Sep 03 2015 */

Formula

a(1) = 0; and for n > 1, if n is odd, a(n) = 1 + a(3n+1), and if n is even, a(n) = 1 + min(a(3n+1),a(n/2)). [But with a similar caveat as in A257265] - Antti Karttunen, Aug 20 2017

Extensions

Escape clause added to definition by N. J. A. Sloane, Aug 20 2017