login
The Collatz or 3x+1 map: a(n) = n/2 if n is even, 3n + 1 if n is odd.
(Formerly M3198)
215

%I M3198 #236 Oct 13 2024 02:32:50

%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

%C The positions of powers of 2 in this sequence are given in A160967. - _Federico Provvedi_, Oct 06 2021

%C If displayed as a rectangular array with six columns, the columns are A008585, A350521, A016777, A082286, A016789, A350522 (see example). - _Omar E. Pol_, Jan 03 2022

%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="https://arxiv.org/abs/math/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="https://arxiv.org/abs/math/0309224">The 3x+1 Problem: An Annotated Bibliography (1963-2000)</a>, arXiv:math/0309224 [math.NT], 2003-2011.

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

%H Jeffrey C. Lagarias, <a href="https://arxiv.org/abs/2111.02635">The 3x+1 Problem: An Overview</a>, arXiv:2111.02635 [math.NT], 2021.

%H Simon Plouffe, <a href="https://arxiv.org/abs/0911.4975">Approximations de séries génératrices et quelques conjectures</a>, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.

%H Simon Plouffe, <a href="/A000051/a000051_2.pdf">1031 Generating Functions</a>, Appendix to Thesis, Montreal, 1992.

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

%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.: (4*x+x^2+2*x^3) / (1-x^2)^2.

%F a(n) = (1/4)*(7*n+2-(-1)^n*(5*n+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

%F From _Federico Provvedi_, Aug 17 2021: (Start)

%F Dirichlet g.f.: (1-2^(-s))*zeta(s) + (3-5*2^(-s))*zeta(s-1).

%F a(n) = ( a(n+2k) + a(n-2k) ) / 2, for every integer k. (End)

%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 + ...

%e From _Omar E. Pol_, Jan 03 2022: (Start)

%e Written as a rectangular array with six columns read by rows the sequence begins:

%e 0, 4, 1, 10, 2, 16;

%e 3, 22, 4, 28, 5, 34;

%e 6, 40, 7, 46, 8, 52;

%e 9, 58, 10, 64, 11, 70;

%e 12, 76, 13, 82, 14, 88;

%e 15, 94, 16, 100, 17, 106;

%e 18, 112, 19, 118, 20, 124;

%e 21, 130, 22, 136, 23, 142;

%e 24, 148, 25, 154, 26, 160;

%e 27, 166, 28, 172, 29, 178;

%e 30, 184, 31, 190, 32, 196;

%e ...

%e (End)

%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.

%Y Column k=1 of A347270, n >= 1.

%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 the suggestion of _M. F. Hasler_, Nov 06 2017