C++ Beginner. Project Euler 14: Longest Collatz sequence under one million Hello, I'm a C++ beginner, learning the language while trying to code Project Euler problems. I'm having trouble coding problem 14, which I'll copy here:


  The following iterative sequence is defined for the set of positive
  integers:
  
  n → n/2 (n is even) n → 3n + 1 (n is odd)
  
  Using the rule above and starting with 13, we generate the following
  sequence: 13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1
  
  It can be seen that this sequence (starting at 13 and finishing at 1)
  contains 10 terms. Although it has not been proved yet (Collatz
  Problem), it is thought that all starting numbers finish at 1.
  
  Which starting number, under one million, produces the longest chain?
  
  NOTE: Once the chain starts the terms are allowed to go above one
  million.


My program runs fast, and works for smaller values of n, but for some reason I don't understand, it doesn't give the right solution for n = 1 million. I think the mod function % might be the issue in some way for large numbers, or the way i defined the variables, but I can't get it right. 
Would appreciate some help, and thank you for your patience in advance.

I wrote this piece of code for it:

#include &lt;iostream&gt;
#include &lt;cmath&gt;
using namespace std;

double maxvec(int *v,int n){  //gets the max value of a vector
  double elmax;
  elmax=v[0];
  for(int i=1;i&lt;n;i++){
    if(v[i]&gt;elmax) elmax=v[i]; 
  }
  return elmax;
}

double indice(int *v,int n){  //gets the index corresponding to the max value of a vector
  double elmax=v[0];
  double indice;
  indice=0;
  for(int i=1;i&lt;n;i++){
    if(v[i]&gt;elmax){ elmax=v[i];indice=i; }
  }
  return indice;
}

int main(){

  const int n = 1000000;

  long x0;

  int ind;

  int k[n-2];     //vector that contains how many elements are there in the sequence for each initial   number

  for ( int i=2; i&lt;n; i++){   //the numbers we are gonna run through the Collatz sequence (in this case the problem asks for n=1000000)

    k[i-2]=0;         

    x0=i;

      while (x0!=1){          //using the property that all Collatz sequences end in 1

      x0=x0%2 + x0/2*((x0+1)%2)+ 3*x0*(x0%2); //the algorithm for the collatz sequence

      k[i-2] = k[i-2]+1;  //for the final iteration of the while loop, the (i-2)th component contains the information of the number of elements that corresponds to the initial value i

       }

  }

  cout&lt;&lt;maxvec(k,n-2)&lt;&lt;endl; //shows the maximum value of array k

  cout&lt;&lt;indice(k,n-2)+2&lt;&lt;endl; //shows the initial value for the max value of k, which is the solution to the problem

}
I will try and tackle correctness, style and performance in that order

Corectness

My initial guess, for wrong results would be you are overflowing an int for long sequences. making x0 an unsigned long I get the longest sequence as 524, for 837799, which matches the results at https://www.dcode.fr/collatz-conjecture . Indeed that sequence contains 2974984576 which will overflow a signed int.

Style

Your code is very c-like and has not really used any c++ features other than cout. Some things I would change:


avoid using namespace std, see https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice This is generally considered bad practise as it you can get unexpected name collisions. It probably won't cause any real issues on a small project like this, but is a bad habit to get into.
Prefer stl containers to raw arrays. Stl containers have many advantages over raw arrays. In your case I would make k a std::array, i.e. std::array&lt; std::size_t,  n-2 &gt; k; std::arrays are fixed size containers very similar to raw arrays, but don't decay to pointers, provide iterators and to allow easily looping over the elements ( and interacting with the rest of the stl ), among other features.
Your update of x0 is not very clear/easy to read. I would break this into the two cases with and if/else, and probably make it a separate function. i.e.


if( x0%2 )
{
    x0 = 3*x0 + 1;
}
else
{
    x0 = x0/2;
}



Use stl functions rather than writing your own. Another advantage of using stl containers is there are many standard functions that use the containers, which can save you having to write your own. e.g. std::max_element this could simplify your calculation of max value and index.


auto maxIt = std::max_element(k.begin(), k.end());
int maxSeq = std::distance(k.begin(), maxIt) + 2;
unsigned long maxValue = k[maxSeq - 2];



Make values unsigned if they cannot be &lt; 0. None of your values should be &lt;0, for clarity it is good practise to make them in this case. The normal way to do this for ints is to use std::size_t. This helps clarify the intent of your code.


Performance

Your code seems to have pretty good performance and has no trivial performance improvements that I can see. Possibly the updating of x0 can be written more efficiently, but I would change it for clarity reasons, as mentioned above, and profile any possible performance changes from there. 

I will note that the sequence does not depend on previous values, so if you reach a value already calculated k for you do not need to calculate the rest of the sequence, but can just add that value. Again you would need to profile whether the cost of doing the extra checks gives an actual improvement.