A286380 -id:A286380 - cp's OEIS frontend

A078719 Number of odd terms among n, f(n), f(f(n)), ...., 1 for the Collatz function (that is, until reaching "1" for the first time), or -1 if 1 is never reached.

1, 1, 3, 1, 2, 3, 6, 1, 7, 2, 5, 3, 3, 6, 6, 1, 4, 7, 7, 2, 2, 5, 5, 3, 8, 3, 42, 6, 6, 6, 40, 1, 9, 4, 4, 7, 7, 7, 12, 2, 41, 2, 10, 5, 5, 5, 39, 3, 8, 8, 8, 3, 3, 42, 42, 6, 11, 6, 11, 6, 6, 40, 40, 1, 9, 9, 9, 4, 4, 4, 38, 7, 43, 7, 4, 7, 7, 12, 12, 2, 7, 41, 41, 2, 2, 10, 10, 5, 10, 5, 34, 5, 5, 39

Offset: 1

Joseph L. Pe, Dec 20 2002

nonn

The Collatz function (related to the "3x+1 problem") is defined by: f(n) = n/2 if n is even; f(n) = 3n + 1 if n is odd. A famous conjecture states that n, f(n), f(f(n)), .... eventually reaches 1.
a(n) = A006667(n) + 1; a(A000079(n))=1; a(A062052(n))=2; a(A062053(n))=3; a(A062054(n))=4; a(A062055(n))=5; a(A062056(n))=6; a(A062057(n))=7; a(A062058(n))=8; a(A062059(n))=9; a(A062060(n))=10. - Reinhard Zumkeller, Oct 08 2011
The count includes also the starting value n if it is odd. See A286380 for the version which never includes n itself. - Antti Karttunen, Aug 10 2017

			The terms n, f(n), f(f(n)), ...., 1 for n = 12 are: 12, 6, 3, 10, 5, 16, 8, 4, 2, 1, of which 3 are odd. Hence a(12) = 3.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Chris K. Caldwell and G. L. Honaker, Jr., Prime curio for 41 (which says 41 is a fixed point)
Eric Weisstein's World of Mathematics, Collatz Problem
Wikipedia, Collatz conjecture
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A006370, A014682, A078720, A139391, A286380.

Cf. A258145, A003602.

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

a:= proc(n) option remember; `if`(n<2, 1,
      `if`(n::even, a(n/2), 1+a(3*n+1)))
    end:
seq(a(n), n=1..94);  # Alois P. Heinz, Jan 17 2025

f[n_] := Module[{a, i, o}, i = n; o = 1; a = {}; While[i > 1, If[Mod[i, 2] == 1, o = o + 1]; a = Append[a, i]; i = f[i]]; o]; Table[f[i], {i, 1, 100}]
Table[Count[NestWhileList[If[EvenQ[#], #/2, 3 # + 1] &, n, # > 1 &], ?OddQ], {n, 94}] (* _Jayanta Basu, Jun 15 2013 *)

a(n) = {my(x=n, v=List([])); while(x>1, if(x%2==0, x=x/2, listput(v, x); x=3*x+1)); 1+#v;} \\ Jinyuan Wang, Dec 29 2019

a(n) = A286380(n) + A000035(n). - Antti Karttunen, Aug 10 2017

a(n) = A258145(A003602(n)-1). - Alan Michael Gómez Calderón, Sep 15 2024

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

A352893 Number of iterations of map x -> A352892(x) needed to reach x <= 2 when starting from x=n, or -1 if such number is never reached. Here A352892 is the next odd term in the Collatz or 3x+1 map (A139391) conjugated by unary-binary-encoding (A156552).

Original entry on oeis.org

0, 0, 1, 2, 1, 1, 1, 5, 3, 6, 1, 4, 1, 3, 2, 5, 1, 2, 1, 6, 7, 8, 1, 4, 3, 8, 6, 3, 1, 1, 1, 39, 4, 44, 2, 41, 1, 44, 9, 11, 1, 6, 1, 8, 5, 10, 1, 38, 3, 7, 9, 8, 1, 5, 7, 37, 45, 10, 1, 9, 1, 56, 7, 39, 4, 3, 1, 44, 45, 40, 1, 41, 1, 39, 3, 44, 2, 8, 1, 11, 6, 15, 1, 3, 9, 15, 11, 13, 1, 4, 7, 10, 11, 32, 9, 38

Offset: 1

Antti Karttunen, Apr 08 2022

nonn

Antti Karttunen, Table of n, a(n) for n = 1..16384
Antti Karttunen, Data supplement: n, a(n) computed for n = 1..65537
Index entries for sequences related to 3x+1 (or Collatz) problem
Index entries for sequences computed from indices in prime factorization

Cf. A000040, A005940, A064989, A139391, A156552, A286380, A329603, A341515, A352890, A352892, A352894.

A005940(n) = { my(p=2, t=1); n--; until(!n\=2, if((n%2), (t*=p), p=nextprime(p+1))); (t); };
A064989(n) = {my(f); f = factor(n); if((n>1 && f[1,1]==2), f[1,2] = 0); for (i=1, #f~, f[i,1] = precprime(f[i,1]-1)); factorback(f)};
A156552(n) = { my(f = factor(n), p, p2 = 1, res = 0); for(i = 1, #f~, p = 1 << (primepi(f[i, 1]) - 1); res += (p * p2 * (2^(f[i, 2]) - 1)); p2 <<= f[i, 2]); res };
A329603(n) = A005940(2+(3*A156552(n)));
A341515(n) = if(n%2, A064989(n), A329603(n));
A348717(n) = { my(f=factor(n)); if(#f~>0, my(pi1=primepi(f[1, 1])); for(k=1, #f~, f[k, 1] = prime(primepi(f[k, 1])-pi1+1))); factorback(f); }; \\ From A348717
A352892(n) = A348717(A341515(n));
A352893(n) = { my(k=0); while(n>2, n = A352892(n); k++); (k); };

\\ Much faster than above program:
A139391(n) = my(x = if(n%2, 3*n+1, n/2)); x/2^valuation(x, 2); \\ From A139391
A286380(n) = { my(k=0); while(n>1, n = A139391(n); k++); (k); };
A352893(n) = if(1==n,0,A286380(A156552(n)));

If n <= 2, a(n) = 0, otherwise a(n) = 1 + a(A352892(n)).
For n > 1, a(n) = A286380(A156552(n)).
a(p) = 1 for all odd primes p.
For n >= 1, A352894(n) <= a(n) <= A352890(n).

A352894 Number of iterations of map x -> A352892(x) needed to reach x < n when starting from x=n, or 0 if such number is never reached. Here A352892 is the next odd term in the Collatz or 3x+1 map (A139391) conjugated by unary-binary-encoding (A156552).

Original entry on oeis.org

0, 0, 1, 2, 1, 1, 1, 4, 1, 1, 1, 3, 1, 2, 1, 4, 1, 1, 1, 2, 1, 2, 1, 3, 1, 3, 1, 2, 1, 1, 1, 35, 1, 40, 1, 2, 1, 5, 1, 5, 1, 1, 1, 2, 1, 6, 1, 34, 1, 1, 1, 2, 1, 1, 1, 33, 1, 6, 1, 1, 1, 17, 1, 35, 1, 1, 1, 6, 1, 1, 1, 3, 1, 35, 1, 4, 1, 1, 1, 5, 1, 10, 1, 3, 1, 10, 1, 4, 1, 1, 1, 6, 1, 24, 1, 34, 1, 1, 1, 2, 1

Offset: 1

Antti Karttunen, Apr 08 2022

nonn

Cf. A000040, A005940, A064989, A139391, A156552, A286380, A329603, A341515, A352890, A352891, A352892, A352893.

A005940(n) = { my(p=2, t=1); n--; until(!n\=2, if((n%2), (t*=p), p=nextprime(p+1))); (t); };
A064989(n) = {my(f); f = factor(n); if((n>1 && f[1,1]==2), f[1,2] = 0); for (i=1, #f~, f[i,1] = precprime(f[i,1]-1)); factorback(f)};
A156552(n) = { my(f = factor(n), p, p2 = 1, res = 0); for(i = 1, #f~, p = 1 << (primepi(f[i, 1]) - 1); res += (p * p2 * (2^(f[i, 2]) - 1)); p2 <<= f[i, 2]); res };
A329603(n) = A005940(2+(3*A156552(n)));
A341515(n) = if(n%2, A064989(n), A329603(n));
A348717(n) = { my(f=factor(n)); if(#f~>0, my(pi1=primepi(f[1, 1])); for(k=1, #f~, f[k, 1] = prime(primepi(f[k, 1])-pi1+1))); factorback(f); }; \\ From A348717
A352892(n) = A348717(A341515(n));
A352894(n) = if(n<=2, 0, my(k=0,x=n); while(x>=n, x = A352892(x); k++); (k));

a(2n+1) = 1 for n >= 1.
For n >= 1, a(n) <= A352891(n).
For n >= 1, a(n) <= A352893(n).

A160541 Number of odd-then-even runs to reach 1 from n under the modified "3x+1" map: x -> x/2 if x is even, x -> (3x+1)/2 if x is odd.

Original entry on oeis.org

0, 1, 1, 1, 1, 2, 3, 1, 4, 2, 3, 2, 2, 4, 2, 1, 3, 5, 4, 2, 1, 4, 2, 2, 5, 3, 17, 4, 4, 3, 16, 1, 6, 4, 2, 5, 4, 5, 6, 2, 17, 2, 6, 4, 4, 3, 16, 2, 5, 6, 5, 3, 2, 18, 17, 4, 7, 5, 6, 3, 3, 17, 15, 1, 6, 7, 5, 4, 3, 3, 16, 5, 18, 5, 2, 5, 5, 7, 6, 2, 4, 18, 17

Offset: 1

Brenton Bostick (bostick(AT)gmail.com), May 18 2009

nonn

The 2->1 step is not counted.
From Dustin Theriault, May 24 2023: (Start)
The ratio of the partial sum of a(n) to the partial sum of A006577(n) appears to approach 1/6 (observation for n = 1..10^10).
The ratio of the partial sum of a(n) to the partial sum of A286380(n) appears to approach 1/2 (observation for n = 1..10^10). (End)
Number of steps x -> A363270(x) to go from n to 1. - Dustin Theriault, Jul 09 2023

			7->11->17->26->13->20->10->5->8->4->2->1, so the odd-then-even runs are (7->11->17->26) (13->20->10) (5->8->4->2), and a(7) is 3.

Michael De Vlieger, Table of n, a(n) for n = 1..10000
Francis Laclé, 2-adic parity explorations of the 3n+1 problem, hal-03201180v2 [cs.DM], 2021.
Dustin Theriault, Ratio between the partial sum of a(n) to the partial sum of A006577(n), for n = 1..10^10.
Dustin Theriault, Ratio between the partial sum of a(n) to the partial sum of A286380(n), for n = 1..10^10.
Dustin Theriault, Histogram of a(n), for n = 1..10^10.
Dustin Theriault, Combined histograms of A006577, A286380, A160541, for n = 1..10^9.

Cf. A006577, A286380, A363270.

int a(int n) {
  int steps = 0;
  while (n > 1) {
    while (n & 1) n += (n >> 1) + 1;
    while (!(n & 1)) n >>= 1;
    ++steps;
  }
  return steps;
} /* Dustin Theriault, May 23 2023 */

Array[Length@ Split[Most@ NestWhileList[If[EvenQ@ #, #/2, (3 # + 1)/2] &, #, # > 1 &], Or[OddQ[#1], EvenQ[#2]] &] &, 120] (* Corrected by Michael De Vlieger, Jul 19 2021 *)

From Alan Michael Gómez Calderón, Mar 19 2025: (Start)
a(n) = A346965(A000265(n)) - (n mod 2) + 1;
a(n) = a(A363270(n)) + 1 for n >= 2. (End)

A334040 Number of odd numbers larger than n in the Collatz trajectory of n.

Original entry on oeis.org

0, 0, 1, 0, 0, 0, 3, 0, 3, 0, 2, 0, 0, 1, 3, 0, 0, 0, 1, 0, 0, 0, 2, 0, 1, 0, 38, 0, 0, 2, 36, 0, 0, 0, 1, 0, 0, 0, 4, 0, 35, 0, 2, 0, 0, 1, 34, 0, 0, 0, 1, 0, 0, 33, 35, 0, 1, 0, 3, 0, 0, 32, 33, 0, 0, 0, 1, 0, 0, 0, 31, 0, 33, 0, 2, 0, 0, 2, 4, 0, 0, 31, 32

Offset: 1

Hamid Kulosman, May 11 2020

nonn

			For n=7 the Collatz process is: 7,22,(11),34,(17),52,26,(13),40,20,10,5,16,8,4,2,1. The numbers in the parentheses are odd numbers in the Collatz process for n=7 that are bigger than 7. There are three of them, hence a(7)=3.

Markus Sigg, Table of n, a(n) for n = 1..10000 (terms 1..1000 from Harvey P. Dale).
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A006370, A006577, A070165, A078719, A286380

Table[Count[NestWhileList[If[EvenQ[#],#/2,3#+1]&,n,#>1&],?(#>n&&OddQ[#]&)],{n,90}] (* _Harvey P. Dale, Aug 03 2023 *)

f(n) = if (n%2, 3*n+1, n/2);
a(n) = {my(nb = 0, m=n); while ((n=f(n)) != 1, if ((n % 2) && (n>m), nb++)); nb;} \\ Michel Marcus, Jun 01 2020

A213209 Number of isolated even numbers in Collatz (3x+1) trajectory of n.

Original entry on oeis.org

0, 1, 1, 0, 0, 2, 2, 0, 2, 1, 1, 1, 0, 3, 3, 0, 0, 3, 2, 0, 0, 2, 2, 1, 2, 1, 24, 2, 1, 4, 23, 0, 2, 1, 1, 2, 2, 3, 5, 0, 23, 1, 3, 1, 0, 3, 22, 1, 2, 3, 2, 0, 0, 25, 24, 2, 3, 2, 4, 3, 2, 24, 24, 0, 2, 3, 3, 0, 0, 2, 21, 2, 24, 3, 1, 2, 1, 6, 5, 0, 2, 24, 23, 0

Offset: 1

Jayanta Basu, Mar 02 2013

nonn

An isolated even is not a member of any even chain in Collatz trajectory of n; see also A213181.

			a(7)=2 since there are only 2 numbers 22 and 34 in the Collatz trajectory of 7 that are not part of any even chain.

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

Cf. A133872, A139391, A213181, A286380.

Collatz[n_] := NestWhileList[If[EvenQ[#], #/2, 3 # + 1] &, n, # > 1 &]; Table[c = Collatz[n]; cnt = 0; evenCnt = 0; Do[If[OddQ[i], If[evenCnt == 1, cnt++]; evenCnt = 0, evenCnt++], {i, c}]; cnt, {n, 100}] (* T. D. Noe, Mar 02 2013 *)

From Alan Michael Gómez Calderón, Apr 23 2025: (Start)
a(n) = a(A139391(n)) + A133872(n+2) for n >= 2;
a(n) = A286380(n) - A213181(n). (End)

cp's OEIS Frontend

A078719 Number of odd terms among n, f(n), f(f(n)), ...., 1 for the Collatz function (that is, until reaching "1" for the first time), or -1 if 1 is never reached.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Formula

Extensions

A352893 Number of iterations of map x -> A352892(x) needed to reach x <= 2 when starting from x=n, or -1 if such number is never reached. Here A352892 is the next odd term in the Collatz or 3x+1 map (A139391) conjugated by unary-binary-encoding (A156552).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

PARI

Formula

A352894 Number of iterations of map x -> A352892(x) needed to reach x < n when starting from x=n, or 0 if such number is never reached. Here A352892 is the next odd term in the Collatz or 3x+1 map (A139391) conjugated by unary-binary-encoding (A156552).

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A160541 Number of odd-then-even runs to reach 1 from n under the modified "3x+1" map: x -> x/2 if x is even, x -> (3x+1)/2 if x is odd.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

C

Mathematica

Formula

A334040 Number of odd numbers larger than n in the Collatz trajectory of n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

A213209 Number of isolated even numbers in Collatz (3x+1) trajectory of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula