Finding maximum Collatz sequence between 1-1000000 I'm trying to find maximum the Collatz sequence between 1 and 1000000. I wrote the following code below. I guess it is correct but it is extremely slow. Can you give me a few hints to make it faster?

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;
using namespace std;
bool myfn(int i, int j) { return i&lt;j; }

int collatz(int x);

int main()
{
    vector &lt;int&gt; myvector;
    for(int i = 1; i &lt; 1000000; i++)
    {
        myvector.push_back(collatz(i));
    }

    cout&lt;&lt;*max_element(myvector.begin(),myvector.end(),myfn);


    return 0;

}

int collatz(int x)
{
    int counter = 1;


    while(1)
    {
        if(x == 1)
            break;

        if(x % 2 == 0)
        {
            x = x / 2;
            counter++;
        }
        else
        {
            x = 3 * x + 1;
            counter++;
        }
    }

    return counter;
}
Your program is non-portable, since an int is only guaranteed to hold numbers up to 32767.  I would change your data type to unsigned long long; otherwise, collatz(159487) will overflow.



Your while condition is clumsy.

while(1)
{
    if(x == 1)
        break;
    …
}


should just be

while (x != 1)
{
    …
}




The key insight is that if you already know, for example, the value of collatz(37), then collatz(74) is just 1 + collatz(74 / 2), and you can reuse the previously computed result.  Therefore, your collatz() function should have access to the results vector — either


pass it in by reference, or
make the vector an instance variable, and the function a method of the class.


It turns out that recursion works quite well for this problem: every chain will terminate in a few hundred steps, so your function call chains will be at most a few hundred frames deep.  Using recursion allows you to cache the result for every number along the chain, which you can't do using iteration.

#include &lt;iostream&gt;
#include &lt;limits&gt;
#include &lt;stdexcept&gt;
#include &lt;vector&gt;

int collatz(unsigned long long n, std::vector&lt;int&gt; &amp;results) {
    int c;
    if (n == 1) {
        return 1;
    } else if (n &lt; results.size() &amp;&amp; results[n]) {
        return results[n];
    } else if (n % 2 == 0) {
        c = 1 + collatz(n / 2, results);
    } else if (n &gt;= (std::numeric_limits&lt;unsigned long long&gt;::max() - 1) / 3) {
        throw std::overflow_error("Overflow");
    } else {
        c = 1 + collatz(3 * n + 1, results);
    }
    if (n &lt; results.size()) {
        results[n] = c;
    }
    return c;
}

int main() {
    const unsigned long long N = 1000000ULL;
    std::vector&lt;int&gt; results(N);
    int max = 0, max_i;
    for (unsigned long long i = 1; i &lt; N; ++i) {
        results[i] = collatz(i, results);
        // std::cout &lt;&lt; "collatz(" &lt;&lt; i &lt;&lt; ") = " &lt;&lt; results[i] &lt;&lt; std::endl;
        if (max &lt; results[i]) {
            max = results[i];
            max_i = i;
        }
    }
    std::cout &lt;&lt; "Max: " &lt;&lt; max_i &lt;&lt; " with " &lt;&lt; max &lt;&lt; " steps" &lt;&lt; std::endl;
    return 0;
}


By packaging your code into a class, you can let main() not worry about some of the details:

template &lt;typename T&gt;
class Collatz {
  public:
    Collatz(T limit) : limit(limit), results(limit) {}

    int operator[](T n) {
        int c;
        if (n == 1) {
            return 1;
        } else if (n &lt; results.size() &amp;&amp; results[n]) {
            return results[n];
        } else if (n % 2 == 0) {
            c = 1 + (*this)[n / 2];
        } else if (n &gt;= (std::numeric_limits&lt;T&gt;::max() - 1) / 3) {
            throw std::overflow_error("Overflow");
        } else {
            c = 1 + (*this)[3 * n + 1];
        }
        if (n &lt; results.size()) {
            results[n] = c;
        }
        return c;
    }

    const T limit;

  private:
    std::vector&lt;int&gt; results;
};    

int main() {
    Collatz&lt;unsigned long long&gt; collatz(1000000ULL);
    int max = 0, max_i;
    for (unsigned long long i = 1; i &lt; collatz.limit; ++i) {
        // std::cout &lt;&lt; "collatz(" &lt;&lt; i &lt;&lt; ") = " &lt;&lt; collatz[i] &lt;&lt; std::endl;
        if (max &lt; collatz[i]) {
            max = collatz[i];
            max_i = i;
        }
    }
    std::cout &lt;&lt; "Max: " &lt;&lt; max_i &lt;&lt; " with " &lt;&lt; max &lt;&lt; " steps" &lt;&lt; std::endl;
    return 0;
}