A071045 -id:A071045 - cp's OEIS frontend

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

Mohammad K. Azarian

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

			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

J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010.

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

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

a014682 n = if r > 0 then div (3 * n + 1) 2 else n'
            where (n', r) = divMod n 2
-- Reinhard Zumkeller, Oct 03 2014

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

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

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

a(n)=if(n%2,3*n+1,n)/2 \\ Charles R Greathouse IV, Sep 02 2015

a(n)=if(n<2,2*n,(n^2-n-1)%(2*n+1)) \\ Jim Singh, Sep 28 2018

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

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

Edited by N. J. A. Sloane, Apr 26 2008, at the suggestion of Artur Jasinski

Edited by N. J. A. Sloane, Jan 31 2011

A123684 Alternate A016777(n) with A000027(n).

Original entry on oeis.org

1, 1, 4, 2, 7, 3, 10, 4, 13, 5, 16, 6, 19, 7, 22, 8, 25, 9, 28, 10, 31, 11, 34, 12, 37, 13, 40, 14, 43, 15, 46, 16, 49, 17, 52, 18, 55, 19, 58, 20, 61, 21, 64, 22, 67, 23, 70, 24, 73, 25, 76, 26, 79, 27, 82, 28, 85, 29, 88, 30, 91, 31, 94, 32, 97, 33, 100, 34, 103, 35, 106, 36

Offset: 1

Alford Arnold, Oct 11 2006

a(n) is a diagonal of Table A123685.
The arithmetic average of the first n terms gives the positive integers repeated (A008619). - Philippe Deléham, Nov 20 2013
Images under the modified '3x-1' map: a(n) = n/2 if n is even, (3n-1)/2 if n is odd. (In this sequence, the numbers at even indices n are n/2 [A000027], and the numbers at odd indices n are 3((n-1)/2) + 1 [A016777] = (3n-1)/2.) The latter correspondence interestingly mirrors an insight in David Bařina's 2020 paper (see below), namely that 3(n+1)/2 - 1 = (3n+1)/2. - Kevin Ge, Oct 30 2024

			The natural numbers begin 1, 2, 3, ... (A000027), the sequence 3*n + 1 begins 1, 4, 7, 10, ... (A016777), therefore A123684 begins 1, 1, 4, 2, 7, 3, 10, ...
1/1 = 1, (1+1)/2 = 1, (1+1+4)/3 = 2, (1+1+4+2)/4 = 2, ... - _Philippe Deléham_, Nov 20 2013

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Index entries for linear recurrences with constant coefficients, signature (0,2,0,-1).
David Bařina, Convergence verification of the Collatz problem

Cf. A000027, A008619, A016777, A016825, A031878, A052928, A064455.
Cf. A071045, A092530, A093005, A105638, A123685, A137501, A225126.
Cf. A014682 (modified Collatz map)

import Data.List (transpose)
a123684 n = a123684_list !! (n-1)
a123684_list = concat $ transpose [a016777_list, a000027_list]
-- Reinhard Zumkeller, Apr 29 2013

&cat[ [ 3*n-2, n ]: n in [1..36] ]; // Klaus Brockhaus, May 12 2007

/* From the fourteenth formula: */ [&+[1+k*(-1)^k: k in [0..n]]: n in [0..80]]; // Bruno Berselli, Jul 16 2013

A123684:=n->n-1/4-(1/2*n-1/4)*(-1)^n: seq(A123684(n), n=1..70); # Wesley Ivan Hurt, Jul 26 2014

CoefficientList[Series[(1 +x +2*x^2)/((1-x)^2*(1+x)^2), {x,0,70}], x] (* Wesley Ivan Hurt, Jul 26 2014 *)
LinearRecurrence[{0,2,0,-1},{1,1,4,2},80] (* Harvey P. Dale, Apr 14 2025 *)

print(vector(72, n, if(n%2==0, n/2, (3*n-1)/2))) \\ Klaus Brockhaus, May 12 2007

print(vector(72, n, n-1/4-(1/2*n-1/4)*(-1)^n)); \\ Klaus Brockhaus, May 12 2007

[(n + (2*n-1)*(n%2))//2 for n in range(1,71)] # G. C. Greubel, Mar 15 2024

From Klaus Brockhaus, May 12 2007: (Start)
G.f.: x*(1+x+2*x^2)/((1-x)^2*(1+x)^2).
a(n) = (1/4)*(4*n - 1 - (2*n - 1)*(-1)^n).
a(2n-1) = A016777(n-1) = 3(n-1) + 1.
a(2n) = A000027(n) = n.
a(n) = A071045(n-1) + 1.
a(n) = A093005(n) - A093005(n-1) for n > 1.
a(n) = A105638(n+2) - A105638(n+1) for n > 1.
a(n) = A092530(n) - A092530(n-1) - 1.
a(n) = A031878(n+1) - A031878(n) - 1. (End)
a(2*n+1) + a(2*n+2) = A016825(n). - Paul Curtz, Mar 09 2011
a(n)= 2*a(n-2) - a(n-4). - Paul Curtz, Mar 09 2011
From Jaroslav Krizek, Mar 22 2011 (Start):
a(n) = n + a(n-1) for odd n; a(n) = n - A064455(n-1) for even n.
a(n) = A064455(n) - A137501(n).
Abs(a(n) - A064455(n)) = A052928(n). (End)
a(n) = A225126(n) for n > 1. - Reinhard Zumkeller, Apr 29 2013
a(n) = Sum_{k=1..n} (1 + (k-1)*(-1)^(k-1)). - Bruno Berselli, Jul 16 2013
a(n) = n + floor(n/2) for odd n; a(n) = n/2 for even n. - Reinhard Muehlfeld, Jul 25 2014

More terms from Klaus Brockhaus, May 12 2007

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A123684 Alternate A016777(n) with A000027(n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Magma

Magma

Maple

Mathematica

PARI

PARI

SageMath

Formula

Extensions