A127789 -id:A127789 - cp's OEIS frontend

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

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

A304174 Decimal expansion of 2^61/(3^32*993), the conjectured maximal residue in the Collatz 3x+1 problem.

Original entry on oeis.org

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

Offset: 1

M. F. Hasler (following an idea of Michel Lagneau), May 07 2018

The residue of n in the 3x+1 problem is defined as the ratio 2^h(n)/(3^t(n)*n), where h = A006666 is the number of halving steps, and t = A006667 is the number of tripling steps. It is conjectured that n = 993 yields the highest possible residue. See e.g. the Roosendaal page, and A127789 for indices of record residues.

			res(993) = 1.253142144395068050165495297839461424861536597396513692763...

Paolo Xausa, Table of n, a(n) for n = 1..10000
Eric Roosendaal, On the 3x + 1 problem, last modified on April 6, 2018.
Index entries for sequences related to 3x+1 (or Collatz) problem

Cf. A006370 (Collatz map), A014682 (condensed version), A127789 (indices of record residues).

Cf. A006666 (halving steps), A006667 (tripling steps), A006577 (total).

First[RealDigits[2^61/(3^32*993), 10, 100]] (* Paolo Xausa, Mar 10 2024 *)

2^61/(3^32*993.) \\ Or, to find this value experimentally:
(c(n,c=[0,0])=while(n>1,bittest(n,0)&&c[1]++&&(n=n*3+1)&&next;n\=2;c[2]++);c); m=1;for(n=1,oo,m<<(t=c(n))[2]>n*3^t[1]||next;m=n*3^t[1]/2^t[2];printf("res(%d) = %f\n",n,1./m )) \\ M. F. Hasler, May 07 2018

res(993) = 2^61/(3^32*993).

A304119 Numerators of record low values of the ratio n*3^A006667(n)/2^A006666(n).

Original entry on oeis.org

1, 27, 1701, 6561, 1760826122505, 115093142840908791, 460166680231540515, 1840049047529878113

Offset: 1

Michel Lagneau, May 03 2018

This has been verified for n up to 10^7.
Conjecture: Consider A006666 and A006667, the sequences giving the number of halving and tripling steps to reach 1 in 3x+1 problem. There exists a rational constant c such that c <= n*3^A006667(n)/2^A006666(n) <= 1 where c = 1840049047529878113/2305843009213693952 is the last term in the sequence of the ratios.
Note that n*3^A006667(n)/2^A006666(n) = 1 if n is a power of 2 (A000079).
It seems that n*3^A006667(n)/2^A006666(n) = c for n = 993*2^k, k = 0, 1, 2, ... In this case, c = 993*2^k*3^32/2^(61+k), where 32 = A006667(993*2^k) and 61+k = A006666(993*2^k). For example, c = 993*3^32/2^61 = 1986*3^32/2^62 = 3972*3^32/2^63 = 7944*3^32/2^64 = ...

			For n=1 to 10 the ratios are: 1, 1, 27/32, 1, 15/16, 27/32, 1701/2048, 1, 6561/8192, 15/16, so the low records are 1, 27/32, 1701/2048, 6561/8192, ...

Cf. A006666, A006667, A127789 (for the indices where these records occur).

q=1; Collatz[n_]:=NestWhileList[If[EvenQ[#], #/2, 3 #+1]&, n, #>1&]; nn=5000; t={}; n=0; While[Length[t]

ht(n) = my(h, t); while(n>1, if(n%2, n=3*n+1; t++, n>>=1; h++)); return([h, t]);
lista(nn) = {m = 2; for (n=1, nn, v = ht(n); newm = n*3^v[2]/2^v[1]; if (newm < m, print1(numerator(newm), ", "); m = newm));} \\ Michel Marcus, May 06 2018

A304123 Denominators of records low values of the ratio n*3^A006667(n)/2^A006666(n).

Original entry on oeis.org

1, 32, 2048, 8192, 2199023255552, 144115188075855872, 576460752303423488, 2305843009213693952

Offset: 1

Michel Lagneau, May 06 2018

			For n=1 to 10 the ratios are 1, 1, 27/32, 1, 15/16, 27/32, 1701/2048, 1, 6561/8192, 15/16, so the low records are 1, 27/32, 1701/2048, 6561/8192, ...

Cf. A127789 (for the indices where these records occur).
Cf. A304119 (for the corresponding numerators).
Cf. A006666, A006667.

q=1;Collatz[n_]:=NestWhileList[If[EvenQ[#],#/2,3 #+1]&,n,#>1&];nn=5000;t={};n=0;While[Length[t]

ht(n) = my(h, t); while(n>1, if(n%2, n=3*n+1; t++, n>>=1; h++)); return([h, t]);
lista(nn) = {m = 2; for (n=1, nn, v = ht(n); newm = n*3^v[2]/2^v[1]; if (newm < m, print1(denominator(newm), ", "); m = newm)); } \\ Michel Marcus, May 06 2018

A304524 Consider the ratio res(p) = 2^A006666(p) / (p*3^A006667(p)) where p is prime. The prime numbers in this sequence are those for which res(p) sets a new record.

Original entry on oeis.org

2, 3, 7, 37, 43, 229, 271, 379, 673, 839, 1987, 5297, 25111, 44641, 50221, 94057, 334423, 1189057, 1759579, 2505337, 28153249, 46869157, 87780541, 584543567, 768901097

Offset: 1

Michel Lagneau, May 14 2018

Is the sequence finite?
In the general case, the residue of a number n in the 3x+1 problem is defined as the ratio res(n) = 2^A006666(n) / (n*3^A006667(n)) (see A127789).
Conjecture: for all prime p, res(p) < res(993) = 2^61/(3^32*993) = 1.253142... (see A304174).

			From _Jon E. Schoenfield_, May 23 2018: (Start)
Let D = A006666(p) and U = A006667(p); then res(p) = 2^D/(p*3^U). It seems clear that res(993) - res(p) is converging toward a positive value:
.
          p |   D |  U |     res(p)      | res(993)-res(p)
  ----------+-----+----+-----------------+----------------
          2 |   1 |  0 | 1               | 0.2531421443...
          3 |   5 |  2 | 1.1851851851... | 0.0679569592...
          7 |  11 |  5 | 1.2039976484... | 0.0491444959...
         37 |  15 |  6 | 1.2148444741... | 0.0382976702...
         43 |  20 |  9 | 1.2389111604... | 0.0142309838...
        229 |  24 | 10 | 1.2407145246... | 0.0124276197...
        271 |  29 | 13 | 1.2425797507... | 0.0105623936...
        379 |  39 | 19 | 1.2480350469... | 0.0051070974...
        673 |  43 | 21 | 1.2494773856... | 0.0036647587...
        839 |  56 | 29 | 1.2514151532... | 0.0017269911...
       1987 |  62 | 32 | 1.2525114739... | 0.0006306704...
       5297 |  65 | 33 | 1.2529055685... | 0.0002365758...
      25111 |  72 | 36 | 1.2529406796... | 0.0002014647...
      44641 |  76 | 38 | 1.2529625095... | 0.0001796348...
      50221 |  73 | 36 | 1.2529656281... | 0.0001765162...
      94057 |  85 | 43 | 1.2529812032... | 0.0001609411...
     334423 |  90 | 45 | 1.2529882803... | 0.0001538640...
    1189057 |  95 | 47 | 1.2529909733... | 0.0001511710...
    1759579 | 113 | 58 | 1.2529910420... | 0.0001511023...
    2505337 | 104 | 52 | 1.2529915763... | 0.0001505680...
   28153249 | 117 | 58 | 1.2529917096... | 0.0001504347...
   46869157 | 132 | 67 | 1.2529917720... | 0.0001503722...
   87780541 | 144 | 74 | 1.2529919281... | 0.0001502162...
  584543567 | 161 | 83 | 1.2529919325... | 0.0001502118...
  768901097 | 182 | 96 | 1.2529919396... | 0.0001502047...
(End)

Eric Roosendaal, On the 3x+1 Problem

Cf. A006666, A006667, A127789, A304174.

lst={2};Print["a(n)"," ","A006667(a(n))"," ","A006666(a(n))","       ","res(a(n))"];q=1;Collatz[n_]:=NestWhileList[If[EvenQ[#],#/2,3 #+1]&,Prime[n],#>1&];nn=10000;t={};n=0;While[Length[t]5000,Break[]];q=Prime[n]*3^od/2^ev]];lst

a(23)-a(24) from Jon E. Schoenfield, May 19 2018

A381762 Numbers k such that S(k) sets a new record, where S(k) denotes the sum of the reciprocals of odd elements in the Collatz sequence which starts at k.

Original entry on oeis.org

1, 3, 7, 9, 559, 745, 993

Offset: 1

Barak Manos, Mar 06 2025

This sequence is conjectured to be finite.

Cf. A304174.

Cf. A127789.

f[n_] := Total[1/Select[NestWhileList[If[OddQ[#], 3*# + 1, #/2] &, n, # > 1 &], OddQ]]; seq[lim_] := Module[{s = {}, fm = 0, f1}, Do[f1 = f[n]; If[f1 > fm, fm = f1; AppendTo[s, n]], {n, 1, lim}]; s]; seq[1000] (* Amiram Eldar, Mar 06 2025 *)

from fractions import Fraction
def S(n):
    arr = []
    while True:
        n //= (n - (n & (n - 1)))
        arr.append(n)
        if n == 1:
            break
        n = 3 * n + 1
    return sum(Fraction(1, x) for x in arr)
m = 0
for n in range(1, 1000):
    k = S(n)
    if m < k:
        m = k
        print(n)

cp's OEIS Frontend

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

A304174 Decimal expansion of 2^61/(3^32*993), the conjectured maximal residue in the Collatz 3x+1 problem.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A304119 Numerators of record low values of the ratio n*3^A006667(n)/2^A006666(n).

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

PARI

A304123 Denominators of records low values of the ratio n*3^A006667(n)/2^A006666(n).

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

PARI

A304524 Consider the ratio res(p) = 2^A006666(p) / (p*3^A006667(p)) where p is prime. The prime numbers in this sequence are those for which res(p) sets a new record.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A381762 Numbers k such that S(k) sets a new record, where S(k) denotes the sum of the reciprocals of odd elements in the Collatz sequence which starts at k.

Views

Author

Keywords