cp's OEIS Frontend

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.

%I A127885 #27 Aug 20 2017 10:58:19
%S A127885 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,
%T A127885 10,18,18,31,5,18,13,13,13,13,21,26,8,21,8,21,16,16,16,29,11,16,16,24,
%U A127885 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
%N 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.
%C A127885 In contrast to the "3x+1" problem (see A006577), here you are free to choose either step if x is even.
%C A127885 See A125731 for the number of steps in the reverse direction, from 1 to n.
%D A127885 M. J. Halm, Sequences (Re)discovered, Mpossibilities 81 (Aug. 2002), p. 1.
%H A127885 David Applegate, <a href="/A127885/b127885.txt">Table of n, a(n) for n = 1..1000</a>
%H A127885 <a href="/index/3#3x1">Index entries for sequences related to 3x+1 (or Collatz) problem</a>
%F A127885 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
%e A127885 Several early values use the path:
%e A127885 6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.
%e A127885 The first path where choosing 3x+1 for even x helps is:
%e A127885 9 -> 28 -> 85 -> 256 -> 128 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1.
%p A127885 # 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.
%p A127885 A127885 := proc(n,lim) local d,d2; options remember;
%p A127885 if (n = 1) then return 0; end if;
%p A127885 if (lim <= 0) then return 0; end if;
%p A127885 if (n > 2 ^ lim) then return lim; end if;
%p A127885 if (n mod 2 = 0) then
%p A127885 d := A127885(n/2,lim-1);
%p A127885 d2 := A127885(3*n+1,d);
%p A127885 if (d2 < d) then d := d2; end if;
%p A127885 else
%p A127885 d := A127885(3*n+1,lim-1);
%p A127885 end if;
%p A127885 return 1+d;
%p A127885 end proc;
%t A127885 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 *)
%o A127885 (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 */
%Y A127885 A127886 gives the difference between A006577 and this sequence.
%Y A127885 Cf. A006577, A125731, A127887, A125195, A125686, A125719, A261870.
%Y A127885 Cf. A290100 (size of the final set when using Alekseyev's algorithm).
%Y A127885 Cf. also A257265.
%K A127885 nonn
%O A127885 1,3
%A A127885 _David Applegate_ and _N. J. A. Sloane_, Feb 04 2007
%E A127885 Escape clause added to definition by _N. J. A. Sloane_, Aug 20 2017