A006577 Number of halving and tripling steps to reach 1 in '3x+1' problem, or -1 if 1 is never reached.

0, 1, 7, 2, 5, 8, 16, 3, 19, 6, 14, 9, 9, 17, 17, 4, 12, 20, 20, 7, 7, 15, 15, 10, 23, 10, 111, 18, 18, 18, 106, 5, 26, 13, 13, 21, 21, 21, 34, 8, 109, 8, 29, 16, 16, 16, 104, 11, 24, 24, 24, 11, 11, 112, 112, 19, 32, 19, 32, 19, 19, 107, 107, 6, 27, 27, 27, 14, 14, 14, 102, 22

Offset: 1

Author

N. J. A. Sloane, Bill Gosper

Keywords

• nonn
• nice
• easy
• hear
• look

Comments

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 a famous unsolved problem. It is conjectured that the answer is yes.

It seems that about half of the terms satisfy a(i) = a(i+1). For example, up to 10000000, 4964705 terms satisfy this condition.

n is an element of row a(n) in triangle A127824. - Reinhard Zumkeller, Oct 03 2012

The number of terms that satisfy a(i) = a(i+1) for i being a power of ten from 10^1 through 10^10 are: 0, 31, 365, 4161, 45022, 477245, 4964705, 51242281, 526051204, 5378743993. - John Mason, Mar 02 2018

5 seems to be the only number whose value matches its total number of steps (checked to n <= 10^9). - Peter Woodward, Feb 15 2021

Examples

			a(5)=5 because the trajectory of 5 is (5,16,8,4,2,1).
		

References

• 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).

Links

• N. J. A. Sloane, Table of n, a(n) for n = 1..10000
• David Eisenbud and Brady Haran, UNCRACKABLE? The Collatz Conjecture, Numberphile video, 2016.
• Geometry.net, Links on Collatz Problem
• Christian Hercher, There are no Collatz m-Cycles with m <= 91, J. Int. Seq. (2023) Vol. 26, Article 23.3.5.
• Jason Holt, Log-log plot of first billion terms
• Jason Holt, Plot of 1 billion values of the number of steps to drop below n (A060445), log scale on x axis
• Jason Holt, Plot of 10 billion values of the number of steps to drop below n (A060445), log scale on x axis
• A. Krowne, Collatz problem, PlanetMath.org.
• J. C. Lagarias, The 3x+1 problem and its generalizations, Amer. Math. Monthly, 92 (1985), 3-23.
• J. C. Lagarias, How random are 3x+1 function iterates?, in The Mathemagician and the Pied Puzzler - A Collection in Tribute to Martin Gardner, Ed. E. R. Berlekamp and T. Rogers, A. K. Peters, 1999, pp. 253-266.
• J. C. Lagarias, The 3x+1 Problem: an annotated bibliography, II (2000-2009), arXiv:0608208 [math.NT], 2006-2012.
• J. C. Lagarias, ed., The Ultimate Challenge: The 3x+1 Problem, Amer. Math. Soc., 2010.
• Jeffrey C. Lagarias, The 3x+1 Problem: An Overview, arXiv:2111.02635 [math.NT], 2021.
• M. Le Brun, Email to N. J. A. Sloane, Jul 1991
• Mathematical BBS, Biblography on Collatz Sequence
• P. Picart, Algorithme de Collatz et conjecture de Syracuse
• E. Roosendaal, On the 3x+1 problem
• J. L. Simons, On the nonexistence of 2-cycles for the 3x+1 problem, Math. Comp. 75 (2005), 1565-1572.
• N. J. A. Sloane, "A Handbook of Integer Sequences" Fifty Years Later, arXiv:2301.03149 [math.NT], 2023, p. 8.
• G. Villemin's Almanach of Numbers, Cycle of Syracuse
• Eric Weisstein's World of Mathematics, Collatz Problem
• Wikipedia, Collatz Conjecture
• Index entries for sequences related to 3x+1 (or Collatz) problem

Crossrefs

See A070165 for triangle giving trajectories of n = 1, 2, 3, ....

Cf. A006370, A125731, A127885, A127886, A008908, A112695, A135282, A208981, A025586.

See also A008884, A161021, A161022, A161023.

Programs

Haskell

import Data.List (findIndex)
import Data.Maybe (fromJust)
a006577 n = fromJust $ findIndex (n `elem`) a127824_tabf
-- Reinhard Zumkeller, Oct 04 2012, Aug 30 2012

Maple

A006577 := proc(n)
        local a,traj ;
        a := 0 ;
        traj := n ;
        while traj > 1 do
                if type(traj,'even') then
                        traj := traj/2 ;
                else
                        traj := 3*traj+1 ;
                end if;
                a := a+1 ;
        end do:
        return a;
end proc: # R. J. Mathar, Jul 08 2012

Mathematica

f[n_] := Module[{a=n,k=0}, While[a!=1, k++; If[EvenQ[a], a=a/2, a=a*3+1]]; k]; Table[f[n],{n,4!}] (* Vladimir Joseph Stephan Orlovsky, Jan 08 2011 *)
Table[Length[NestWhileList[If[EvenQ[#],#/2,3#+1]&,n,#!=1&]]-1,{n,80}] (* Harvey P. Dale, May 21 2012 *)

PARI

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

PARI

step(n)=if(n%2,3*n+1,n/2);
A006577(n)=if(n==1,0,A006577(step(n))+1); \\ Michael B. Porter, Jun 05 2010

Python

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, Jun 05 2017

Python

def A006577(n):
    ct = 0
    while n != 1: n = A006370(n); ct += 1
    return ct # Ya-Ping Lu, Feb 22 2024

R

collatz<-function(n) ifelse(n==1,0,1+ifelse(n%%2==0,collatz(n/2),collatz(3*n+1))); sapply(1:72, collatz) # Christian N. K. Anderson, Oct 09 2024

Formula

a(n) = A006666(n) + A006667(n).

a(n) = A112695(n) + 2 for n > 2. - Reinhard Zumkeller, Apr 18 2008

a(n) = A008908(n) - 1. - L. Edson Jeffery, Jul 21 2014

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

a(n) = 2*A007814(n + 1) + a(A085062(n)) + 1 for n > 1. - Wing-Yin Tang, Jan 06 2025

Extensions

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