This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006370 The Collatz or 3x+1 map: a(n) = n/2 if n is even, 3n + 1 if n is odd.
(Formerly M3198)

%I M3198

%S 0,4,1,10,2,16,3,22,4,28,5,34,6,40,7,46,8,52,9,58,10,64,11,70,12,76,

%T 13,82,14,88,15,94,16,100,17,106,18,112,19,118,20,124,21,130,22,136,

%U 23,142,24,148,25,154,26,160,27,166,28,172,29,178,30,184,31,190,32,196,33

%N The Collatz or 3x+1 map: a(n) = n/2 if n is even, 3n + 1 if n is odd.

%C 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 an unsolved problem. It is conjectured that the answer is yes.

%C The Krasikov-Lagarias paper shows that at least N^0.84 of the positive numbers <N fall into the 4-2-1 cycle of the 3x+1 problem. This is far short of what we think is true, that all positive numbers fall into this cycle, but it is a step. - Richard C. Schroeppel, May 01 2002

%C Also A001477 and A016957 interleaved. - _Omar E. Pol_, Jan 16 2014, updated Nov 07 2017

%C a(n) is the image of a(2*n) under the 3*x+1 map. - _L. Edson Jeffery_, Aug 17 2014

%D R. K. Guy, Unsolved Problems in Number Theory, E16.

%D J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010.

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H T. D. Noe, <a href="/A006370/b006370.txt">Table of n, a(n) for n=0..1000</a>

%H Darrell Cox, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL15/Cox/cox10.html">The 3n + 1 Problem: A Probabilistic Approach</a>, Journal of Integer Sequences, Vol. 15 (2012), #12.5.2.

%H David Eisenbud and Brady Haran, <a href="https://www.youtube.com/watch?v=5mFpVDpKX70">UNCRACKABLE? The Collatz Conjecture</a>, Numberphile Video, 2016.

%H I. Krasikov and J. C. Lagarias, <a href="http://arXiv.org/abs/math.NT/0205002">Bounds for the 3x+1 Problem using Difference Inequalities</a>, arXiv:math/0205002 [math.NT], 2002.

%H J. C. Lagarias, <a href="http://www.cecm.sfu.ca/organics/papers/lagarias/paper/html/paper.html">The 3x+1 problem and its generalizations</a>, Amer. Math. Monthly, 92 (1985), 3-23.

%H J. C. Lagarias, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa56/aa5614.pdf">The set of rational cycles for the 3x+1 problem</a>, Acta Arithmetica, LVI (1990), pp. 33-53.

%H J. C. Lagarias, <a href="http://arxiv.org/abs/math.NT/0309224">The 3x+1 Problem: An Annotated Bibliography (1963-2000)</a>, arXiv:math/0309224 [math.NT], 2003-2011.

%H J. C. Lagarias, <a href="http://arxiv.org/abs/math/0608208">The 3x+1 Problem: an annotated bibliography, II (2000-2009)</a>, arXiv:math/0608208 [math.NT], 2006-2012.

%H E. Roosendaal, <a href="http://www.ericr.nl/wondrous/index.html">On the 3x+1 problem</a>

%H Simon Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/MasterThesis.pdf">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992.

%H Simon Plouffe, <a href="http://www.lacim.uqam.ca/%7Eplouffe/articles/FonctionsGeneratrices.pdf">1031 Generating Functions and Conjectures</a>, Université du Québec à Montréal, 1992.

%H S. Schreiber & N. J. A. Sloane, <a href="/A006368/a006368.pdf">Correspondence, 1980</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CollatzProblem.html">Collatz Problem</a>

%H Wikipedia, <a href="http://en.wikipedia.org/wiki/Collatz_conjecture">Collatz conjecture</a>

%H <a href="/index/3#3x1">Index entries for sequences related to 3x+1 (or Collatz) problem</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (0,2,0,-1).

%F G.f.: (4x+x^2+2x^3) / (1-x^2)^2.

%F a(n) = (1/4)(7n+2-(-1)^n(5n+2)). - _Benoit Cloitre_, May 12 2002

%F a(n) = ((n mod 2)*2 + 1)*n/(2 - (n mod 2)) + (n mod 2). - _Reinhard Zumkeller_, Sep 12 2002

%F a(n) = A014682(n+1) * A000034(n). - _R. J. Mathar_, Mar 09 2009

%F a(n) = a(a(2*n)) = -A001281(-n) for all n in Z. - _Michael Somos_, Nov 10 2016

%F E.g.f.: (2 + x)*sinh(x)/2 + 3*x*cosh(x). - _Ilya Gutkovskiy_, Dec 20 2016

%e G.f. = 4*x + x^2 + 10*x^3 + 2*x^4 + 16*x^5 + 3*x^6 + 22*x^7 + 4*x^8 + 28*x^9 + ...

%p f := n-> if n mod 2 = 0 then n/2 else 3*n+1; fi;

%p A006370:=(4+z+2*z**2)/(z-1)**2/(1+z)**2; # _Simon Plouffe_ in his 1992 dissertation; uses offset 0

%t f[n_]:=If[EvenQ[n],n/2,3n+1];Table[f[n],{n,50}] (* _Geoffrey Critzer_, Jun 29 2013 *)

%t LinearRecurrence[{0,2,0,-1},{4,1,10,2},70] (* _Harvey P. Dale_, Jul 19 2016 *)

%o (PARI) for(n=1,100,print1((1/4)*(7*n+2-(-1)^n*(5*n+2)),","))

%o (PARI) A006370(n)=if(n%2,3*n+1,n/2) \\ _Michael B. Porter_, May 29 2010

%o (Haskell)

%o a006370 n | m /= 0 = 3 * n + 1

%o | otherwise = n' where (n',m) = divMod n 2

%o -- _Reinhard Zumkeller_, Oct 07 2011

%o (Python)

%o def A006370(n):

%o ....q,r = divmod(n,2)

%o ....return 3*n+1 if r else q # _Chai Wah Wu_, Jan 04 2015

%o (MAGMA) [(1/4)*(7*n+2-(-1)^n*(5*n+2)): n in [1..70]]; // _Vincenzo Librandi_, Dec 20 2016

%Y Cf. A139391, A016945, A005408, A016825, A082286, A070165.

%Y A006577 gives number of steps to reach 1.

%Y Cf. A001281.

%K nonn,nice,easy

%O 0,2

%A _N. J. A. Sloane_

%E More terms from Larry Reeves (larryr(AT)acm.org), Apr 27 2001

%E Zero prepended and new Name from _N. J. A. Sloane_ at suggestion of _M. F. Hasler_, Nov 06 2017

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 22 11:00 EDT 2018. Contains 315270 sequences. (Running on oeis4.)