Collatz sequence

Easy Timeunproven SpaceO(k)

Take a positive integer. If it is even, halve it; if it is odd, triple it and add one. Repeat until it reaches 1. Given n, return the whole sequence this produces, starting at n and ending at 1. Whether every number reaches 1 is the Collatz conjecture, unproven since 1937 and untouched by every number tested so far.

Examples

Example 1

Input
n = 27
Output
[27,82,41,124,62,31,94,47,142,71,214,107,322,161,484,242,121,364,182,91,274,137,412,206,103,310,155,466,233,700,350,175,526,263,790,395,1186,593,1780,890,445,1336,668,334,167,502,251,754,377,1132,566,283,850,425,1276,638,319,958,479,1438,719,2158,1079,3238,1619,4858,2429,7288,3644,1822,911,2734,1367,4102,2051,6154,3077,9232,4616,2308,1154,577,1732,866,433,1300,650,325,976,488,244,122,61,184,92,46,23,70,35,106,53,160,80,40,20,10,5,16,8,4,2,1]
112 values: 111 steps, climbing to 9232 before it falls to 1.

Example 2

Input
n = 6
Output
[6,3,10,5,16,8,4,2,1]
6 halves to 3, which triples to 10 — nine values, eight steps.

The Code

function collatz(n) {
  const path = [n];
  while (n !== 1) {
    if (n % 2 === 0) n = n / 2;
    else n = 3 * n + 1;
    path.push(n);
  }
  return path;
}
collatz(27);
Done

The first 10 calls, of 113. This one does not fit on a page.

Step through collatz(27) call by call

More like this

All math & numbers examples (8) →