A006577 -id:A006577 - cp's OEIS frontend

A222582 Smallest numbers k such that A006577(n+k) = A006577(n) + A006577(k), or 0 if no such number exists.

12, 2, 0, 0, 1152, 24, 26, 22, 16, 12, 0, 10, 10, 0, 10, 9, 0, 0, 0, 0, 0, 8, 0, 6, 8, 7, 6094, 8, 8, 8, 456, 8, 6, 249, 268, 133, 6, 131, 120, 6, 301, 7, 96, 6, 6, 112, 0, 79, 74, 77, 6, 6, 86, 0, 0, 67, 70, 65, 68, 6, 6, 84, 84, 6, 58, 61, 56, 6, 66, 6, 58

Offset: 1

Michel Lagneau, Feb 25 2013

nonn

A006577 is the number of halving and tripling steps to reach 1 in '3x+1' problem.

a(n) = 0 for n = 3, 4, 11, 14, 17, 18, 19, 20, 21, 23, 47, 54, 55, 73, ...

			a(12)=10 because A006577(12+10) = 15, and A006577(12) + A006577(10) = 9 + 6 = 15.

Cf. A006577, A221947.

lst:={ }:C:= proc(n) a := 0 ; x := n ; while x > 1 do if type(x, 'even') then x := x/2:a:=a+1:  else x := 3*x+1 ; a := a+1 ; end if; end do; a ; end proc:
for n from 1 to 73 do: ii:=0:for k from 2 to 100000 while(ii=0) do:z:=n+k : if  C(z)=C(n)+C(k) then ii:=1: printf ( "%d %d \n",n,k):else fi:od: if ii=0 then printf ( "%d %d \n",n,0):else fi:od:

A006370 The Collatz or 3x+1 map: a(n) = n/2 if n is even, 3n + 1 if n is odd.

Original entry on oeis.org

0, 4, 1, 10, 2, 16, 3, 22, 4, 28, 5, 34, 6, 40, 7, 46, 8, 52, 9, 58, 10, 64, 11, 70, 12, 76, 13, 82, 14, 88, 15, 94, 16, 100, 17, 106, 18, 112, 19, 118, 20, 124, 21, 130, 22, 136, 23, 142, 24, 148, 25, 154, 26, 160, 27, 166, 28, 172, 29, 178, 30, 184, 31, 190, 32, 196, 33

Offset: 0

N. J. A. Sloane

The 3x+1 or Collatz problem is as follows: start with any number n. If n is even, divide it by 2, otherwise multiply it by 3 and add 1. Do we always reach 1? This is an unsolved problem. It is conjectured that the answer is yes.
The Krasikov-Lagarias paper shows that at least N^0.84 of the positive numbers < N fall into the 4-2-1 cycle of the 3x+1 problem. This is far short of what we think is true, that all positive numbers fall into this cycle, but it is a step. - Richard C. Schroeppel, May 01 2002
Also A001477 and A016957 interleaved. - Omar E. Pol, Jan 16 2014, updated Nov 07 2017
a(n) is the image of a(2*n) under the 3*x+1 map. - L. Edson Jeffery, Aug 17 2014
The positions of powers of 2 in this sequence are given in A160967. - Federico Provvedi, Oct 06 2021
If displayed as a rectangular array with six columns, the columns are A008585, A350521, A016777, A082286, A016789, A350522 (see example). - Omar E. Pol, Jan 03 2022

			G.f. = 4*x + x^2 + 10*x^3 + 2*x^4 + 16*x^5 + 3*x^6 + 22*x^7 + 4*x^8 + 28*x^9 + ...
From _Omar E. Pol_, Jan 03 2022: (Start)
Written as a rectangular array with six columns read by rows the sequence begins:
   0,   4,  1,  10,  2,  16;
   3,  22,  4,  28,  5,  34;
   6,  40,  7,  46,  8,  52;
   9,  58, 10,  64, 11,  70;
  12,  76, 13,  82, 14,  88;
  15,  94, 16, 100, 17, 106;
  18, 112, 19, 118, 20, 124;
  21, 130, 22, 136, 23, 142;
  24, 148, 25, 154, 26, 160;
  27, 166, 28, 172, 29, 178;
  30, 184, 31, 190, 32, 196;
...
(End)

R. K. Guy, Unsolved Problems in Number Theory, E16.
J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..1000
Darrell Cox, The 3n + 1 Problem: A Probabilistic Approach, Journal of Integer Sequences, Vol. 15 (2012), #12.5.2.
David Eisenbud and Brady Haran, UNCRACKABLE? The Collatz Conjecture, Numberphile Video, 2016.
I. Krasikov and J. C. Lagarias, Bounds for the 3x+1 Problem using Difference Inequalities, arXiv:math/0205002 [math.NT], 2002.
J. C. Lagarias, The 3x+1 problem and its generalizations, Amer. Math. Monthly, 92 (1985), 3-23.
J. C. Lagarias, The set of rational cycles for the 3x+1 problem, Acta Arithmetica, LVI (1990), pp. 33-53.
J. C. Lagarias, The 3x+1 Problem: An Annotated Bibliography (1963-2000), arXiv:math/0309224 [math.NT], 2003-2011.
J. C. Lagarias, The 3x+1 Problem: an annotated bibliography, II (2000-2009), arXiv:math/0608208 [math.NT], 2006-2012.
Jeffrey C. Lagarias, The 3x+1 Problem: An Overview, arXiv:2111.02635 [math.NT], 2021.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
E. Roosendaal, On the 3x+1 problem.
S. Schreiber & N. J. A. Sloane, Correspondence, 1980.
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. A139391, A016945, A005408, A016825, A082286, A070165.
A006577 gives number of steps to reach 1.
Cf. A001281, A047374.
Column k=1 of A347270, n >= 1.

a006370 n | m /= 0    = 3 * n + 1
          | otherwise = n' where (n',m) = divMod n 2
-- Reinhard Zumkeller, Oct 07 2011

[(1/4)*(7*n+2-(-1)^n*(5*n+2)): n in [1..70]]; // Vincenzo Librandi, Dec 20 2016

f := n-> if n mod 2 = 0 then n/2 else 3*n+1; fi;
A006370:=(4+z+2*z**2)/(z-1)**2/(1+z)**2; # Simon Plouffe in his 1992 dissertation; uses offset 0

f[n_]:=If[EvenQ[n],n/2,3n+1];Table[f[n],{n,50}] (* Geoffrey Critzer, Jun 29 2013 *)
LinearRecurrence[{0,2,0,-1},{4,1,10,2},70] (* Harvey P. Dale, Jul 19 2016 *)

for(n=1,100,print1((1/4)*(7*n+2-(-1)^n*(5*n+2)),","))

A006370(n)=if(n%2,3*n+1,n/2) \\ Michael B. Porter, May 29 2010

def A006370(n):
    q, r = divmod(n, 2)
    return 3*n+1 if r else q # Chai Wah Wu, Jan 04 2015

G.f.: (4*x+x^2+2*x^3) / (1-x^2)^2.
a(n) = (1/4)*(7*n+2-(-1)^n*(5*n+2)). - Benoit Cloitre, May 12 2002
a(n) = ((n mod 2)*2 + 1)*n/(2 - (n mod 2)) + (n mod 2). - Reinhard Zumkeller, Sep 12 2002
a(n) = A014682(n+1) * A000034(n). - R. J. Mathar, Mar 09 2009
a(n) = a(a(2*n)) = -A001281(-n) for all n in Z. - Michael Somos, Nov 10 2016
E.g.f.: (2 + x)*sinh(x)/2 + 3*x*cosh(x). - Ilya Gutkovskiy, Dec 20 2016
From Federico Provvedi, Aug 17 2021: (Start)
Dirichlet g.f.: (1-2^(-s))*zeta(s) + (3-5*2^(-s))*zeta(s-1).
a(n) = ( a(n+2k) + a(n-2k) ) / 2, for every integer k. (End)
a(n) + a(n+1) = A047374(n+1). - Leo Ortega, Aug 22 2025

More terms from Larry Reeves (larryr(AT)acm.org), Apr 27 2001

Zero prepended and new Name from N. J. A. Sloane at the suggestion of M. F. Hasler, Nov 06 2017

A025586 Largest value in '3x+1' trajectory of n.

Original entry on oeis.org

1, 2, 16, 4, 16, 16, 52, 8, 52, 16, 52, 16, 40, 52, 160, 16, 52, 52, 88, 20, 64, 52, 160, 24, 88, 40, 9232, 52, 88, 160, 9232, 32, 100, 52, 160, 52, 112, 88, 304, 40, 9232, 64, 196, 52, 136, 160, 9232, 48, 148, 88, 232, 52, 160, 9232, 9232, 56, 196, 88, 304, 160, 184, 9232

Offset: 1

David W. Wilson

Here by definition the trajectory ends when 1 is reached. Therefore this sequence differs for n = 1 and n = 2 from A056959, which considers the orbit ending in the infinite loop 1 -> 4 -> 2 -> 1.
a(n) = A220237(n,A006577(n)). - Reinhard Zumkeller, Jan 03 2013
A006885 and A006884 give record values and where they occur. - Reinhard Zumkeller, May 11 2013
For n > 2, a(n) is divisible by 4. See the explanatory comment in A056959. - Peter Munn, Oct 14 2019
In an email of Aug 06 2023, Guy Chouraqui observes that the digital root of a(n) appears to be either 7 or a multiple of 4 for all n > 2.  (See also A006885.) - N. J. A. Sloane, Aug 11 2023

			The 3x + 1 trajectory of 9 is 9, 28, 14, 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1 (see A033479). Since the largest number in that sequence is 52, a(9) = 52.

T. D. Noe, Table of n, a(n) for n = 1..10000
Christian Hercher, There are no Collatz m-Cycles with m <= 91, J. Int. Seq. (2023) Vol. 26, Article 23.3.5.
Philippe Picart, Algorithme de Collatz et conjecture de Syracuse
Index entries for sequences related to 3x+1 (or Collatz) problem

Essentially the same as A056959: only a(1) and a(2) differ, see Comments.

Cf. A006370, A006577, A006884, A006885, A220237.

a025586 = last . a220237_row
-- Reinhard Zumkeller, Jan 03 2013, Aug 29 2012

a:= proc(n) option remember; `if`(n=1, 1,
      max(n, a(`if`(n::even, n/2, 3*n+1))))
    end:
seq(a(n), n=1..87);  # Alois P. Heinz, Oct 16 2021

collatz[a0_Integer, maxits_:1000] := NestWhileList[If[EvenQ[#], #/2, 3# + 1] &, a0, Unequal[#, 1, -1, -10, -34] &, 1, maxits]; (* collatz[n] function definition by Eric Weisstein *) Flatten[Table[Take[Sort[Collatz[n], Greater], 1], {n, 60}]] (* Alonso del Arte, Nov 14 2007 *)
collatzMax[n_] := Module[{r = m = n}, While[m > 2, If[OddQ[m], m = 3 * m + 1; If[m > r, r = m], m = m/2]]; r]; Table[ collatzMax[n], {n, 100}] (* Jean-François Alcover, Jan 28 2015, after Charles R Greathouse IV *)
(* Using Weisstein's collatz[n] definition above *) Table[Max[collatz[n]], {n, 100}] (* Alonso del Arte, May 25 2019 *)

a(n)=my(r=n);while(n>2,if(n%2,n=3*n+1;if(n>r,r=n),n/=2));r \\ Charles R Greathouse IV, Jul 19 2011

def a(n):
    if n<2: return 1
    l=[n, ]
    while True:
        if n%2==0: n//=2
        else: n = 3*n + 1
        if not n in l:
            l+=[n, ]
            if n<2: break
        else: break
    return max(l)
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Apr 14 2017

def collatz(n: Int): Int = (n % 2) match {
  case 0 => n / 2
  case 1 => 3 * n + 1
}
def collatzTrajectory(start: Int): List[Int] = if (start == 1) List(1)
else {
  import scala.collection.mutable.ListBuffer
  var curr = start; var trajectory = new ListBuffer[Int]()
  while (curr > 1) { trajectory += curr; curr = collatz(curr) }
  trajectory.toList
}
for (n <- 1 to 100) yield collatzTrajectory(n).max // Alonso del Arte, Jun 02 2019

A006667 Number of tripling steps to reach 1 from n in '3x+1' problem, or -1 if 1 is never reached.

Original entry on oeis.org

0, 0, 2, 0, 1, 2, 5, 0, 6, 1, 4, 2, 2, 5, 5, 0, 3, 6, 6, 1, 1, 4, 4, 2, 7, 2, 41, 5, 5, 5, 39, 0, 8, 3, 3, 6, 6, 6, 11, 1, 40, 1, 9, 4, 4, 4, 38, 2, 7, 7, 7, 2, 2, 41, 41, 5, 10, 5, 10, 5, 5, 39, 39, 0, 8, 8, 8, 3, 3, 3, 37, 6, 42, 6, 3, 6, 6, 11, 11, 1, 6, 40, 40, 1, 1, 9, 9, 4, 9, 4, 33, 4, 4, 38

Offset: 1

N. J. A. Sloane and Bill Gosper

A075680, which gives the values for odd n, isolates the essential behavior of this sequence. - T. D. Noe, Jun 01 2006

A033959 and A033958 give record values and where they occur. - Reinhard Zumkeller, Jan 08 2014

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 204, Problem 22.
R. K. Guy, Unsolved Problems in Number Theory, E16.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..10000
J. C. Lagarias, The 3x+1 problem and its generalizations, Amer. Math. Monthly, 92 (1985), 3-23.
Eric Weisstein's World of Mathematics, Collatz Problem.
Wikipedia, Collatz conjecture
Index entries for sequences related to 3x+1 (or Collatz) problem

Equals A078719(n)-1.

Cf. A000079, A000265, A006370, A006577, A006666 (halving steps), A092893, A127789, A139391, A209229.

a006667 = length . filter odd . takeWhile (> 2) . (iterate a006370)
a006667_list = map a006667 [1..]
-- Reinhard Zumkeller, Oct 08 2011

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

Table[Count[Differences[NestWhileList[If[EvenQ[#],#/2,3#+1]&,n,#>1&]], ?Positive], {n,100}] (* _Harvey P. Dale, Nov 14 2011 *)

for(n=2,100,s=n; t=0; while(s!=1,if(s%2==0,s=s/2,s=(3*s+1)/2; t++); if(s==1,print1(t,","); ); ))

def a(n):
    if n==1: return 0
    x=0
    while True:
        if n%2==0: n/=2
        else:
            n = 3*n + 1
            x+=1
        if n<2: break
    return x
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Apr 14 2017

a(1) = 0, a(n) = a(n/2) if n is even, a(n) = a(3n+1)+1 if n>1 is odd. The Collatz conjecture is that this defines a(n) for all n >= 1.
a(n) = A078719(n) - 1; a(A000079(n))=0; a(A062052(n))=1; a(A062053(n))=2; a(A062054(n))=3; a(A062055(n))=4; a(A062056(n))=5; a(A062057(n))=6; a(A062058(n))=7; a(A062059(n))=8; a(A062060(n))=9. - Reinhard Zumkeller, Oct 08 2011
a(n*2^k) = a(n), for all k >= 0. - L. Edson Jeffery, Aug 11 2014
a(n) = floor(log(2^A006666(n)/n)/log(3)). - Joe Slater, Aug 30 2017
a(n) = a(A085062(n)) + A007814(n+1) for n >= 2. - Alan Michael Gómez Calderón, Feb 07 2025
From  Alan Michael Gómez Calderón, Mar 31 2025: (Start)
a(n) = a(A139391(n)) + (n mod 2) for n >= 2;
a(n) = a(A139391(A000265(n))) - A209229(n) + 1 for n >= 2;
a(n) = a(A000265(A139391(n))) + (n mod 2) for n >= 2. (End)

More terms from Larry Reeves (larryr(AT)acm.org), Apr 27 2001

"Escape clause" added to definition by N. J. A. Sloane, Jun 06 2017

A006666 Number of halving steps to reach 1 in '3x+1' problem, or -1 if this never happens.

Original entry on oeis.org

0, 1, 5, 2, 4, 6, 11, 3, 13, 5, 10, 7, 7, 12, 12, 4, 9, 14, 14, 6, 6, 11, 11, 8, 16, 8, 70, 13, 13, 13, 67, 5, 18, 10, 10, 15, 15, 15, 23, 7, 69, 7, 20, 12, 12, 12, 66, 9, 17, 17, 17, 9, 9, 71, 71, 14, 22, 14, 22, 14, 14, 68, 68, 6, 19, 19, 19, 11, 11, 11, 65, 16, 73, 16, 11, 16

Offset: 1

N. J. A. Sloane, Bill Gosper

Equals the total number of steps to reach 1 under the modified '3x+1' map: T(n) = n/2 if n is even, (3n+1)/2 if n is odd (see A014682).

Pairs of consecutive integers of the same height occur infinitely often and in infinitely many different patterns (Garner 1985). - Joe Slater, May 24 2018

			2 -> 1 so a(2) = 1; 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1, with 5 halving steps, so a(3) = 5; 4 -> 2 -> 1 has two halving steps, so a(4) = 2; etc.

R. K. Guy, Unsolved Problems in Number Theory, E16.
J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..10000
David Eisenbud and Brady Haran, UNCRACKABLE? The Collatz Conjecture, Numberphile Video, 2016.
Lynn E. Garner, On Heights in the Collatz 3n+1 Problem, Discrete Math. 55 (1985) 57-64.
J. C. Lagarias, The 3x+1 problem and its generalizations, Amer. Math. Monthly, m92 (1985), 3-23.
Jeffrey C. Lagarias, The 3x+1 Problem: An Overview, arXiv:2111.02635 [math.NT], 2021.
K. Matthews, The Collatz Conjecture
Eric Weisstein's World of Mathematics, Collatz Problem
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A006370, A006577, A006667 (tripling steps), A014682, A092892, A127789 (record indices of 2^a(n)/(3^A006667(n)*n)).

a006666 = length . filter even . takeWhile (> 1) . (iterate a006370)
-- Reinhard Zumkeller, Oct 08 2011

# A014682
T:=proc(n) if n mod 2 = 0 then n/2 else (3*n+1)/2; fi; end;
# A006666
t1:=[0]:
for n from 2 to 100 do
L:=1; p := n;
while T(p) <> 1 do p:=T(p); L:=L+1; od:
t1:=[op(t1),L];
od: t1;

Table[Count[NestWhileList[If[OddQ[#],3#+1,#/2]&,n,#>1&],?(EvenQ[#]&)], {n,80}] (* _Harvey P. Dale, Sep 30 2011 *)

a(n)=my(t); while(n>1, if(n%2, n=3*n+1, n>>=1; t++)); t \\ Charles R Greathouse IV, Jun 21 2017

def a(n):
    if n==1: return 0
    x=0
    while True:
        if not n%2:
            n//=2
            x+=1
        else: n = 3*n + 1
        if n<2: break
    return x
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Apr 14 2017

A092892(a(n)) = n and A092892(m) <> n for m < a(n). - Reinhard Zumkeller, Mar 14 2014
a(2^n) = n. - Bob Selcoe, Apr 16 2015
a(n) = ceiling(log(n*3^A006667(n))/log(2)). - Joe Slater, Aug 30 2017
a(2^k-1) = a(2^(k+1)-1)-1, for odd k>1. - Joe Slater, May 17 2018
a(n) = a(A085062(n)) + A007814(n+1) + 1 for n >= 2. - Alan Michael Gómez Calderón, Feb 01 2025

More terms from Larry Reeves (larryr(AT)acm.org), Apr 27 2001

Name edited by M. F. Hasler, May 07 2018

A008908 a(n) = (1 + number of halving and tripling steps to reach 1 in the Collatz (3x+1) problem), or -1 if 1 is never reached.

Original entry on oeis.org

1, 2, 8, 3, 6, 9, 17, 4, 20, 7, 15, 10, 10, 18, 18, 5, 13, 21, 21, 8, 8, 16, 16, 11, 24, 11, 112, 19, 19, 19, 107, 6, 27, 14, 14, 22, 22, 22, 35, 9, 110, 9, 30, 17, 17, 17, 105, 12, 25, 25, 25, 12, 12, 113, 113, 20, 33, 20, 33, 20, 20, 108, 108, 7, 28, 28, 28, 15, 15, 15, 103

Offset: 1

N. J. A. Sloane, Bill Gosper

The number of steps (iterations of the map A006370) to reach 1 is given by A006577, this sequence counts 1 more. - M. F. Hasler, Nov 05 2017

When Collatz 3N+1 function is seen as an isometry over the dyadics, the halving step necessarily following each tripling is not counted, hence N -> N/2, if even, but N -> (3N+1)/2, if odd. Counting iterations of this map until reaching 1 leads to sequence A064433. - Michael Vielhaber (vielhaber(AT)gmail.com), Nov 18 2009

R. K. Guy, Unsolved Problems in Number Theory, E16.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
J. C. Lagarias, The 3x+1 problem and its generalizations, Amer. Math. Monthly, 92 (1985), 3-23.
Nitrxgen, Collatz Calculator
Wikipedia, Collatz conjecture
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A006577, A006370, A006667, A075677.

a008908 = length . a070165_row
-- Reinhard Zumkeller, May 11 2013, Aug 30 2012, Jul 19 2011

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

Table[Length[NestWhileList[If[EvenQ[ # ], #/2, 3 # + 1] &, i, # != 1 &]], {i, 75}]

a(n)=my(c=1); while(n>1, n=if(n%2, 3*n+1, n/2); c++); c \\ Charles R Greathouse IV, May 18 2015

def a(n):
    if n==1: return 1
    x=1
    while True:
        if n%2==0: n//=2
        else: n = 3*n + 1
        x+=1
        if n<2: break
    return x
print([a(n) for n in range(1, 101)]) # Indranil Ghosh, Apr 15 2017

a(n) = A006577(n) + 1.
a(n) = f(n,1) with f(n,x) = if n=1 then x else f(A006370(n),x+1).
a(A033496(n)) = A159999(A033496(n)). - Reinhard Zumkeller, May 04 2009
a(n) = A006666(n) + A078719(n).
a(n) = length of n-th row in A070165. - Reinhard Zumkeller, May 11 2013

More terms from Larry Reeves (larryr(AT)acm.org), Apr 27 2001
"Escape clause" added to definition by N. J. A. Sloane, Jun 06 2017
Edited by M. F. Hasler, Nov 05 2017

A006578 Triangular numbers plus quarter squares: n*(n+1)/2 + floor(n^2/4) (i.e., A000217(n) + A002620(n)).

Original entry on oeis.org

0, 1, 4, 8, 14, 21, 30, 40, 52, 65, 80, 96, 114, 133, 154, 176, 200, 225, 252, 280, 310, 341, 374, 408, 444, 481, 520, 560, 602, 645, 690, 736, 784, 833, 884, 936, 990, 1045, 1102, 1160, 1220, 1281, 1344, 1408, 1474, 1541, 1610, 1680, 1752, 1825, 1900, 1976, 2054

Offset: 0

N. J. A. Sloane

Equals (1, 2, 3, 4, ...) convolved with (1, 2, 1, 2, ...). a(4) = 14 = (1, 2, 3, 4) dot (2, 1, 2, 1) = (2 + 2 + 6 + 4). - Gary W. Adamson, May 01 2009
We observe that is the transform of A032766 by the following transform T: T(u_0,u_1,u_2,u_3,...) = (u_0, u_0+u_1, u_0+u_1+u_2, u_0+u_1+u_2+u_3+u_4,...). In other words, v_p = Sum_{k=0..p} u_k and the g.f. phi_v of is given by phi_v = phi_u/(1-z). - Richard Choulet, Jan 28 2010
Equals row sums of a triangle with (1, 4, 7, 10, ...) in every column, shifted down twice for columns > 1. - Gary W. Adamson, Mar 03 2010
Number of pairs (x,y) with x in {0,...,n}, y odd in {0,...,2n}, and x < y. - Clark Kimberling, Jul 02 2012
Also A049451 and positives A000567 interleaved. - Omar E. Pol, Aug 03 2012
Similar to A001082. Members of this family are A093005, A210977, this sequence, A210978, A181995, A210981, A210982. - Omar E. Pol, Aug 09 2012

			G.f. = x + 4*x^2 + 8*x^3 + 14*x^4 + 21*x^5 + 30*x^6 + 40*x^7 + 52*x^8 + 65*x^9 + ...

Marc LeBrun, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Vincenzo Librandi, Table of n, a(n) for n = 0..10000
Bruno Berselli, Hexagonal spiral containing the initial terms.
Marc Le Brun, Email to N. J. A. Sloane, Jul 1991
Emanuele Munarini, Topological indices for the antiregular graphs, Le Mathematiche (2021) Vol. 76, No. 1, see p. 283.
Simon Plouffe, Approximations de séries génératrices et quelques conjectures, Dissertation, Université du Québec à Montréal, 1992; arXiv:0911.4975 [math.NT], 2009.
Simon Plouffe, 1031 Generating Functions, Appendix to Thesis, Montreal, 1992.
Index entries for linear recurrences with constant coefficients, signature (2,0,-2,1).

Cf. A001859, A077043, A002620, A002378.
Row sums of A104567.
Cf. A000034, A032766, A002717, A070893. - Richard Choulet, Jan 28 2010
Cf. A051125.

[(6*n^2+4*n-1+(-1)^n)/8: n in [0..50] ]; // Vincenzo Librandi, Aug 20 2011

with (combinat): seq(count(Partition((3*n+1)), size=3), n=0..52); # Zerinvary Lajos, Mar 28 2008
# 2nd program
A006578 := proc(n)
    (6*n^2 + 4*n - 1 + (-1)^n)/8 ;
end proc: # R. J. Mathar, Apr 28 2017

Accumulate[LinearRecurrence[{1,1,-1}, {0,1,3}, 100]] (* Harvey P. Dale, Sep 29 2013 *)
a[ n_] := Quotient[n + 1, 2] (Quotient[n, 2] 3 + 1); (* Michael Somos, Jun 09 2014 *)
a[ n_] := Quotient[3 (n + 1)^2 + 1, 4] - (n + 1); (* Michael Somos, Jun 10 2015 *)
LinearRecurrence[{2, 0, -2, 1},{0, 1, 4, 8},53] (* Ray Chandler, Aug 03 2015 *)

{a(n) = (3*(n+1)^2 + 1)\4 - n - 1}; /* Michael Somos, Mar 10 2006 */

Expansion of x*(1+2*x) / ((1-x)^2*(1-x^2)). - Simon Plouffe in his 1992 dissertation
a(n) + A002620(n) = A002378(n) = n*(n+1).
Partial sums of A032766. - Paul Barry, May 30 2003
a(n) = a(n-1) + a(n-2) - a(n-3) + 3 = A002620(n) + A004526(n) = A001859(n) - A004526(n+1). - Henry Bottomley, Mar 08 2000
a(n) = (6*n^2 + 4*n - 1 + (-1)^n)/8. - Paul Barry, May 30 2003
a(n) = A001859(-1-n) for all n in Z. - Michael Somos, May 10 2006
a(n) = (A002378(n)/2 + A035608(n))/2. - Reinhard Zumkeller, Feb 07 2010
a(n) = (3*n^2 + 2*n - (n mod 2))/4. - Ctibor O. Zizka, Mar 11 2012
a(n) = Sum_{i=1..n} floor(3*i/2) = Sum_{i=0..n} (i + floor(i/2)). - Enrique Pérez Herrero, Apr 21 2012
a(n) = 3*n*(n+1)/2 - A001859(n). - Clark Kimberling, Jul 02 2012
a(n) = Sum_{i=1..n} (n - i + 1) * 2^( (i+1) mod 2 ). - Wesley Ivan Hurt, Mar 30 2014
a(n) = A002717(n) - A002717(n-1). - Michael Somos, Jun 09 2014
a(n) = Sum_{k=1..n} floor((n+k+1)/2). - Wesley Ivan Hurt, Mar 31 2017
a(n) = A002620(n+1)+2*A002620(n). - R. J. Mathar, Apr 28 2017
Sum_{n>=1} 1/a(n) = 3 - Pi/(4*sqrt(3)) - 3*log(3)/4. - Amiram Eldar, May 28 2022
E.g.f.: (x*(5 + 3*x)*cosh(x) - (1 - 5*x - 3*x^2)*sinh(x))/4. - Stefano Spezia, Aug 22 2023

Offset and description changed by N. J. A. Sloane, Nov 30 2006

A006877 In the '3x+1' problem, these values for the starting value set new records for number of steps to reach 1.

Original entry on oeis.org

1, 2, 3, 6, 7, 9, 18, 25, 27, 54, 73, 97, 129, 171, 231, 313, 327, 649, 703, 871, 1161, 2223, 2463, 2919, 3711, 6171, 10971, 13255, 17647, 23529, 26623, 34239, 35655, 52527, 77031, 106239, 142587, 156159, 216367, 230631, 410011, 511935, 626331, 837799

Offset: 1

N. J. A. Sloane and Robert Munafo

Both the 3x+1 steps and the halving steps are counted.

This sequence without a(2) = 2 specifies where records occur in A208981. - Omar E. Pol, Apr 14 2022

D. R. Hofstadter, Goedel, Escher, Bach: an Eternal Golden Braid, Random House, 1980, p. 400.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Hugo Pfoertner, Table of n, a(n) for n = 1..148 (from Eric Rosendaal's 3x+1 Delay Records, terms 1..130 from T. D. Noe)
T. Ahmed and H. Snevily, Are there an infinite number of Collatz integers?, 2013.
David Barina, Convergence verification of the Collatz problem, The Journal of Supercomputing 77(3) (2021), 2681-2688.
David Barina, Computational Verification of the Collatz Problem, preprint on Research Square (2024).
Gaston H. Gonnet, Computations on the 3n+1 conjecture, Maple Technical Newsletter 6 (1991): 18-22.
Brian Hayes, Computer Recreations: On the ups and downs of hailstone numbers, Scientific American, 250 (No. 1, 1984), pp. 10-16.
J. C. Lagarias, The 3x+1 problem and its generalizations, Amer. Math. Monthly, 92 (1985), 3-23.
G. T. Leavens and M. Vermeulen, 3x+1 search programs, Computers and Mathematics with Applications, 24 (1992), 79-99. (Annotated scanned copy)
Robert Munafo, Integer Sequences Related to 3x+1 Collatz Iteration
Eric Roosendaal, 3x+1 Delay Records
Olivier Rozier and Claude Terracol, Paradoxical behavior in Collatz sequences, arXiv:2502.00948 [math.GM], 2025. See p. 15.
Robert G. Wilson v, Letter to N. J. A. Sloane with attachments, Jan. 1989
Robert G. Wilson v, Tables of A6877, A6884, A6885, Jan. 1989
Index entries for sequences from "Goedel, Escher, Bach"
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A006884, A006885, A006877, A006878, A033492, A380138.

A006877 := proc(n) local a,L; L := 0; a := n; while a <> 1 do if a mod 2 = 0 then a := a/2; else a := 3*a+1; fi; L := L+1; od: RETURN(L); end;

numberOfSteps[x0_] := Block[{x = x0, nos = 0}, While [x != 1 , If[Mod[x, 2] == 0 , x = x/2, x = 3*x + 1]; nos++]; nos]; a[1] = 1; a[n_] := a[n] = Block[{x = a[n-1] + 1}, record = numberOfSteps[x - 1]; While[ numberOfSteps[x] <= record, x++]; x]; A006877 = Table[ Print[a[n]]; a[n], {n, 1, 44}](* Jean-François Alcover, Feb 14 2012 *)
DeleteDuplicates[Table[{n,Length[NestWhileList[If[EvenQ[#],#/2,3#+1]&,n,#>1&]]},{n,838000}],GreaterEqual[#1[[2]],#2[[2]]]&][[All,1]] (* Harvey P. Dale, May 13 2022 *)

A006577(n)=my(s);while(n>1,n=if(n%2,3*n+1,n/2);s++);s
step(n,r)=my(t);forstep(k=bitor(n,1),2*n,2,t=A006577(k);if(t>r,return([k,t])));[2*n,r+1]
r=0;print1(n=1);for(i=1,100,[n,r]=step(n,r); print1(", "n)) \\ Charles R Greathouse IV, Apr 01 2013

c1 = lambda x: (3*x+1 if (x%2) else x>>1)
r = -1
for n in range(1, 10**5):
    a=0 ; n1=n
    while n>1: n=c1(n); a+=1;
    if a > r: print(n1, end = ', '); r=a
print('...') # Ya-Ping Lu and Robert Munafo, Mar 22 2024

A006590 a(n) = Sum_{k=1..n} ceiling(n/k).

Original entry on oeis.org

1, 3, 6, 9, 13, 16, 21, 24, 29, 33, 38, 41, 48, 51, 56, 61, 67, 70, 77, 80, 87, 92, 97, 100, 109, 113, 118, 123, 130, 133, 142, 145, 152, 157, 162, 167, 177, 180, 185, 190, 199, 202, 211, 214, 221, 228, 233, 236, 247, 251, 258, 263, 270, 273, 282, 287, 296, 301

Offset: 1

N. J. A. Sloane

The following sequences all have the same parity: A004737, A006590, A027052, A071028, A071797, A078358, A078446. - Jeremy Gardiner, Mar 16 2003

Given the fact that ceiling(x) <= x+1, we can, using well known results for the harmonic series, easily derive that n*log(n) <= a(n) <= n*(1+log(n)) + n = n(log(n)+2). - Stefan Steinerberger, Apr 08 2006

Marc LeBrun, personal communication.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 1..1000
M. Le Brun, Email to N. J. A. Sloane, Jul 1991

Cf. A000005, A006218.

a006590 n = sum $ map f [1..n] where
   f x = y + 1 - 0 ^ r where (y, r) = divMod n x
-- Reinhard Zumkeller, Feb 18 2013

[&+[Ceiling(n/j): j in [1..n]] : n in [1..60]]; // G. C. Greubel, Nov 07 2019

seq(add(ceil(n/j), j = 1..n), n = 1..60); # G. C. Greubel, Nov 07 2019

Table[Sum[Ceiling[n/i], {i, 1, n}], {n, 1, 60}] (* Stefan Steinerberger, Apr 08 2006 *)
nxt[{n_,a_}]:={n+1,a+DivisorSigma[0,n]+1}; Transpose[NestList[nxt,{1,1},60]][[2]] (* Harvey P. Dale, Aug 23 2013 *)

first(n)=my(v=vector(n,i,i),s); for(i=1,n-1,v[i+1]+=s+=numdiv(i)); v \\ Charles R Greathouse IV, Feb 07 2017

a(n) = n + sum(k=1, n-1, (n-1)\k); \\ Michel Marcus, Oct 10 2021

from math import isqrt
def A006590(n): return (lambda m: n+2*sum((n-1)//k for k in range(1, m+1))-m*m)(isqrt(n-1)) # Chai Wah Wu, Oct 09 2021

[sum(ceil(n/j) for j in (1..n)) for n in (1..60)] # G. C. Greubel, Nov 07 2019

a(n) = n+Sum_{k=1..n-1} tau(k). - Vladeta Jovovic, Oct 17 2002
a(n) = 1 + a(n-1) + tau(n-1), a(n) = A006218(n-1) + n. - T. D. Noe, Jan 05 2007
a(n) = a(n-1) + A000005(n) + 1 for n >= 2. a(n) = A161886(n) - A000005(n) + 1 = A161886(n-1) + 2 = A006218(n) + A049820(n) for n >= 1. - Jaroslav Krizek, Nov 14 2009

More terms from Stefan Steinerberger, Apr 08 2006

A033493 Sum of the numbers in the trajectory of n for the 3x+1 problem.

Original entry on oeis.org

1, 3, 49, 7, 36, 55, 288, 15, 339, 46, 259, 67, 119, 302, 694, 31, 214, 357, 519, 66, 148, 281, 633, 91, 658, 145, 101440, 330, 442, 724, 101104, 63, 841, 248, 540, 393, 535, 557, 2344, 106, 101331, 190, 1338, 325, 497, 679, 100979, 139, 806, 708, 1130, 197

Offset: 1

Jeff Burch

Given a power of two, the value in this sequence is the next higher Mersenne number, or a(2^m) = 2^(m + 1) - 1. - Alonso del Arte, Apr 10 2009

Conjecture: a(n) = A006577(n)^2 only at a(3) = 49. Verified for n <= 10^7. - Luca Santarsiero, Jul 13 2025

			a(5) = 36 because the Ulam's conjecture trajectory sequence starting on 5 runs 5, 16, 8, 4, 2, 1 and therefore 5 + 16 + 8 + 4 + 2 + 1 = 36. - _Alonso del Arte_, Apr 10 2009

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Eric Weisstein's World of Mathematics, Collatz Problem
Wikipedia, Collatz conjecture
Index entries for sequences related to 3x+1 (or Collatz) problem

Apart from initial term, exactly the same as A049074.

Cf. A006370, A006577, A070165.

a033493 = sum . a070165_row  -- Reinhard Zumkeller, Oct 08 2011

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

collatz[1] = 1; collatz[n_Integer?OddQ] := 3n + 1; collatz[n_Integer?EvenQ] := n/2; Table[-1 + Plus @@ FixedPointList[collatz, n], {n, 60}] (* Alonso del Arte, Apr 10 2009 *)

def a(n):
    if n==1: return 1
    l=[n, ]
    while True:
        if n%2==0: n//=2
        else: n = 3*n + 1
        l+=[n, ]
        if n<2: break
    return sum(l)
print([a(n) for n in range(1, 101)])  # Indranil Ghosh, Apr 14 2017

a(n) = Sum_{k=1..A006577(n)} A070165(k). - Reinhard Zumkeller, Oct 08 2011

Corrected a(16) to 31 to match other powers of 2; removed duplicate value of a(48) = 139 because a(49) = 806 and not 139. - Alonso del Arte, Apr 10 2009

cp's OEIS Frontend

A222582 Smallest numbers k such that A006577(n+k) = A006577(n) + A006577(k), or 0 if no such number exists.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Maple

A006370 The Collatz or 3x+1 map: a(n) = n/2 if n is even, 3n + 1 if n is odd.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Magma

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A025586 Largest value in '3x+1' trajectory of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Scala

A006667 Number of tripling steps to reach 1 from n in '3x+1' problem, or -1 if 1 is never reached.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A006666 Number of halving steps to reach 1 in '3x+1' problem, or -1 if this never happens.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A008908 a(n) = (1 + number of halving and tripling steps to reach 1 in the Collatz (3x+1) problem), or -1 if 1 is never reached.

Views

Author