A014682 The Collatz or 3x+1 function: a(n) = n/2 if n is even, otherwise (3n+1)/2.

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

Offset: 0

Author

Mohammad K. Azarian

Keywords

• nonn
• easy

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

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

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

Examples

			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
		

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 sequences related to 3x+1 (or Collatz) problem
• Index entries for linear recurrences with constant coefficients, signature (0,2,0,-1).

Crossrefs

Cf. A002378, A004526, A076936, A139391, A016116, A126241, A060412, A060413, A006370, A070168 (iterations), A005408, A016957, A064455, A153285, A008619, A193356.

Bisections: A001477, A016789.

Cf. A093353.

Programs

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

Magma

[IsOdd(n) select (3*n+1)/2 else n/2: n in [0..52]]; // Vincenzo Librandi, Sep 28 2018

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)[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

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 *)

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

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

The above formula can be rewritten to show a pattern: a(n) = (n*(n+1)) mod (n+(n+1)). - Peter Munn, Jan 29 2022

Binary: a(n) = (n shift left (n AND 1)) - (n shift right 1) = A109043(n) - A004526(n). - Rudi B. Stranden, Jun 15 2021

From Rudi B. Stranden, Mar 21 2022: (Start)

a(n) = A064455(n+1) - 1, relating the number ON cells in row n of cellular automaton rule 54.

a(n) = 2*n - A071045(n).

(End)

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

a(n) = n*(n mod 2) + ceiling(n/2) = A193356(n) + A008619(n+1). - Jonathan Shadrach Gilbert, Mar 12 2023

a(n) = 2*a(n-2) - a(n-4) for n > 3. - Chai Wah Wu, Apr 17 2024

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