1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
using System;
class Program {
    const int MAX = 1048577;
    static int[] cache = new int[MAX];

    static int collatz(ulong n) {
        return collatz(n, 0, 0);
    }
    static int collatz(ulong n, ulong org_n) {
        return collatz(n, org_n, 0);
    }
    static int collatz(ulong n, ulong org_n, int depth) {
        if(MAX > n) {
            if(cache[n] != -1) {
                cache[org_n] = cache[n] + depth;
                return cache[n] + depth;
            }
        }

        if(n % 2 == 0) {
            return collatz(n / 2, org_n, depth + 1);
        } else if(n == 1) {
            cache[org_n] = depth;
            return depth;
        } else {
            return collatz(n * 3 + 1, org_n, depth + 1);
        }
    }


    static void Main() {
        long tick = DateTime.Now.Ticks;
        for(int i = 0; i < MAX; i++)
            cache[i] = -1;

        ulong max_n = 0;
        int max_steps = 0;

        for(ulong i = 1; i < MAX; i++) {
            int steps = collatz(i, i);
            if(max_steps < steps) {
                max_steps = steps;
                max_n = i;
            }
        }

        Console.WriteLine("f(" + max_n + ")=" + max_steps);
        Console.WriteLine((DateTime.Now.Ticks - tick) / 10000L + "ms");
        Console.ReadLine();
    }
}