Thursday, 13 October 2011

Collatz conjecture

 

Problem

  This is project euler problem 14. Really interesting and mathematically challenging one.

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

Source: Project Euler.

The below figure will explain the problem precisely.

References

http://en.wikipedia.org/wiki/Collatz_conjecture

http://projecteuler.net/problem=14

Solution

I tried the tail recursive way first..!! But its too slow and it took hours to run.. In debug mode, stack is used even for tail recursion.. so, it went useless to do 1 million function calls every time. so, moved into a iterative way.

Just a brute force algorithm for 1 million values took around 10-15 minutes to run. But, the 1-minute rule given by project euler is not followed in this program.. :)

There are better ways to do.. But since there seems no valid applications for this series, am just leaving it here..

#include <iostream>
#include <cmath>
 
using namespace std;
 
 
int main()
{
    int gMax = 0;
    double gI = 0;
    for(double i=1; i<1000000; i++) {
        double val = i;
        int count = 0;
        cout<<val<<" ";
        while(val != 1) {
            ++count;
            if (fmod(val, 2.0) == 0) {
                val = val/2;
            }
            else
            { // odd
                val = 3*val + 1;
            }
        }
        count++;
        if(count > gMax) {
            gI = i;
            gMax = count;
        }
        cout<<endl;
    }
 
    return 0;
}
  • gMax is the maximum count of the numbers in the series
  • gI is the number which yields this max count