A006577 -id:A006577 - cp's OEIS frontend

A001281 Image of n under the map n->n/2 if n even, n->3n-1 if n odd.

0, 2, 1, 8, 2, 14, 3, 20, 4, 26, 5, 32, 6, 38, 7, 44, 8, 50, 9, 56, 10, 62, 11, 68, 12, 74, 13, 80, 14, 86, 15, 92, 16, 98, 17, 104, 18, 110, 19, 116, 20, 122, 21, 128, 22, 134, 23, 140, 24, 146, 25, 152, 26, 158, 27, 164, 28, 170, 29, 176, 30, 182, 31, 188

Offset: 0

N. J. A. Sloane

On the set of positive integers, the orbit of any number seems to end in the orbit of 1, of 5 or of 17. Writing n=1+q*2^p with q odd, it is easily seen that for p=0,1 and p>3, some iterations of the map lead to a strictly smaller number (for n>17). The cases p=2 and p=3 may give rise to bigger loops (depending on the form of q). See sequences A135727-A135729 for maxima of the orbits and corresponding record indices. - M. F. Hasler, Nov 29 2007

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

T. D. Noe, Table of n, a(n) for n = 0..1000
J. C. Lagarias, The 3x+1 problem and its generalizations, Amer. Math. Monthly, 92 (1985), 3-23.
Index entries for linear recurrences with constant coefficients, signature (0,2,0,-1)

Cf. A037082.

Cf. A037084, A039500-A039505, A135727-A135730. See also A006370, A006577 (Collatz 3x+1 problem).

f := n-> if n mod 2 = 0 then n/2 else 3*n-1; fi;

Table[If[OddQ[n], 3*n-1, n/2], {n, 0, 100}] (* T. D. Noe, Jun 27 2012 *)

A001281(n)=if(n%2,3*n-1,n>>1) \\ M. F. Hasler, Nov 29 2007

f(n) = (7n-2-(5n-2)*cos(Pi*n))/4. - Robert W. Craigen (craigen(AT)fresno.edu)

G.f.: x*(2 + x + 4*x^2)/((1 - x)^2*(1 + x)^2). - Ilya Gutkovskiy, Aug 17 2016

A127824 Triangle in which row n is a sorted list of all numbers having total stopping time n in the Collatz (or 3x+1) iteration.

Original entry on oeis.org

1, 2, 4, 8, 16, 5, 32, 10, 64, 3, 20, 21, 128, 6, 40, 42, 256, 12, 13, 80, 84, 85, 512, 24, 26, 160, 168, 170, 1024, 48, 52, 53, 320, 336, 340, 341, 2048, 17, 96, 104, 106, 113, 640, 672, 680, 682, 4096, 34, 35, 192, 208, 212, 213, 226, 227, 1280, 1344, 1360, 1364

Offset: 0

T. D. Noe, Jan 31 2007

The length of each row is A005186(n). The largest number in row n is 2^n. The second-largest number in row n is A000975(n-2) for n>4. The smallest number in row n is A033491(n). The Collatz conjecture asserts that every positive integer occurs in some row of this triangle.
n is an element of row number A006577(n). - Reinhard Zumkeller, Oct 03 2012
Conjecture: The numbers T(n, 1),...,T(n, k_n) of row n are arranged in non-overlapping clusters of numbers which have the same order of magnitude and whose Collatz trajectories to 1 have the same numbers of ups and downs. The highest cluster of row n is just the number 2^n, the trajectory to 1 of which has n-1 downs and no ups. The second highest cluster of row n consists of the numbers T(n, k_n - r) = 4^(r - 1) * t(n - 2*r + 2) for 1 <= r <= (n - 3) / 2, where t(k) = (2^k - (-1)^k - 3) / 6. These have n-2 downs and one up. The largest and second largest number of this latter cluster are given by A000975 and A153772. - Markus Sigg, Sep 25 2020

			The triangle starts:
   0:   1
   1:   2
   2:   4
   3:   8
   4:  16
   5:   5   32
   6:  10   64
   7:   3   20   21  128
   8:   6   40   42  256
   9:  12   13   80   84   85  512
  10:  24   26  160  168  170 1024
  11:  48   52   53  320  336  340  341 2048
  12:  17   96  104  106  113  640  672  680  682 4096
- _Reinhard Zumkeller_, Oct 03 2012

See also A006577.

Alois P. Heinz, Rows n = 0..42, flattened (first 31 rows from T. D. Noe)
Paul Andaloro, On total stopping times under 3x+1 iteration, Fib. Quar. 38 (1) (2000) 73.
Jason Davies, Collatz Graph: All Numbers Lead to One
Wolfdieter Lang, On Collatz Words, Sequences, and Trees, Journal of Integer Sequences, Vol 17 (2014), Article 14.11.7.
Markus Sigg, On the cluster structures in Collatz preimages, arXiv:2012.07839 [math.GM], 2020.
Wikipedia, Collatz Conjecture

Cf. A006577 (total stopping time of n), A088975 (traversal of the Collatz tree).
Column k=1 gives A033491.
Last elements of rows give A000079.
Row lengths give A005186.
Row sums give A337673(n+1).

import Data.List (union, sort)
a127824 n k = a127824_tabf !! n !! k
a127824_row n = a127824_tabf !! n
a127824_tabf = iterate f [1] where
   f row = sort $ map (* 2) row `union`
                  [x' | x <- row, let x' = (x - 1) `div` 3,
                        x' * 3 == x - 1, odd x', x' > 1]
-- Reinhard Zumkeller, Oct 03 2012

s={1}; t=Flatten[Join[s, Table[s=Union[2s, (Select[s,Mod[ #,3]==1 && OddQ[(#-1)/3] && (#-1)/3>1&]-1)/3]; s, {n,13}]]]

Suppose S is the list of numbers in row n. Then the list of numbers in row n+1 is the union of each number in S multiplied by 2 and the numbers (x-1)/3, where x is in S, with x=1 (mod 3) and where (x-1)/3 is an odd number greater than 1.

A033491 a(n) is the smallest integer that takes n halving and tripling steps to reach 1 in the 3x+1 problem.

Original entry on oeis.org

1, 2, 4, 8, 16, 5, 10, 3, 6, 12, 24, 48, 17, 34, 11, 22, 7, 14, 28, 9, 18, 36, 72, 25, 49, 98, 33, 65, 130, 43, 86, 172, 57, 114, 39, 78, 153, 305, 105, 203, 406, 135, 270, 540, 185, 361, 123, 246, 481, 169, 329, 641, 219, 427, 159, 295, 569, 1138, 379, 758, 283, 505

Offset: 0

Jeff Burch

a(n) is the smallest term in n-th row of A127824. - Reinhard Zumkeller, Nov 29 2012
Interestingly, there are many n such that a(n) = 2*a(n-1). - Dmitry Kamenetsky, Feb 11 2017
a(n) is the position of the first occurrence of n in A006577. - Sean A. Irvine, Jul 07 2020

T. D. Noe, Table of n, a(n) for n = 0..1924 (from Eric Roosendaal's data) [Roosendaal's table is now complete through 2007 - _N. J. A. Sloane_, Oct 21 2012]
Eric Roosendaal, 3x+1 Class Records
Eric Weisstein's World of Mathematics, Collatz Problem
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A126727 (missing numbers).

Cf. A006577, A127824.

a033491 = head . a127824_row  -- Reinhard Zumkeller, Nov 29 2012

f[ n_ ] := Module[ {i = 0, m = n}, While[ m != 1, m = If[ OddQ[ m ], 3m + 1, m/2 ]; i++ ]; i ]; a = Table[ 0, {75} ]; Do[ m = f[ n ]; If[ a[[ m + 1 ]] == 0, a[[ m + 1 ]] = n ], {n, 1, 1250} ]; a
With[{c=Table[Length[NestWhileList[If[OddQ[#],3#+1,#/2]&,n,#!=1&]],{n,2000}]}, Flatten[Table[Position[c,i,1,1],{i,70}]]] (* Harvey P. Dale, Jan 06 2013 *)

a(n)=if(n<0,0,k=1; while(abs(if(k<0,0,s=k; c=1; while((1-(s%2))*s/2+(s%2)*(3*s+1)>1,s=(1-(s%2))*s/2+(s%2)*(3*s+1); c++); c)-n-1)>0,k++); k)

import numpy
nupto = 62
A033491 = numpy.zeros(nupto, dtype=object)
k, counter = 1, 0
while counter < nupto:
    kk, n = k, 0
    while n <= nupto and kk != 1:
        if kk % 2 == 0:
            kk //= 2
        else:
            kk = (kk*3+1)//2
            n += 1
        n += 1
    if n < nupto and not A033491[n]:
        A033491[n] = k
        counter += 1
    k += 1
print(list(A033491)) # Karl-Heinz Hofmann, Feb 11 2023

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

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

A354236 A(n,k) is the n-th number m such that the Collatz (or 3x+1) trajectory starting at m contains exactly k odd integers; square array A(n,k), n>=1, k>=1, read by antidiagonals.

Original entry on oeis.org

1, 5, 2, 3, 10, 4, 17, 6, 20, 8, 11, 34, 12, 21, 16, 7, 22, 35, 13, 40, 32, 9, 14, 23, 68, 24, 42, 64, 25, 18, 15, 44, 69, 26, 80, 128, 33, 49, 19, 28, 45, 70, 48, 84, 256, 43, 65, 50, 36, 29, 46, 75, 52, 85, 512, 57, 86, 66, 51, 37, 30, 88, 136, 53, 160, 1024

Offset: 1

Alois P. Heinz, May 20 2022

			Square array A(n,k) begins:
    1,   5,  3,  17, 11,  7,  9,  25,  33,  43, ...
    2,  10,  6,  34, 22, 14, 18,  49,  65,  86, ...
    4,  20, 12,  35, 23, 15, 19,  50,  66,  87, ...
    8,  21, 13,  68, 44, 28, 36,  51,  67,  89, ...
   16,  40, 24,  69, 45, 29, 37,  98, 130, 172, ...
   32,  42, 26,  70, 46, 30, 38,  99, 131, 173, ...
   64,  80, 48,  75, 88, 56, 72, 100, 132, 174, ...
  128,  84, 52, 136, 90, 58, 74, 101, 133, 177, ...
  256,  85, 53, 138, 92, 60, 76, 102, 134, 178, ...
  512, 160, 96, 140, 93, 61, 77, 196, 260, 179, ...

Alois P. Heinz, Rows n = 1..150, flattened
Wikipedia, Collatz Conjecture
Index entries for sequences related to 3x+1 (or Collatz) problem
Index entries for sequences that are permutations of the positive integers

Columns k=1-12 give: A011782, A062052, A062053, A062054, A062055, A062056, A062057, A062058, A062059, A062060, A072466, A072122.
Row n=1 gives A092893(k-1).
Main diagonal gives A380244.
Cf. A006577, A006667, A078719.

b:= proc(n) option remember; irem(n, 2, 'r')+
      `if`(n=1, 0, b(`if`(n::odd, 3*n+1, r)))
    end:
A:= proc() local h, p, q; p, q:= proc() [] end, 0;
      proc(n, k)
        if k=1 then return 2^(n-1) fi;
        while nops(p(k))

b[n_] := b[n] = Module[{q, r}, {q, r} = QuotientRemainder[n, 2]; r +
     If[n == 1, 0, b[If[OddQ[n], 3*n + 1, q]]]];
A = Module[{h, p, q}, p[_] = {}; q = 0;
     Function[{n, k}, If[k == 1, 2^(n - 1)];
     While[Length[p[k]] < n, q = q + 1;
        h = b[q];
        p[h] = Append[p[h], q]];
     p[k][[n]]]];
Table[Table[A[n, 1+d-n], {n, 1, d}], {d, 1, 12}] // Flatten (* Jean-François Alcover, Jun 02 2022, after Alois P. Heinz *)

A078719(A(n,k)) = k.

A006579 a(n) = Sum_{k=1..n-1} gcd(n,k).

Original entry on oeis.org

0, 1, 2, 4, 4, 9, 6, 12, 12, 17, 10, 28, 12, 25, 30, 32, 16, 45, 18, 52, 44, 41, 22, 76, 40, 49, 54, 76, 28, 105, 30, 80, 72, 65, 82, 132, 36, 73, 86, 140, 40, 153, 42, 124, 144, 89, 46, 192, 84, 145, 114, 148, 52, 189, 134, 204, 128, 113, 58, 300, 60, 121, 210, 192

Offset: 1

Marc LeBrun

nonn

This sequence for a(n) also arises in the following context. If f(x) is a monic univariate polynomial of degree d>1 over Zn (= Z/nZ, the ring of integers modulo n), and we let X be the number of distinct roots of f(x) in Zn taken over all n^d choices for f(x), then the variance Var[X] = a(n)/n and the expected value E[X] = 1. - Michael Monagan, Sep 11 2015

Conjecture: a(n) != -1 (mod n) for a composite n. - Thomas Ordowski, Jun 11 2025

			a(12) = gcd(12,1) + gcd(12,2) + ... + gcd(12,11) = 1 + 2 + 3 + 4 + 1 + 6 + 1 + 4 + 3 + 2 + 1 = 28.

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

Amiram Eldar, Table of n, a(n) for n = 1..10000 (terms 1..2000 from T. D. Noe)
Marc Le Brun, Email to N. J. A. Sloane, Jul 1991.
Michael Monagan and Baris Tuncer, Some results on counting roots of polynomials and the Sylvester resultant, arXiv:1609.08712 [math.CO], 2016.

Antidiagonal sums of array A003989.

Cf. A018804.

a:= n-> add(igcd(n, k), k=1..n-1):
seq(a(n), n=1..64);

f[n_] := Sum[ GCD[n, k], {k, 1, n - 1}]; Table[ f[n], {n, 1, 60}]
f[p_, e_] := (e*(p - 1)/p + 1)*p^e; a[n_] := Times @@ f @@@ FactorInteger[n] - n; Array[a, 100] (* Amiram Eldar, Apr 26 2023 *)

A006579(n) = sum(k=1,n-1,gcd(n,k)) \\ Michael B. Porter, Feb 23 2010

from math import prod
from sympy import factorint
def A006579(n): return prod(p**(e-1)*((p-1)*e+p) for p, e in factorint(n).items()) - n # Chai Wah Wu, May 15 2022

a(p) = p-1 for a prime p.
a(n) = A018804(n)-n = Sum_{ d divides n } (d-1)*phi(n/d). - Vladeta Jovovic, May 04 2002
a(n+2) = Sum_{k=0..n} gcd(n-k+1, k+1) = -Sum_{k=0..4n+2} gcd(4n-k+3, k+1)*(-1)^k/4. - Paul Barry, May 03 2005
G.f.: Sum_{k>=1} phi(k) * x^(2*k) / (1 - x^k)^2. - Ilya Gutkovskiy, Feb 06 2020
a(p^k) = k(p-1)p^(k-1) for prime p. - Chai Wah Wu, May 15 2022

More terms from Robert G. Wilson v, May 04 2002

Corrected by Ron Lalonde (ronronronlalonde(AT)hotmail.com), Oct 24 2002

A127885 a(n) = minimal number of steps to get from n to 1, where a step is x -> 3x+1 if x is odd, or x -> either x/2 or 3x+1 if x is even; or -1 if 1 is never reached.

Original entry on oeis.org

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

Offset: 1

David Applegate and N. J. A. Sloane, Feb 04 2007

nonn

In contrast to the "3x+1" problem (see A006577), here you are free to choose either step if x is even.

See A125731 for the number of steps in the reverse direction, from 1 to n.

			Several early values use the path:
6 -> 3 -> 10 -> 5 -> 16 -> 8 -> 4 -> 2 -> 1.
The first path where choosing 3x+1 for even x helps is:
9 -> 28 -> 85 -> 256 -> 128 -> 64 -> 32 -> 16 -> 8 -> 4 -> 2 -> 1.

M. J. Halm, Sequences (Re)discovered, Mpossibilities 81 (Aug. 2002), p. 1.

David Applegate, Table of n, a(n) for n = 1..1000
Index entries for sequences related to 3x+1 (or Collatz) problem

A127886 gives the difference between A006577 and this sequence.
Cf. A006577, A125731, A127887, A125195, A125686, A125719, A261870.
Cf. A290100 (size of the final set when using Alekseyev's algorithm).
Cf. also A257265.

# Code from David Applegate: Be careful - the function takes an iteration limit and returns the limit if it wasn't able to determine the answer (that is, if A127885(n,lim) == lim, all you know is that the value is >= lim). To use it, do manual iteration on the limit.
A127885 := proc(n,lim) local d,d2; options remember;
if (n = 1) then return 0; end if;
if (lim <= 0) then return 0; end if;
if (n > 2 ^ lim) then return lim; end if;
if (n mod 2 = 0) then
d := A127885(n/2,lim-1);
d2 := A127885(3*n+1,d);
if (d2 < d) then d := d2; end if;
else
d := A127885(3*n+1,lim-1);
end if;
return 1+d;
end proc;

Table[-1 + Length@ NestWhileList[Flatten[# /. {k_ /; OddQ@ k :> 3 k + 1, k_ /; EvenQ@ k :> {k/2, 3 k + 1}}] &, {n}, FreeQ[#, 1] &], {n, 126}] (* Michael De Vlieger, Aug 20 2017 *)

{ A127885(n) = my(S,k); S=[n]; k=0; while( S[1]!=1, k++; S=vecsort( concat(apply(x->3*x+1,S), apply(x->x\2, select(x->x%2==0,S) )),,8);  ); k } /* Max Alekseyev, Sep 03 2015 */

a(1) = 0; and for n > 1, if n is odd, a(n) = 1 + a(3n+1), and if n is even, a(n) = 1 + min(a(3n+1),a(n/2)). [But with a similar caveat as in A257265] - Antti Karttunen, Aug 20 2017

Escape clause added to definition by N. J. A. Sloane, Aug 20 2017

A006585 Egyptian fractions: number of solutions to 1 = 1/x_1 + ... + 1/x_n in positive integers x_1 < ... < x_n.

Original entry on oeis.org

1, 0, 1, 6, 72, 2320, 245765, 151182379

Offset: 1

N. J. A. Sloane

All denominators in the expansion 1 = 1/x_1 + ... + 1/x_n are bounded by A000058(n-1), i.e., 0 < x_1 < ... < x_n < A000058(n-1). Furthermore, for a fixed n, x_i <= (n+1-i)*(A000058(i-1)-1). - Max Alekseyev, Oct 11 2012

If on the other hand, x_k need not be unique, see A002966. - Robert G. Wilson v, Jul 17 2013

			The 6 solutions for n=4 are 2,3,7,42; 2,3,8,24; 2,3,9,18; 2,3,10,15; 2,4,5,20; 2,4,6,12.

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

M. Le Brun, Email to N. J. A. Sloane, Jul 1991
S. V. Konyagin, Double exponential lower bound for the number of representations of unity by Egyptian fractions. Mathematical Notes, 95:1-2 (2014), 277-281.
T. D. Browning and C. Elsholtz, The number of representations of rationals as a sum of unit fractions, Illinois J. Math. 55:2 (2011), 685-696.
Joel Louwsma, On solutions of Sum_{i=1..n} 1/x_i = 1 in integers of the form 2^a*k^b, where k is a fixed odd positive integer, arXiv:2402.09515 [math.NT], 2024.
Index entries for sequences related to Egyptian fractions

Cf. A000058, A002966, A002967, A280518.

a(n) = A280520(n,1).

a(1)-a(7) are confirmed by Jud McCranie, Dec 11 1999

a(8) from John Dethridge (jcd(AT)ms.unimelb.edu.au), Jan 08 2004

A008884 3x+1 sequence starting at 27.

Original entry on oeis.org

27, 82, 41, 124, 62, 31, 94, 47, 142, 71, 214, 107, 322, 161, 484, 242, 121, 364, 182, 91, 274, 137, 412, 206, 103, 310, 155, 466, 233, 700, 350, 175, 526, 263, 790, 395, 1186, 593, 1780, 890, 445, 1336, 668, 334, 167, 502, 251, 754, 377, 1132, 566, 283, 850, 425, 1276, 638, 319, 958, 479, 1438, 719, 2158, 1079

Offset: 0

N. J. A. Sloane

27=A060412(4); a(A006577(27))=a(111)=1; a(n)=A161021(n+59) for n with 103<=n<=111. - Reinhard Zumkeller, Jun 03 2009

At step 109 enters the loop 4 2 1 4 2 1 4 2 1 ... - N. J. A. Sloane, Jul 27 2019

R. K. Guy, Unsolved Problems in Number Theory, E16.
H.-O. Peitgen et al., Chaos and Fractals, Springer, p. 33.

T. D. Noe, Table of n, a(n) for n = 0..111
F. Oort, Prime numbers, 2013, ICCM Notices, Talk at Academia Sinica and National Taiwan University, 17-XII-2012.
Index entries for sequences related to 3x+1 (or Collatz) problem
Index entries for linear recurrences with constant coefficients, signature (0,0,1).

Cf. A161022, A161023.

Row 27 of A347270.

[ n eq 1 select 27 else IsOdd(Self(n-1)) select 3*Self(n-1)+1 else Self(n-1) div 2: n in [1..70] ]; // Klaus Brockhaus, Dec 25 2010

f := proc(n) option remember; if n = 0 then 27; elif f(n-1) mod 2 = 0 then f(n-1)/2 else 3*f(n-1)+1; fi; end;

NestList[If[EvenQ[#],#/2,3#+1]&,27,70] (* Harvey P. Dale, Jun 30 2011 *)

Collatz(n,lim=0)={
my(c=n,e=0,L=List(n)); if(lim==0, e=1; lim=n*10^6);
for(i=1,lim, if(c%2==0, c=c/2, c=3*c+1); listput(L,c); if(e&&c==1, break));
return(Vec(L)); }
print(Collatz(27)) \\ A008884 (from 27 to the first 1)
\\ Anatoly E. Voevudko, Mar 26 2016

a(0) = 27, a(n) = 3*a(n-1)+1 if a(n-1) is odd, a(n) = a(n-1)/2 if a(n-1) is even. - Vincenzo Librandi, Dec 24 2010; corrected by Klaus Brockhaus, Dec 25 2010

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

A135282 Largest k such that 2^k appears in the trajectory of the Collatz 3x+1 sequence started at n.

Original entry on oeis.org

0, 1, 4, 2, 4, 4, 4, 3, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 6, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 5, 4, 4, 4, 4, 4, 4, 4, 4, 4, 6, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 6, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 8, 4, 4, 4, 4, 4, 4, 4, 4, 6, 8, 4, 4

Offset: 1

Masahiko Shin, Dec 02 2007

nonn

Most of the first eighty terms in the sequence are 4, because the trajectories finish with 16 -> 8 -> 4 -> 2 -> 1. - R. J. Mathar, Dec 12 2007
Most of the first ten thousand terms are 4, and there only appear 4, 6, 8, and 10 in the extent, unless n is power of 2. In the other words, it seems that the trajectory of the Collatz 3x + 1 sequence ends with either 16, 64, 256 or 1024. There are few exceptional terms, for example a(10920) = 12, a(10922) = 14. It also seems all terms are even unless n is an odd power of 2. - Masahiko Shin, Mar 16 2010
It is true that all terms are even unless n is an odd power of 2: 2 == -1 mod 3, 2 * 2 == -1 * -1 == 1 mod 3. Therefore only even-indexed powers of 2 are congruent to 1 mod 3 and thus reachable by either a halving step or a "tripling step," whereas the odd-indexed powers of 2 are only reachable by a halving step or as an initial value. - Alonso del Arte, Aug 15 2010

			a(6) = 4 because the sequence is 6, 3, 10, 5, 16, 8, 4, 2, 1; there 16 = 2^4 is the largest power of 2 encountered.

Cf. A007814, A209229, A070165, A232503.

Cf. A006577, A208981.

#include  int main(){ int i, s, f; for(i = 2; i < 10000; i++){ f = 0; s = i; while(s != 1){ if(s % 2 == 0){ s = s/2; f++;} else{ f = 0; s = 3 * s + 1; } } printf("%d,", f); } return 0; } /* Masahiko Shin, Mar 16 2010 */

a135282 = a007814 . head . filter ((== 1) . a209229) . a070165_row
-- Reinhard Zumkeller, Jan 02 2013

A135282 := proc(n) local k,threen1 ; k := 0 : threen1 := n ; while threen1 > 1 do if 2^ilog[2](threen1) = threen1 then k := max(k,ilog[2](threen1)) ; fi ; if threen1 mod 2 = 0 then threen1 := threen1/2 ; else threen1 := 3*threen1+1 ; fi ; od: RETURN(k) ; end: for n from 1 to 80 do printf("%d, ",A135282(n)) ; od: # R. J. Mathar, Dec 12 2007

Collatz[n_] := If[EvenQ[n], n/2, 3*n + 1]; Log[2, Table[NestWhile[Collatz, n, ! IntegerQ[Log[2, #]] &], {n, 100}]] (* T. D. Noe, Mar 05 2012 *)

a(n) = A006577(n) - A208981(n) (after Alonso del Arte's comment in A208981), if A006577(n) is not -1. - Omar E. Pol, Apr 10 2022

Edited and extended by R. J. Mathar, Dec 12 2007

More terms from Masahiko Shin, Mar 16 2010

cp's OEIS Frontend

A001281 Image of n under the map n->n/2 if n even, n->3n-1 if n odd.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A127824 Triangle in which row n is a sorted list of all numbers having total stopping time n in the Collatz (or 3x+1) iteration.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Mathematica

Formula

A033491 a(n) is the smallest integer that takes n halving and tripling steps to reach 1 in the 3x+1 problem.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Haskell

Mathematica

PARI

Python

Extensions

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

A354236 A(n,k) is the n-th number m such that the Collatz (or 3x+1) trajectory starting at m contains exactly k odd integers; square array A(n,k), n>=1, k>=1, read by antidiagonals.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A006579 a(n) = Sum_{k=1..n-1} gcd(n,k).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Python

Formula

Extensions