The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 56th year, we are closing in on 350,000 sequences, and we’ve crossed 9,700 citations (which often say “discovered thanks to the OEIS”). Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A014682 The Collatz or 3x+1 function: a(n) = n/2 if n is even, otherwise (3n+1)/2. 93
 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, 41, 14, 44, 15, 47, 16, 50, 17, 53, 18, 56, 19, 59, 20, 62, 21, 65, 22, 68, 23, 71, 24, 74, 25, 77, 26, 80, 27, 83, 28, 86, 29, 89, 30, 92, 31, 95, 32, 98, 33, 101, 34, 104 (list; graph; refs; listen; history; text; internal format)
 OFFSET 0,2 COMMENTS This is the function usually denoted by T(n) in the literature on the 3x+1 problem. See A006370 for further references and links. Intertwining of sequence A016789 '2,5,8,11,... ("add 3")' and the nonnegative integers. a(n) = log_2(A076936(n)). - Amarnath Murthy, Oct 19 2002 The average value of a(0), ..., a(n-1) is A004526(n). - Amarnath Murthy, Oct 19 2002 Partial sums are A093353. - Paul Barry, Mar 31 2008 Absolute first differences are essentially in A014681 and A103889. - R. J. Mathar, Apr 05 2008 The Monks article claims to "determine the structure of the groups generated by the maps x maps to x/2 and x maps to (3x+1)/2 modulo b for b relatively prime to 6, and study the action of these groups on the directed graph associated to the 3x+1 dynamical system." - Jonathan Vos Post, Apr 18 2012 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 REFERENCES J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010. LINKS N. J. A. Sloane (terms 0..1000) & Antti Karttunen, Table of n, a(n) for n = 0..100000 C. J. Everett, Iteration of the number-theoretic function f(2n) = n, f(2n + 1) = 3n + 2, Advances in Mathematics, Volume 25, Issue 1, July 1977, Pages 42-45. Jeffrey C. Lagarias, The 3x+1 Problem: An Overview, arXiv:2111.02635 [math.NT], 2021. Keenan Monks, Kenneth G. Monks, Kenneth M. Monks, and Maria Monks, Strongly sufficient sets and the distribution of arithmetic sequences in the 3x+1 graph, arXiv:1204.3904v1 [math.DS], Apr 17 2012. R. Terras, A stopping time problem on the positive integers, Acta Arith. 30 (1976) 241-252. Eric Weisstein's World of Mathematics, Collatz Problem Wikipedia, Collatz conjecture Index entries for linear recurrences with constant coefficients, signature (0,2,0,-1). FORMULA From Paul Barry, Mar 31 2008: (Start) G.f.: x*(2 + x + x^2)/(1-x^2)^2. a(n) = (4*n+1)/4 - (2*n+1)*(-1)^n/4. (End) a(n) = -a(n-1) + a(n-2) + a(n-3) + 4. - John W. Layman 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 O.g.f.: x*(2+x+x^2)/((-1+x)^2*(1+x)^2). - R. J. Mathar, Apr 05 2008 a(n) = 5/4 + (1/2)*((-1)^n)*n + (3/4)*(-1)^n + n. - Alexander R. Povolotsky, Apr 05 2008 a(n) = Sum_{i=-n..2*n} i*(-1)^i. - Bruno Berselli, Dec 14 2015 a(n) = Sum_{k=0..n-1} Sum_{i=0..k} C(i,k) + (-1)^k. - Wesley Ivan Hurt, Sep 20 2017 a(n) = (n^2-n-1) mod (2*n+1) for n > 1. - Jim Singh, Sep 26 2018 Binary: a(n) = (n shift left (n AND 1)) - (n shift right 1) = A109043(n) - A004526(n). - Rudi B. Stranden, Jun 15 2021 EXAMPLE 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 MAPLE 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 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) ; 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(A076936(n)) ; end: for n from 1 to 85 do printf("%d, ", A014682(n)) ; od ; # R. J. Mathar, Mar 20 2007 MATHEMATICA Collatz[n_?OddQ] := (3n + 1)/2; Collatz[n_?EvenQ] := n/2; Table[Collatz[n], {n, 0, 79}] (* Alonso del Arte, Apr 21 2011 *) LinearRecurrence[{0, 2, 0, -1}, {0, 2, 1, 5}, 70] (* Jean-François Alcover, Sep 23 2017 *) Table[If[OddQ[n], (3 n + 1) / 2, n / 2], {n, 0, 60}] (* Vincenzo Librandi, Sep 28 2018 *) PROG (Haskell) a014682 n = if r > 0 then div (3 * n + 1) 2 else n'             where (n', r) = divMod n 2 -- Reinhard Zumkeller, Oct 03 2014 (PARI) a(n)=if(n%2, 3*n+1, n)/2 \\ Charles R Greathouse IV, Sep 02 2015 (PARI) a(n)=if(n<2, 2*n, (n^2-n-1)%(2*n+1)) \\ Jim Singh, Sep 28 2018 (Python) def a(n): return n//2 if n%2==0 else (3*n + 1)//2 print([a(n) for n in range(101)]) # Indranil Ghosh, Jul 29 2017 (MAGMA) [IsOdd(n) select (3*n+1)/2 else n/2: n in [0..52]]; // Vincenzo Librandi, Sep 28 2018 CROSSREFS Cf. A004526, A076936, A139391, A016116, A126241, A060412, A060413, A006370, A070168 (iterations), A005408, A016957, A064455, A153285. Bisections: A001477, A016789. Sequence in context: A185727 A070951 A076937 * A167160 A111361 A257971 Adjacent sequences:  A014679 A014680 A014681 * A014683 A014684 A014685 KEYWORD nonn,easy AUTHOR EXTENSIONS Edited by N. J. A. Sloane, Apr 26 2008, at the suggestion of Artur Jasinski Edited by N. J. A. Sloane, Jan 31 2011 STATUS approved

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

Last modified December 7 13:08 EST 2021. Contains 349581 sequences. (Running on oeis4.)