|
%I #9 Dec 24 2014 19:59:51
%S 0,2,-1,1,6,-1,3,8,-1,5,5,-1,2,15,-1,7,7,-1,12,4,-1,4,9,-1,9,9,-1,14,
%T 14,-1,6,19,-1,6,11,-1,11,11,-1,3,29,-1,16,16,-1,8,8,-1,8,21,-1,8,13,
%U -1,26,13,-1,13,13,-1,5,31,-1,18,18,-1,5,23,-1,10
%N a(n) = minimal number of steps to get from 1 to n, where a step is x -> 3x+1 if x is odd, or x -> either x/2 or 3x+1 if x is even. Set a(n) = -1 if n cannot be reached from 1.
%C In contrast to the "3x+1" problem, here you are free to choose either step if x is even.
%C Clearly a(3k) = -1 for all k; we conjecture that a(n) >= 0 otherwise.
%C See A127885 for the number of steps in the reverse direction, from n to 1.
%H David Applegate, <a href="/A125731/b125731.txt">Table of n, a(n) for n = 1..1000</a>
%e The initial values use these paths:
%e 1 -> 4 -> 2 -> 7 -> 22 -> 11.
%e 1 -> 4 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8.
%e 1 -> 4 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 49 -> 148 -> 74 -> 37 -> 12 -> 56 -> 28 -> 14.
%p # 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 A125731(n,lim) == lim, all you know is that the value is >= lim). To use it, do manual iteration on the limit.
%p A125731 := proc(n,lim) local d,d2; options remember;
%p if (n = 1) then return 0; end if;
%p if (n mod 3 = 0) then return -1; end if;
%p if (lim <= 0) then return 0; end if;
%p if (n > (3 ** (lim+1) - 1)/2) then return lim; end if;
%p if (n mod 9 = 4 or n mod 9 = 7) then
%p d := A125731((n-1)/3,lim-1);
%p d2 := A125731(2*n,d);
%p if (d2 < d) then d := d2; end if;
%p else
%p d := A125731(2*n,lim-1);
%p end if;
%p return 1+d;
%p end proc;
%K sign
%O 1,2
%A _David Applegate_ and _N. J. A. Sloane_, Feb 02 2007
|
