%I #211 Apr 17 2024 15:18:12
%S 0,2,1,5,2,8,3,11,4,14,5,17,6,20,7,23,8,26,9,29,10,32,11,35,12,38,13,
%T 41,14,44,15,47,16,50,17,53,18,56,19,59,20,62,21,65,22,68,23,71,24,74,
%U 25,77,26,80,27,83,28,86,29,89,30,92,31,95,32,98,33,101,34,104
%N The Collatz or 3x+1 function: a(n) = n/2 if n is even, otherwise (3n+1)/2.
%C This is the function usually denoted by T(n) in the literature on the 3x+1 problem. See A006370 for further references and links.
%C Intertwining of sequence A016789 '2,5,8,11,... ("add 3")' and the nonnegative integers.
%C a(n) = log_2(A076936(n)). - _Amarnath Murthy_, Oct 19 2002
%C The average value of a(0), ..., a(n-1) is A004526(n). - _Amarnath Murthy_, Oct 19 2002
%C Partial sums are A093353. - _Paul Barry_, Mar 31 2008
%C Absolute first differences are essentially in A014681 and A103889. - _R. J. Mathar_, Apr 05 2008
%C Only terms of A016789 occur twice, at positions given by sequences A005408 (odd numbers) and A016957 (6n+4): (1,4), (3,10), (5,16), (7,22), ... - _Antti Karttunen_, Jul 28 2017
%C a(n) represents the unique congruence class modulo 2n+1 that is represented an odd number of times in any 2n+1 consecutive oblong numbers (A002378). This property relates to _Jim Singh_'s 2018 formula, as n^2 + n is a relevant oblong number. - _Peter Munn_, Jan 29 2022
%D J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010.
%H N. J. A. Sloane (terms 0..1000) & Antti Karttunen, <a href="/A014682/b014682.txt">Table of n, a(n) for n = 0..100000</a>
%H C. J. Everett, <a href="http://dx.doi.org/10.1016/0001-8708(77)90087-1">Iteration of the number-theoretic function f(2n) = n, f(2n + 1) = 3n + 2</a>, Advances in Mathematics, Volume 25, Issue 1, July 1977, Pages 42-45.
%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 Keenan Monks, Kenneth G. Monks, Kenneth M. Monks, and Maria Monks, <a href="http://arxiv.org/abs/1204.3904">Strongly sufficient sets and the distribution of arithmetic sequences in the 3x+1 graph</a>, arXiv:1204.3904v1 [math.DS], Apr 17 2012.
%H R. Terras, <a href="http://matwbn.icm.edu.pl/ksiazki/aa/aa30/aa3034.pdf">A stopping time problem on the positive integers</a>, Acta Arith. 30 (1976) 241-252.
%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 From _Paul Barry_, Mar 31 2008: (Start)
%F G.f.: x*(2 + x + x^2)/(1-x^2)^2.
%F a(n) = (4*n+1)/4 - (2*n+1)*(-1)^n/4. (End)
%F a(n) = -a(n-1) + a(n-2) + a(n-3) + 4. - _John W. Layman_
%F For n > 1 this is the image of n under the modified "3x+1" map (cf. A006370): n -> n/2 if n is even, n -> (3*n+1)/2 if n is odd. - _Benoit Cloitre_, May 12 2002
%F O.g.f.: x*(2+x+x^2)/((-1+x)^2*(1+x)^2). - _R. J. Mathar_, Apr 05 2008
%F a(n) = 5/4 + (1/2)*((-1)^n)*n + (3/4)*(-1)^n + n. - _Alexander R. Povolotsky_, Apr 05 2008
%F a(n) = Sum_{i=-n..2*n} i*(-1)^i. - _Bruno Berselli_, Dec 14 2015
%F a(n) = Sum_{k=0..n-1} Sum_{i=0..k} C(i,k) + (-1)^k. - _Wesley Ivan Hurt_, Sep 20 2017
%F a(n) = (n^2-n-1) mod (2*n+1) for n > 1. - _Jim Singh_, Sep 26 2018
%F The above formula can be rewritten to show a pattern: a(n) = (n*(n+1)) mod (n+(n+1)). - _Peter Munn_, Jan 29 2022
%F Binary: a(n) = (n shift left (n AND 1)) - (n shift right 1) = A109043(n) - A004526(n). - _Rudi B. Stranden_, Jun 15 2021
%F From _Rudi B. Stranden_, Mar 21 2022: (Start)
%F a(n) = A064455(n+1) - 1, relating the number ON cells in row n of cellular automaton rule 54.
%F a(n) = 2*n - A071045(n).
%F (End)
%F E.g.f.: (1 + x)*sinh(x)/2 + 3*x*cosh(x)/2 = ((4*x+1)*e^x + (2*x-1)*e^(-x))/4. - _Rénald Simonetto_, Oct 20 2022
%F a(n) = n*(n mod 2) + ceiling(n/2) = A193356(n) + A008619(n+1). - _Jonathan Shadrach Gilbert_, Mar 12 2023
%F a(n) = 2*a(n-2) - a(n-4) for n > 3. - _Chai Wah Wu_, Apr 17 2024
%e a(3) = -3*(-1) - 2*1 - 1*(-1) - 0*1 + 1*(-1) + 2*1 + 3*(-1) + 4*1 + 5*(-1) + 6*1 = 5. - _Bruno Berselli_, Dec 14 2015
%p T:=proc(n) if n mod 2 = 0 then n/2 else (3*n+1)/2; fi; end; # _N. J. A. Sloane_, Jan 31 2011
%p A076936 := proc(n) option remember ; local apr,ifr,me,i,a ; if n <=2 then n^2 ; else apr := mul(A076936(i),i=1..n-1) ; ifr := ifactors(apr)[2] ; me := -1 ; for i from 1 to nops(ifr) do me := max(me, op(2,op(i,ifr))) ; od ; me := me+ n-(me mod n) ; a := 1 ; for i from 1 to nops(ifr) do a := a*op(1,op(i,ifr))^(me-op(2,op(i,ifr))) ; od ; if a = A076936(n-1) then me := me+n ; a := 1 ; for i from 1 to nops(ifr) do a := a*op(1,op(i,ifr))^(me-op(2,op(i,ifr))) ; od ; fi ; RETURN(a) ; fi ; end: A014682 := proc(n) log[2](A076936(n)) ; end: for n from 1 to 85 do printf("%d, ",A014682(n)) ; od ; # _R. J. Mathar_, Mar 20 2007
%t Collatz[n_?OddQ] := (3n + 1)/2; Collatz[n_?EvenQ] := n/2; Table[Collatz[n], {n, 0, 79}] (* _Alonso del Arte_, Apr 21 2011 *)
%t LinearRecurrence[{0, 2, 0, -1}, {0, 2, 1, 5}, 70] (* _Jean-François Alcover_, Sep 23 2017 *)
%t Table[If[OddQ[n], (3 n + 1) / 2, n / 2], {n, 0, 60}] (* _Vincenzo Librandi_, Sep 28 2018 *)
%o (Haskell)
%o a014682 n = if r > 0 then div (3 * n + 1) 2 else n'
%o where (n', r) = divMod n 2
%o -- _Reinhard Zumkeller_, Oct 03 2014
%o (PARI) a(n)=if(n%2,3*n+1,n)/2 \\ _Charles R Greathouse IV_, Sep 02 2015
%o (PARI) a(n)=if(n<2,2*n,(n^2-n-1)%(2*n+1)) \\ _Jim Singh_, Sep 28 2018
%o (Python)
%o def a(n): return n//2 if n%2==0 else (3*n + 1)//2
%o print([a(n) for n in range(101)]) # _Indranil Ghosh_, Jul 29 2017
%o (Magma) [IsOdd(n) select (3*n+1)/2 else n/2: n in [0..52]]; // _Vincenzo Librandi_, Sep 28 2018
%Y Cf. A002378, A004526, A076936, A139391, A016116, A126241, A060412, A060413, A006370, A070168 (iterations), A005408, A016957, A064455, A153285, A008619, A193356.
%Y Bisections: A001477, A016789.
%K nonn,easy
%O 0,2
%A _Mohammad K. Azarian_
%E Edited by _N. J. A. Sloane_, Apr 26 2008, at the suggestion of _Artur Jasinski_
%E Edited by _N. J. A. Sloane_, Jan 31 2011