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

%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