login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006577 Number of halving and tripling steps to reach 1 in `3x+1' problem.
(Formerly M4323)
131
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

N. J. A. Sloane, Table of n, a(n) for n = 1..10000

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]

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

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 * A073652 A248285 A117029

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified June 25 21:01 EDT 2016. Contains 274199 sequences.