Optimized Longest Collatz Sequence I'm writing a program to calculate the longest collatz sequence for positive integers below some N. I have optimized it as far as I can - is there anything more I could do to optimize it? Any constructive criticism is welcome :) 

A few interesting notes: It is easy to prove (by contradiction or otherwise) that the number that produces the longest chain exists in the second half of the numbers from 1-N (that is, it must be greater than N/2). If we try to run the loop from N/2 to N, the running time becomes substantially slower. Interesting... Also, the lower while loop is an interesting idea, but provides no tangible performance benefits (or losses, for that matter - which is why I kept it. It's an interesting idea).

Thank you!

#include &lt;iostream&gt;
#include &lt;chrono&gt;

using namespace std::chrono;

const int N = 1000000;
long long iCpy;
short ct;
short maxLength = 0;
short vals[N] = {0};

int main() {
  // Time the program:
  auto startTime = steady_clock::now();

  int i, maxIndex = 0;

  // calculate collatz lengths for all indices.
  // keep track of max value:
  for (i = 2; i &lt; N; i++) {
    iCpy = i;
    ct = 0;

    while (iCpy != 1) {
      if (iCpy &lt; N &amp;&amp; vals[iCpy]) {
        ct += vals[iCpy];
        break;
      }

      if (iCpy &amp; 1) {
        iCpy *= 3;
        iCpy++;
      } else {
        iCpy &gt;&gt;= 1; // Equivalent to iCpy /= 2
      }

      ct++;
    }

    iCpy = i;
    vals[iCpy] = ct;
    while (iCpy &lt; N/2) {
      iCpy &lt;&lt;= 1; // Equivalent to iCpy *= 2
      vals[iCpy] = ++ct;
    }
    if (ct &gt; maxLength) {
      maxLength = ct;
      maxIndex = iCpy;
    }
  }

  // output the max index and length:
  std::cout &lt;&lt; "Max number: " &lt;&lt; maxIndex &lt;&lt; ", with length " &lt;&lt; maxLength &lt;&lt; std::endl;

  auto elapsed = duration_cast&lt;milliseconds&gt;(steady_clock::now() - startTime);
  std::cout &lt;&lt; "Program execution took " &lt;&lt; elapsed.count() &lt;&lt; "ms\n";
  return 0;
}
Here are some suggestions:


Don't use global variables.
Instead of using a single big function, break it down to logical parts.
const int N = 1000000; should be constexpr instead of const.
Instead of = {0}, use {}.  The latter makes it clear that you are
value initializing all elements.
i should be declared in the loop.
Post-increment operators i++ should be changed to pre-increment
++i in a discarded-value expression.
iCpy &amp; 1 should be iCpy % 2 == 0.  iCpy &lt;&lt;= 1; // Equivalent to iCpy *= 2 should be iCpy *= 2.  Optimization doesn't happen in this way &mdash; the compiler knows such things much better.
Use &lt;&lt; '\n' instead of &lt;&lt; std::endl when you don't need the flushing behavior.