A060413 -id:A060413 - 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

A060412 In the '3x+1' problem, these values for the starting value set new records for the "dropping time", number of steps to reach a lower value than the start.

Original entry on oeis.org

2, 3, 7, 27, 703, 10087, 35655, 270271, 362343, 381727, 626331, 1027431, 1126015, 8088063, 13421671, 20638335, 26716671, 56924955, 63728127, 217740015, 1200991791, 1827397567, 2788008987, 12235060455

Offset: 1

N. J. A. Sloane, Apr 06 2001; b-file added Nov 27 2007

nonn

The (3x+1)/2 steps and the halving steps are counted. - Don Reble, May 13 2006

Where records occur in A102419 (could be prefixed by an initial 1). - N. J. A. Sloane, Oct 20 2012

			See A102419.

N. J. A. Sloane, Table of n, a(n) for n = 1..35 (from the web page of Tomás Oliveira e Silva)
Tomás Oliveira e Silva, Tables
Eric Roosendaal, On the 3x + 1 problem
N. J. A. Sloane, First 36 terms of A217934 and A060412 [From Roosendaal web site]
Index entries for sequences related to 3x+1 (or Collatz) problem

A060413 gives associated "dropping times", A060414 the maximal values and A060415 the steps at which the maxima occur. See also A217934.

Cf. A060445, A008884, A161021, A161022, A161023, A014682, A126241.

dcoll[n_]:=Length[NestWhileList[If[EvenQ[#],#/2,3#+1]&,n,#>=n&]]; t={max=2}; Do[If[(y=dcoll[n])>max,max=y; AppendTo[t,n]],{n,3,1130000,4}]; t (* Jayanta Basu, May 28 2013 *)

A126241 Dropping times in the 3n+1 problem (or the Collatz problem). Let T(n):=n/2 if n is even, (3n+1)/2 otherwise (A014682). Let a(n) be the smallest integer k such that T^(k)(n)

Original entry on oeis.org

0, 1, 4, 1, 2, 1, 7, 1, 2, 1, 5, 1, 2, 1, 7, 1, 2, 1, 4, 1, 2, 1, 5, 1, 2, 1, 59, 1, 2, 1, 56, 1, 2, 1, 4, 1, 2, 1, 8, 1, 2, 1, 5, 1, 2, 1, 54, 1, 2, 1, 4, 1, 2, 1, 5, 1, 2, 1, 7, 1, 2, 1, 54, 1, 2, 1, 4, 1, 2, 1, 51, 1, 2, 1, 5, 1, 2, 1, 8, 1, 2, 1, 4, 1, 2, 1, 5, 1, 2, 1, 45, 1, 2, 1, 8, 1, 2, 1, 4

Offset: 1

Christof Menzel (christof.menzel(AT)hs-niederrhein.de), Mar 08 2007

nonn

Also called "stopping times", although that term is usually reserved for A006666.
From K. Spage, Oct 22 2009, corrected Aug 21 2014: (Start)
Congruency relationship: For n>1 and m>1, all m congruent to n mod 2^(a(n)) have a dropping time equal to a(n).
By refining the definition of the dropping time to "starting with x=n, iterate x until (abs(x) <= abs(n))" the above congruency relationship holds for all nonnegative values of n and all positive or negative values of m including zero.
By this refined definition, a(1)=2 rather than the usual zero set by convention. All other values of positive a(n) remain unchanged. (End)
Terras defines a coefficient stopping time (definition 1.5) tau(n) = d which is the smallest d for which 3^u/2^d < 1 where u is the number of tripling steps among the first d steps starting from n. Clearly tau(n) <= a(n), and Terras conjectures (conjecture 2.9) that tau(n) = a(n) for n>=2. - Olivier Rozier, May 13 2024

			s(15) = 7, since the trajectory {T^(k)(15)} (k=1,2,3,...) equals 23,35,53,80,40,20,10.

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

T. D. Noe, Table of n, a(n) for n = 1..10000
J. C. Lagarias, The 3x+1 Problem: An Annotated Bibliography (1963-1999), arXiv:math/0309224 [math.NT], 2003-2011.
Olivier Rozier and Claude Terracol, Paradoxical behavior in Collatz sequences, arXiv:2502.00948 [math.GM], 2025. See p. 2.
Riho Terras, A stopping time problem on the positive integers, Acta Arith. 30 (1976) 241-252, with definition 0.1 chi(n) = a(n).
Index entries for sequences related to 3x+1 (or Collatz) problem

See A074473, which is the main entry for dropping times.
Cf. A014682, A006666, A006577.
Records: A060412, A060413.
Cf. A020914 (allowable dropping times). - K. Spage, Aug 22 2014

Collatz2[n_] := If[n<2, {}, Rest[NestWhileList[If[EvenQ[#], #/2, (3 # + 1)/2] &, n, # >= n &]]]; Table[Length[Collatz2[n]], {n, 1, 1000}]

a(n) = ceiling(A102419(n)/(1+log(2)/log(3))). - K. Spage, Aug 22 2014

Broken link fixed by K. Spage, Oct 22 2009

A060415 In the '3x+1' problem, take the sequence of starting values which set new records for the "dropping time" (A060412); sequence gives associated iterate where maximal value is reached in the trajectory with that start.

Original entry on oeis.org

0, 2, 3, 45, 48, 20, 78, 124, 95, 103, 62, 147, 186, 36, 168, 65, 60, 179, 41, 146, 254, 254, 319, 346, 423, 166, 297, 206, 223, 164, 659, 607, 840, 808, 512

Offset: 1

N. J. A. Sloane, Apr 06 2001; b-file added Nov 27 2007

nonn

N. J. A. Sloane, Table of n, a(n) for n = 1..35 (from the web page of Tomás Oliveira e Silva)
Tomás Oliveira e Silva, Tables
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A060412, A060413, A060414.

Corrected by Don Reble, May 13 2006

A340420 The number of steps that n requires to reach 1 under the map: m -> m/2 if m is even, m-> 3*m + 1 if m is an odd prime, otherwise m -> m - 1. a(n) = -1 if 1 is never reached.

Original entry on oeis.org

0, 1, 7, 2, 5, 8, 16, 3, 4, 6, 14, 9, 9, 17, 18, 4, 12, 5, 20, 7, 8, 15, 16, 10, 11, 10, 11, 18, 18, 19, 19, 5, 6, 13, 14, 6, 21, 21, 22, 8, 22, 9, 9, 16, 17, 17, 17, 11, 12, 12, 13, 11, 11, 12, 13, 19, 20, 19, 32, 20, 20, 20, 21, 6, 7, 7, 27, 14, 15, 15, 15

Offset: 1

Ya-Ping Lu, Jan 07 2021

Conjecture: a(n) is never equal to -1.

			a(3) = 7 because 3*3 + 1 = 10 -> 10/2 = 5 -> 3*5 + 1 = 16 -> 16/2 = 8 -> 8/2 = 4 -> 4/2 = 2 -> 2/2 = 1 -> 1.
a(14) = 17 because 14 -> 7 -> 22 -> 11 -> 34 -> 17 -> 52 -> 26 -> 13 -> 40 -> 20 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.
The 39 terms for a(n) <= 9 are given in the figure below.
145 288 12 42 13 80 133 264 260 258 255 512
  \  /   \  \  \ /    \ /    |   |   \  /
   144    6  21 40    132   130 129  256
     \     \   \ |     |     |    \  /
      72    3   20     66    65   128
        \     \ /       \     \   /
         36    10       33      64
           \     \        \    /
            18     5        32
               \     \     /
                 9      16
                   \    /
                      8
                      |
                      4
                      |
                      2
                      |
                      1

Alois P. Heinz, Table of n, a(n) for n = 1..65536

Cf. A006577, A060413, A339991, A340008, A340418.

a:= proc(n) option remember; `if`(n=1, 0, 1 + a(
     `if`(n::even, n/2, `if`(isprime(n), 3*n+1, n-1))))
    end:
seq(a(n), n=1..100);  # Alois P. Heinz, Jan 08 2021

a[n_] := a[n] = If[n == 1, 0, 1 + a[
   If[EvenQ[n], n/2, If[PrimeQ[n], 3n+1, n-1]]]];
Array[a, 100] (* Jean-François Alcover, Jan 30 2021, after Alois P. Heinz *)

f(n) = if (n % 2, if (isprime(n), 3*n+1, n-1), n/2);
a(n) = my(s=n, c=0); while(s>1, s=f(s); c++); c; \\ Michel Marcus, Jan 21 2021

from sympy import isprime
for n in range(1, 101):
    ct, m = 0, n
    while m > 1:
        if m%2 == 0: m //= 2
        elif isprime(m) == 1: m = 3*m + 1
        else: m -= 1
        ct += 1
    print(ct)

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

A060412 In the '3x+1' problem, these values for the starting value set new records for the "dropping time", number of steps to reach a lower value than the start.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A126241 Dropping times in the 3n+1 problem (or the Collatz problem). Let T(n):=n/2 if n is even, (3n+1)/2 otherwise (A014682). Let a(n) be the smallest integer k such that T^(k)(n)

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A060415 In the '3x+1' problem, take the sequence of starting values which set new records for the "dropping time" (A060412); sequence gives associated iterate where maximal value is reached in the trajectory with that start.

Views

Author

Keywords

Links

Crossrefs

Extensions

A340420 The number of steps that n requires to reach 1 under the map: m -> m/2 if m is even, m-> 3*m + 1 if m is an odd prime, otherwise m -> m - 1. a(n) = -1 if 1 is never reached.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python