title: Max length of collatz sequence - optimisation
body: <p>I'm trying to solve <a href="http://www.codewars.com/kata/53a9ee602f150d5d6b000307/" rel="nofollow noreferrer">this MaxCollatzLength kata</a> but I'm struggling to optimise it to run fast enough for really large numbers.</p>
  
  <blockquote>
    <p>In this kata we will take a look at the length of collatz sequences.
    And how they evolve. Write a function that take a positive integer n
    and return the number between 1 and n that has the maximum Collatz
    sequence length and the maximum length. The output has to take the
    form of an array [number, maxLength] For exemple the Collatz sequence
    of 4 is [4,2,1], 3 is [3,10,5,16,8,4,2,1], 2 is [2,1], 1 is [ 1 ], so
    MaxCollatzLength(4) should return [3,8]. If n is not a positive
    integer, the function have to return [].</p>
    
    <p>As you can see, numbers in Collatz sequences may exceed n. The last
    tests use random big numbers so you may consider some optimisation in
    your code:</p>
    
    <p>You may get very unlucky and get only hard numbers: try submitting 2-3
    times if it times out; if it still does, probably you need to optimize
    your code more; </p>
    
    <p>Optimisation 1: when calculating the length of a
    sequence, if n is odd, what 3n+1 will be ? </p>
    
    <p>Optimisation 2: when looping through 1 to n, take i such that i &lt; n/2, what 
    will be the length of the sequence for 2i ?</p>
  </blockquote>
  
  <p>A recursive solution quickly blows the stack, so I'm using a while loop.  I think I've understood and applied the first optimisation. I also spotted that for n that is a power of 2, the max length will be (log2 of n) + 1 (that only shaves off a very small amount of time for an arbirtarily large number).  Finally I have memoised the collatz lengths computed so far to avoid recalculations.</p>
  
  <p>I don't understand what is meant by the second optimisation, however.  I've tried to notice a pattern with a few random samples and loops and I've plotted the max collatz lengths for n &lt; 50000.  I noticed it seems to roughly follow a curve but I don't know how to proceed - is this a red herring?</p>
  
  <p><a href="https://i.stack.imgur.com/qdTvt.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/qdTvt.png" alt="enter image description here"></a></p>
  
  <p>I'm ideally looking for a hints in the right direction so I can work towards the solution myself.</p>
  
  <pre class="lang-js prettyprint-override"><code>function collatz(n) {
    let result = [];
  
    while (n !== 1) {
      result.push(n);
      if (n % 2 === 0) n /= 2;
      else {
        n = n * 3 + 1;
        result.push(n);
        n = n / 2;
      }
    }
  
    result.push(1);
    return result;
  }
  
  function collatzLength(n) {
    if (n &lt;= 1) return 1;
    if (!collatzLength.precomputed.hasOwnProperty(n)) {
      // powers of 2 are logarithm2 + 1 long
      if ((n &amp; (n - 1)) === 0) { 
        collatzLength.precomputed[n] = Math.log2(n) + 1; 
      } else {
        collatzLength.precomputed[n] = collatz(n).length;
      }
    }
    return collatzLength.precomputed[n];
  }
  
  collatzLength.precomputed = {};
  
  function MaxCollatzLength(n) {
    if (typeof n !== 'number' || n === 0) return [];
    let maxLen = 0;
    let numeralWithMaxLen = Infinity;
  
    while (n !== 0) {
      let lengthOfN = collatzLength(n);
  
      if (lengthOfN &gt; maxLen) {
        maxLen = lengthOfN;
        numeralWithMaxLen = n;
      }
      n--;
    }
  
    return [numeralWithMaxLen, maxLen];
  }
  </code></pre>