A005186 -id:A005186 - cp's OEIS frontend

A060322 Consider the version of the Collatz or 3x+1 problem where x -> x/2 if x is even, x -> (3x+1)/2 if x is odd. Define the stopping time of x to be the number of steps needed to reach 1. Sequence gives the number of integers x with stopping time n.

1, 1, 1, 1, 2, 3, 4, 5, 6, 8, 12, 18, 24, 31, 39, 50, 68, 91, 120, 159, 211, 282, 381, 505, 665, 885, 1187, 1590, 2122, 2829, 3765, 5014, 6682, 8902, 11878, 15844, 21122, 28150, 37536, 50067, 66763, 89009, 118631, 158171, 210939, 281334, 375129, 500106, 666725

Offset: 1

Bo T. Ahlander (ahlboa(AT)isk.kth.se), Mar 29 2001

nonn

The Mathematica function StoppingTime[n] is the length of the Collatz sequence starting at n before reaching 1.
Suppose we have a list L of the numbers with StoppingTime n. Then the list LL of StoppingTime n+1 can be produced as: First. Add to LL all numbers in L multiplied by 2. Second. For the numbers x now in LL, if x == 1 (mod 3), AppendTo LL the number (x-1)/3 (if (x-1)/3 != 1). These two steps make LL complete.
I think the offset, examples, formula and code are all off by 1 -- they all treat the stopping time of 1 to be 1, rather than 0. - David Applegate, Oct 16 2008
a(n+1), n >= 0, is the row length of A248573(n,m) (Collatz-Terras tree). For the first differences see A131450(n+1), but with A131450(2) = 1 (the number of 2 (mod 3) numbers in row n, for n >= 0, of A248573). - Wolfdieter Lang, May 04 2015

			StoppingTime = 1: L = {1}, a(1)=1.
StoppingTime = 2: L = {2}, a(2)=1.
StoppingTime = 3: L = {4}, a(3)=1.
StoppingTime = 4: L = {8}, a(4)=1.
StoppingTime = 5: L = {5, 16}, a(5)=2. First, LL = {10, 32} (= 2*L). Second, 10 == 1 (mod 3), so we AppendTo LL also (10-1)/3 = 3. We get LL = {3, 10, 32}. So a(6) = 3.

See A005186 for another version.

Cf. A248573, A131450.

(*** Program #1 ***) For[v = 1, v <= 12, v++, lst = {}; For[n = 1, n < 2^v, n++, If[StoppingTime[n] == v, AppendTo[lst, n]]]; Print[lst]; Print[Length[lst]]; ]
(*** Program #2 ***) lst1 = {1}; For[v = 1, v <= 12, v++, L1 = Length[lst1]; Print["Number of numbers with StoppingTime ", v, ": ", L1]; Print["List of numbers: ", lst1]; (* Numbers with StoppingTime n *) Print["Control of StoppingTime: ", Map[StoppingTime, lst1]]; (* Controll *) Print[""]; lst2 = 2 lst1; For[i = 1, i <= L1, i++, x = (lst2[[i]] - 1)/3; If[IntegerQ[x] && x != 1, AppendTo[lst2, x]]; ]; lst1 = Sort[lst2]; ]
(*** Program #3 ***) lst0 = {}; lst1 = {1}; For[v = 1, v <= 35, v++, L1 = Length[lst1]; AppendTo[lst0, L1]; lst2 = 2 lst1; For[i = 1, i <= L1, i++, x = (lst2[[i]] - 1)/3; If[IntegerQ[x], AppendTo[lst2, x]]; ]; lst1 = Complement[lst2, {1}]; ]; lst0

first(N) = my(a=Vec([1, 1, 1, 1, 2], N), p=[], q=[5]); for(n=6, N, my(r=List()); foreach(p, x, listput(r, 4*x+1); if(1==x%6, listput(r, x+(x-1)/3))); foreach(q, x, if(5==x%6, listput(r, x-(x+1)/3))); a[n]=a[n-1]+#r; p=q; q=Vec(r)); a; \\ Ruud H.G. van Tol, Aug 14 2024

# code to calculate terms after a(4):
@x=(8,0);for($n=5;$n<=60;$n++){do{$q=2*shift(@x);push(@x,($q-1)/3)if($q%3==1);push @x,$q}while $q;print($#x,", ");} # Carl R. White, Oct 03 2006

Conjecture: lim_{n->oo} a(n) = a(n-1)*4/3. - Joe Slater, Jan 27 2024

More terms from Carl R. White, Oct 03 2006
Edited by N. J. A. Sloane, Sep 15 2007
More terms from Joe Slater, Apr 10 2025

A220145 The Collatz (3x+1) iteration mod 2 with bits combined.

Original entry on oeis.org

1, 10, 10000101, 100, 100001, 100001010, 10000100010010101, 1000, 10000100010010101001, 1000010, 100001000100101, 1000010100, 1000010001, 100001000100101010, 100001000001010101, 10000, 1000010001001, 100001000100101010010, 100001000100101000101, 10000100

Offset: 1

T. D. Noe, Jan 17 2013

This is essentially sequence A070165 mod 2 with bits in the same iteration combined. Note that A176999 is similar, but with a different encoding.

It appears that all numbers are distinct. Sequence A005186 tells how many numbers produce bit strings of a given length. Sequence A221468 converts to decimal and A221467 sorts them.

			For n = 7, the Collatz iteration is 7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1. Looking at these numbers in base 2 and reversing them, we obtain 10000100010010101.

T. D. Noe, Table of n, a(n) for n = 1..10000

Cf. A005186, A070165, A176999, A221467, A221468.

Collatz[n_] := NestWhileList[If[EvenQ[#], #/2, 3 # + 1] &, n, # > 1 &]; Table[FromDigits[Mod[Reverse[Collatz[n]], 2]], {n, 30}]

A176999 An encoding of the Collatz iteration of n.

Original entry on oeis.org

1, 1111010, 11, 11110, 11110101, 1111011101101010, 111, 1111011101101010110, 111101, 11110111011010, 111101011, 111101110, 11110111011010101, 11110111110101010, 1111, 111101110110, 11110111011010101101, 11110111011010111010, 1111011, 1111110, 111101110110101

Offset: 2

T. D. Noe, Apr 30 2010

Working from right to left, the sequence of 0's and 1's in a(n) encode, respectively, the sequence of 3x+1 and x/2 steps in the Collatz iteration of n. This is reverse one's complement of Garner's parity vector. Criswell mentions this encoding.

The length of a(n) is A006577(n). The number of 1's in a(n) is A006666(n). The number of 0's in a(n) is A006667(n). The number of terms having length k is A005186(k).

			a(5)=11110 because the Collatz iteration for 5 is a 3x+1 step (0) followed by 4 x/2 steps (four 1's).

T. D. Noe, Table of n, a(n) for n = 2..10000
Evans A. Criswell, The Collatz Problem (3x+1)
Lynn E. Garner, On heights in the Collatz 3n+1 problem, Discrete Math, 55 (1985), 57-64.

Cf. A006577, A006666, A006667, A005186.

Cf. A220145, A260592.

encode[n_]:=Module[{m=n,p,lst={}}, While[m>1, p=Mod[m,2]; AppendTo[lst,1-p]; If[p==0, m=m/2, m=3m+1]]; FromDigits[Reverse[lst]]]; Table[encode[n], {n,2,26}]

A337144 n is the a(n)-th positive integer which takes its number of steps to reach 1 in the Collatz (or 3x+1) problem.

Original entry on oeis.org

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 1, 1, 1, 2, 2, 3, 1, 2, 1, 1, 2, 1, 1, 2, 3, 1, 2, 1, 1, 2, 1, 2, 3, 1, 2, 1, 3, 1, 2, 3, 4, 1, 1, 1, 2, 3, 2, 3, 1, 2, 2, 1, 3, 2, 4, 5, 1, 2, 2, 1, 2, 3, 2, 3, 4, 1, 1, 1, 2, 5, 3, 4, 1, 2, 3, 5, 1, 2, 4, 5, 1, 2

Offset: 1

Alois P. Heinz, Jan 27 2021

			a(13) = 2 because A006577(13) = A006577(12) = 9 != A006577(j) for j < 12.

Alois P. Heinz, Table of n, a(n) for n = 1..65536
Wikipedia, Collatz Conjecture
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A005186, A006577, A380244.

collatz:= proc(n) option remember; `if`(n=1, 0,
   1 + collatz(`if`(n::even, n/2, 3*n+1)))
end:
b:= proc() 0 end:
a:= proc(n) option remember; local t;
     `if`(n=1, 0, a(n-1));
      t:= collatz(n); b(t):= b(t)+1
    end:
seq(a(n), n=1..120);

collatz[n_] := collatz[n] = If[n == 1, 0,
   1 + collatz[If[EvenQ[n], n/2, 3n+1]]];
b[_] = 0;
a[n_] := a[n] = Module[{t},
   If[n == 1, 0, a[n-1]];
   t = collatz[n]; b[t] = b[t]+1];
Array[a, 120] (* Jean-François Alcover, Jan 29 2021, after Alois P. Heinz *)

Ordinal transform of A006577.

a(n) = |{ j in {1..n} : A006577(j) = A006577(n) }|.

A341218 a(n) is the number of numbers k such that A340873(k) = n.

Original entry on oeis.org

1, 1, 1, 2, 3, 4, 6, 8, 11, 15, 21, 29, 40, 54, 74, 102, 139, 189, 259, 355, 486, 664, 908, 1242, 1697, 2317, 3165, 4326, 5911, 8076, 11034, 15073, 20588, 28125, 38415, 52477, 71692, 97931, 133774, 182739, 249634, 341013, 465839, 636346, 869279, 1187486

Offset: 0

Rémy Sigrist, Feb 07 2021

			The first terms, alongside the correspond k's, are:
   n  a(n)  k's
   -  ----  ----------------------
   0     1              1
                        |
   1     1              2
                        |
   2     1              4
                       / \
   3     2            3   8
                     /   / \
   4     3          6   7   16
                   /   /   /  \
   5     4       12  14  15    32

Rémy Sigrist, PARI program for A341218
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A005186, A340873.

PARI
```
See Links section.
```

a(n) <= a(n+1) <= 2*a(n).

A221468 The Collatz (3x+1) iteration in A220145 converted to decimal.

Original entry on oeis.org

1, 2, 133, 4, 33, 266, 67733, 8, 541865, 66, 16933, 532, 529, 135466, 135253, 16, 4233, 1083730, 1083717, 132, 129, 33866, 33813, 1064, 8669737, 1058, 2678946987458595510314019806849701, 270932, 270929, 270506, 83717093358081109697313118964053, 32, 69357897

Offset: 1

T. D. Noe, Jan 17 2013

Sequence A005186 tells how many of these numbers are in [2^n, 2^(n+1)-1].
From Rémy Sigrist, Aug 19 2017: (Start)
a(2^n) = 2^n for any n >= 0.
A000120(a(n)) - 1 = A006667(n) for any n > 0.
A070939(a(n)) - 1 = A006577(n) for any n > 0.
All terms are Fibbinary numbers (A003714).
(End)

Cf. A000120, A003714, A005186, A006577, A006667, A070939, A220145.

Table[FromDigits[#, 2] &@ Boole@ OddQ@ Reverse@ NestWhileList[If[EvenQ@ #, #/2, 3 # + 1] &, n, # > 1 &], {n, 33}] (* Michael De Vlieger, Aug 19 2017 *)

a(n) = my (v=0, p=1); while (n>1, if (n%2, n = 3*n+1; v += p, n = n/2); p *= 2); return (p+v) \\ Rémy Sigrist, Aug 19 2017

A375094 a(n) is the least number not occurring in a Collatz trajectory of n steps.

Original entry on oeis.org

2, 3, 3, 3, 3, 3, 3, 6, 7, 7, 7, 7, 7, 7, 7, 7, 9, 9, 9, 18, 25, 25, 25, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27, 27

Offset: 0

Markus Sigg and Hugo Pfoertner, Aug 03 2024

A006877 and A288493 form a run-length encoding of this sequence: It starts with A288493(1) copies of A006877(2), followed by A288493(2) copies of A006877(3), followed by A288493(3) copies of A006877(4), and so on.

			a(5) = 3 because there are two trajectories with 5 steps, namely (32,16,8,4,2,1) and (5,16,8,4,2,1). 3 is the smallest number not appearing in both.

Markus Sigg and Hugo Pfoertner, Table of n, a(n) for n = 0..2441
Wikipedia, Collatz Conjecture
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A005186, A006877, A127824, A288493.

# output in b-file format
from itertools import count
n = 0
for k in count():
    m = k
    s = 0
    while m > 1:
        m = m // 2 if m % 2 == 0 else 3*m+1
        s += 1
    while n < s:
        print(n, k, flush=True)
        n += 1

A221467 The Collatz (3x+1) iteration in A220145 sorted and converted to decimal.

Original entry on oeis.org

1, 2, 4, 8, 16, 32, 33, 64, 66, 128, 129, 132, 133, 256, 258, 264, 266, 512, 513, 516, 528, 529, 532, 1024, 1026, 1032, 1056, 1058, 1064, 2048, 2049, 2052, 2064, 2112, 2113, 2116, 2128, 4096, 4098, 4104, 4105, 4128, 4224, 4226, 4232, 4233, 4256, 8192, 8193

Offset: 1

T. D. Noe, Jan 17 2013

Sequence A005186 tells how many of these numbers are in [2^n, 2^(n+1)-1].

A337673 a(n) is the sum of all positive integers whose Collatz orbit has length n.

Original entry on oeis.org

0, 1, 2, 4, 8, 16, 37, 74, 172, 344, 786, 1572, 3538, 7206, 16252, 33112, 73762, 149967, 330107, 678610, 1498356, 3082302, 6742487, 13855154, 30122440, 62388962, 135783788, 281177482, 608402189, 1259151448, 2711432766, 5646008216, 12172417990, 25339969480, 54409676729, 113159496364

Offset: 0

Markus Sigg, Sep 15 2020

nonn

a(n) >= 2^(n-1) as 2^(n-1) has orbit length n.

			a(6) = 5+32 = 37 as the positive integers whose Collatz orbit has length 6 are {5,32} - the orbit of 5 is 5,16,8,4,2,1, and the orbit of 32 is 32,16,8,4,2,1.

Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A000975, A005186, A153772.

Equals row sums of triangles A088975 and A127824.

nextSet(s) = { my(s1 = Set([])); for(i = 1, #s, s1 = setunion(s1, Set([2*s[i]])); if (s[i] > 4 && (s[i]-1) % 3 == 0 && (s[i]-1)/3 % 2 == 1, s1 = setunion(s1, Set([(s[i]-1)/3]))); ); return(s1); }
a(n) = { my(s = Set([1])); for(k = 1, n, s = nextSet(s); ); return(sum(i=1,#s,s[i])); }

More terms from David A. Corneth, Sep 15 2020

A268338 Numbers that cycle under the following transformation: if m is even, divide by 2, if m is congruent to 1 mod 4, multiply by 3 and add 1; if m is congruent to 3 mod 4, multiply by 7 and add 1.

Original entry on oeis.org

1, 2, 4, 19, 23, 31, 38, 41, 46

Offset: 1

David Consiglio, Jr., Feb 01 2016

Some numbers appear to grow indefinitely under these rules, but it is possible that they may eventually cycle at some point. All numbers up to 50 either cycle or transform to another number that cycles (typically 1). 51 is the first open case: it may eventually cycle or may continue to grow indefinitely.

			23 is a member of this sequence. 23 is congruent to 3 mod 4.  As a result, 23 transforms to 23*7+1 = 162.  From there 162 -> 81 -> 244 -> 122 -> 61 -> 184 -> 92 -> 46 -> 23.  23 is the least member of this cycle.
49 is not a member of this sequence because it eventually reduces to 19, which cycles.

Cf. A267703, A267970, A267969, A006666, A006370, A005186, A267970, A232711.

a = 1
b = 1
prev = []
keep = []
count = 0
while b < 51:
    keep.append(a)
    flag1 = False
    flag2 = False
    if a % 2 == 0:
        a /= 2
    elif a % 4 == 1:
        a = a*3+1
    else:
        a = a*7+1
    if count > 50:
        b += 1
        a = b
        count = 0
        keep = []
    if keep.count(a) == 2 and a not in prev and a <= 50:
        prev.append(a)
        count = 0
        keep = []
        b += 1
        a = b
    count += 1
print(sorted(prev))
# David Consiglio, Jr., Feb 01 2016

Corrected and edited by David Consiglio, Jr., Apr 20 2016

cp's OEIS Frontend

A060322 Consider the version of the Collatz or 3x+1 problem where x -> x/2 if x is even, x -> (3x+1)/2 if x is odd. Define the stopping time of x to be the number of steps needed to reach 1. Sequence gives the number of integers x with stopping time n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Perl

Formula

Extensions

A220145 The Collatz (3x+1) iteration mod 2 with bits combined.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A176999 An encoding of the Collatz iteration of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A337144 n is the a(n)-th positive integer which takes its number of steps to reach 1 in the Collatz (or 3x+1) problem.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A341218 a(n) is the number of numbers k such that A340873(k) = n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Formula

A221468 The Collatz (3x+1) iteration in A220145 converted to decimal.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

A375094 a(n) is the least number not occurring in a Collatz trajectory of n steps.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

A221467 The Collatz (3x+1) iteration in A220145 sorted and converted to decimal.

Views

Author

Keywords