|
|
A006370
|
|
The Collatz or 3x+1 map: a(n) = n/2 if n is even, 3n + 1 if n is odd.
(Formerly M3198)
|
|
208
|
|
|
0, 4, 1, 10, 2, 16, 3, 22, 4, 28, 5, 34, 6, 40, 7, 46, 8, 52, 9, 58, 10, 64, 11, 70, 12, 76, 13, 82, 14, 88, 15, 94, 16, 100, 17, 106, 18, 112, 19, 118, 20, 124, 21, 130, 22, 136, 23, 142, 24, 148, 25, 154, 26, 160, 27, 166, 28, 172, 29, 178, 30, 184, 31, 190, 32, 196, 33
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
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 an unsolved problem. It is conjectured that the answer is yes.
The Krasikov-Lagarias paper shows that at least N^0.84 of the positive numbers < N fall into the 4-2-1 cycle of the 3x+1 problem. This is far short of what we think is true, that all positive numbers fall into this cycle, but it is a step. - Richard C. Schroeppel, May 01 2002
a(n) is the image of a(2*n) under the 3*x+1 map. - L. Edson Jeffery, Aug 17 2014
|
|
REFERENCES
|
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).
|
|
LINKS
|
|
|
FORMULA
|
G.f.: (4*x+x^2+2*x^3) / (1-x^2)^2.
Dirichlet g.f.: (1-2^(-s))*zeta(s) + (3-5*2^(-s))*zeta(s-1).
a(n) = ( a(n+2k) + a(n-2k) ) / 2, for every integer k. (End)
|
|
EXAMPLE
|
G.f. = 4*x + x^2 + 10*x^3 + 2*x^4 + 16*x^5 + 3*x^6 + 22*x^7 + 4*x^8 + 28*x^9 + ...
Written as a rectangular array with six columns read by rows the sequence begins:
0, 4, 1, 10, 2, 16;
3, 22, 4, 28, 5, 34;
6, 40, 7, 46, 8, 52;
9, 58, 10, 64, 11, 70;
12, 76, 13, 82, 14, 88;
15, 94, 16, 100, 17, 106;
18, 112, 19, 118, 20, 124;
21, 130, 22, 136, 23, 142;
24, 148, 25, 154, 26, 160;
27, 166, 28, 172, 29, 178;
30, 184, 31, 190, 32, 196;
...
(End)
|
|
MAPLE
|
f := n-> if n mod 2 = 0 then n/2 else 3*n+1; fi;
|
|
MATHEMATICA
|
f[n_]:=If[EvenQ[n], n/2, 3n+1]; Table[f[n], {n, 50}] (* Geoffrey Critzer, Jun 29 2013 *)
LinearRecurrence[{0, 2, 0, -1}, {4, 1, 10, 2}, 70] (* Harvey P. Dale, Jul 19 2016 *)
|
|
PROG
|
(PARI) for(n=1, 100, print1((1/4)*(7*n+2-(-1)^n*(5*n+2)), ", "))
(Haskell)
a006370 n | m /= 0 = 3 * n + 1
| otherwise = n' where (n', m) = divMod n 2
(Python)
q, r = divmod(n, 2)
(Magma) [(1/4)*(7*n+2-(-1)^n*(5*n+2)): n in [1..70]]; // Vincenzo Librandi, Dec 20 2016
|
|
CROSSREFS
|
A006577 gives number of steps to reach 1.
|
|
KEYWORD
|
nonn,nice,easy
|
|
AUTHOR
|
|
|
EXTENSIONS
|
More terms from Larry Reeves (larryr(AT)acm.org), Apr 27 2001
|
|
STATUS
|
approved
|
|
|
|