|
| |
|
|
A014682
|
|
The Collatz or 3x+1 function: a(n) = n/2 if n is even, otherwise (3n+1)/2.
|
|
119
|
|
|
|
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.
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
|
|
|
REFERENCES
|
J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010.
|
|
|
LINKS
|
|
|
|
FORMULA
|
G.f.: x*(2 + x + x^2)/(1-x^2)^2.
a(n) = (4*n+1)/4 - (2*n+1)*(-1)^n/4. (End)
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) = 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
a(n) = A064455(n+1) - 1, relating the number ON cells in row n of cellular automaton rule 54.
(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) = 2*a(n-2) - a(n-4) for n > 3. - Chai Wah Wu, Apr 17 2024
|
|
|
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)[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 *)
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
(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
(Magma) [IsOdd(n) select (3*n+1)/2 else n/2: n in [0..52]]; // Vincenzo Librandi, Sep 28 2018
|
|
|
CROSSREFS
|
Cf. A002378, A004526, A076936, A139391, A016116, A126241, A060412, A060413, A006370, A070168 (iterations), A005408, A016957, A064455, A153285, A008619, A193356.
|
|
|
KEYWORD
|
nonn,easy
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
