|
| |
|
|
A006577
|
|
Number of halving and tripling steps to reach 1 in `3x+1' problem, or -1 if 1 is never reached.
(Formerly M4323)
|
|
149
|
|
|
|
0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20, 7, 7, 15, 15, 10, 23, 10, 111, 18, 18, 18, 106, 5, 26, 13, 13, 21, 21, 21, 34, 8, 109, 8, 29, 16, 16, 16, 104, 11, 24, 24, 24, 11, 11, 112, 112, 19, 32, 19, 32, 19, 19, 107, 107, 6, 27, 27, 27, 14, 14, 14, 102, 22
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,3
|
|
|
COMMENTS
|
The 3x+1 or Collatz problem is as follows: start with any number n. If n is even, divide it by 2, otherwise multiply it by 3 and add 1. Do we always reach 1? This is a famous unsolved problem. It is conjectured that the answer is yes.
It seems that about half of the terms satisfy a(i) = a(i+1). For example, up to 10000000, 4964705 terms satisfy this condition.
n is an element of row a(n) in triangle A127824. - Reinhard Zumkeller, Oct 03 2012
|
|
|
REFERENCES
|
R. K. Guy, Unsolved Problems in Number Theory, E16.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
|
|
|
LINKS
|
William Boyles, Table of n, a(n) for n = 1..100000, terms 1..10000 from N. J. A. Sloane
Geometry.net, Links on Collatz Problem
Jason Holt, Log-log plot of first billion terms
Jason Holt, Plot of 1 billion values of the number of steps to drop below n (A060445), log scale on x axis
Jason Holt, Plot of 10 billion values of the number of steps to drop below n (A060445), log scale on x axis
A. Krowne, PlanetMath.org, Collatz problem
J. C. Lagarias, The 3x+1 problem and its generalizations, Amer. Math. Monthly, 92 (1985), 3-23.
J. C. Lagarias, How random are 3x+1 function iterates?, in The Mathemagician and the Pied Puzzler - A Collection in Tribute to Martin Gardner, Ed. E. R. Berlekamp and T. Rogers, A. K. Peters, 1999, pp. 253-266.
J. C. Lagarias, The 3x+1 Problem: an annotated bibliography, II (2000-2009), arXiv:0608208 [math.NT], 2006-2012.
J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010.
Mathematical BBS, Biblography on Collatz Sequence
P. Picart, Algorithme de Collatz et conjecture de Syracuse
E. Roosendaal, On the 3x+1 problem
J. L. Simons, On the nonexistence of 2-cycles for the 3x+1 problem, Math. Comp. 75 (2005), 1565-1572.
G. Villemin's Almanach of Numbers, Cycle of Syracuse
Eric Weisstein's World of Mathematics, Collatz Problem
Wikipedia, Collatz Conjecture
Index entries for sequences related to 3x+1 (or Collatz) problem
|
|
|
FORMULA
|
a(n) = A006666(n) + A006667(n).
a(n) = A112695(n) + 2 for n > 2. - Reinhard Zumkeller, Apr 18 2008
a(n) = A008908(n) - 1. - L. Edson Jeffery, Jul 21 2014
|
|
|
EXAMPLE
|
a(5)=5 because the trajectory of 5 is (5,16,8,4,2,1).
|
|
|
MAPLE
|
A006577 := proc(n)
local a, traj ;
a := 0 ;
traj := n ;
while traj > 1 do
if type(traj, 'even') then
traj := traj/2 ;
else
traj := 3*traj+1 ;
end if;
a := a+1 ;
end do:
return a;
end proc: # R. J. Mathar, Jul 08 2012
|
|
|
MATHEMATICA
|
f[n_] := Module[{a=n, k=0}, While[a!=1, k++; If[EvenQ[a], a=a/2, a=a*3+1]]; k]; Table[f[n], {n, 4!}] (* Vladimir Joseph Stephan Orlovsky, Jan 08 2011 *)
Table[Length[NestWhileList[If[EvenQ[#], #/2, 3#+1]&, n, #!=1&]]-1, {n, 80}] (* Harvey P. Dale, May 21 2012 *)
|
|
|
PROG
|
(PARI) a(n)=if(n<0, 0, s=n; c=0; while(s>1, s=if(s%2, 3*s+1, s/2); c++); c)
(PARI) step(n)=if(n%2, 3*n+1, n/2);
A006577(n)=if(n==1, 0, A006577(step(n))+1); \\ Michael B. Porter, Jun 05 2010
(Haskell)
import Data.List (findIndex)
import Data.Maybe (fromJust)
a006577 n = fromJust $ findIndex (n `elem`) a127824_tabf
-- Reinhard Zumkeller, Oct 04 2012, Aug 30 2012
(Python)
def a(n):
if n==1: return 0
x=0
while True:
if n%2==0: n/=2
else: n = 3*n + 1
x+=1
if n<2: break
return x
print [a(n) for n in xrange(1, 101)] # Indranil Ghosh, Jun 05 2017
|
|
|
CROSSREFS
|
See A070165 for triangle giving trajectories of n = 1, 2, 3, ....
Cf. A125731, A127885, A127886, A008908, A112695.
A008884, A161021 ,A161022, A161023. - Reinhard Zumkeller, Jun 03 2009
Cf. A006370.
Sequence in context: A200237 A072761 A127885 * A280234 A073652 A277848
Adjacent sequences: A006574 A006575 A006576 * A006578 A006579 A006580
|
|
|
KEYWORD
|
nonn,nice,easy,hear,look
|
|
|
AUTHOR
|
N. J. A. Sloane, Bill Gosper
|
|
|
EXTENSIONS
|
More terms from Larry Reeves (larryr(AT)acm.org), Apr 27 2001
"Escape clause" added to definition by N. J. A. Sloane, Jun 06 2017
|
|
|
STATUS
|
approved
|
| |
|
|
