|
%I M3198 #228 Mar 22 2024 18:50:10
%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
|
