Search All of the Math Forum:
Views expressed in these public forums are not endorsed by
NCTM or The Math Forum.


Paul
Posts:
763
Registered:
7/12/10


Efficiently finding long Collatz sequences.
Posted:
Aug 13, 2014 3:32 PM


I am trying to find the longest Collatz sequence starting at a number < 1 million. Any ideas for how to do this efficiently? My code is copypasted below and it seems extremely inefficient. (I know that this sounds a lot like a homework problem. I do promise you that no it isn't.)
Thank you.
#include <iostream>
using std::cout; using std::endl;
int main() { int globalMax = 0; int longestChain = 0; const int NumTrials = 1000 * 1000;
for(int i = 1; i < NumTrials; i++) {
int collatz = i; int Max = 0; while (collatz !=1) { Max++; collatz = collatz % 2 == 0 ? collatz/2 : 3 * collatz + 1; }
if(Max > globalMax) { globalMax = Max; longestChain = i; }
}
cout << longestChain << endl << globalMax;
return 0; }
Paul Epstein



