|
|
A006577
|
|
Number of halving and tripling steps to reach 1 in '3x+1' problem, or -1 if 1 is never reached.
(Formerly M4323)
|
|
237
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,3
|
|
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.
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
|
|
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
|
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.
|
|
FORMULA
|
|
|
EXAMPLE
|
a(5)=5 because the trajectory of 5 is (5,16,8,4,2,1).
|
|
MAPLE
|
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;
|
|
MATHEMATICA
|
Table[Length[NestWhileList[If[EvenQ[#], #/2, 3#+1]&, n, #!=1&]]-1, {n, 80}] (* Harvey P. Dale, May 21 2012 *)
|
|
PROG
|
(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);
(Haskell)
import Data.List (findIndex)
import Data.Maybe (fromJust)
a006577 n = fromJust $ findIndex (n `elem`) a127824_tabf
(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
|
|
CROSSREFS
|
See A070165 for triangle giving trajectories of n = 1, 2, 3, ....
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
EXTENSIONS
|
More terms from Larry Reeves (larryr(AT)acm.org), Apr 27 2001
|
|
STATUS
|
approved
|
|
|
|