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


Math Forum
»
Discussions
»
sci.math.*
»
sci.math
Notice: We are no longer accepting new posts, but the forums will continue to be readable.
Topic:
Efficiently finding long Collatz sequences.
Replies:
10
Last Post:
Aug 16, 2014 10:40 PM



Paul
Posts:
780
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



