DouKaku?

/*
Core 2 Duo 2.33GHzで

% time ./a.out 1000000
h(1000000) = 837799 where g(837799) = 525
0.264u 0.006s 0:00.27 96.2%     0+0k 0+0io 0pf+0w
*/

#include <stdio.h>
#include <stdlib.h>

#ifndef CACHE_SIZE
#define CACHE_SIZE 64*1024*1024 /* large enough */
#endif

#define MAX_U16        65535
typedef unsigned short U16;
typedef long long      I64;

U16 *cache;
int cachesize;
#define lookup(n)  ((n) < cachesize ? cache[(n)] : 0)
#define store(n,g) if ((n) < cachesize && g <= MAX_U16) cache[(n)] = (g)

I64 g(I64 n){
    I64 result = lookup(n);
    if (result) return result;
    I64 i = n;
    I64 l;
    result = 1;
    while (i > 1){
        i = i & 1 ? i*3+1 : i >> 1;
        l = lookup(i);
        if (l){
            result += l;
            break;
        }else{
            result++;
        }
    }
    if (i < 1)       fprintf(stderr, "overflow! g(%qd) = %qd\n", n, i);
    store(n, result);
    return result;
}

I64 *h(I64 n){
    I64 i, nmax = 0, gmax = 0, gnext = 0;
    static I64 result[2];
    for (i = n; i > 1 ; i--){
        gnext = g(i);
#ifdef VERBOSE
        fprintf(stderr, "g(%qd) = %qd\r", i, gnext);
#endif
        if (gnext > gmax){
            nmax = i; gmax = gnext;
        }
        if (i & 0xffff) continue;
       printf("nmax = %qd, gmax = %qd, n = %qd\r", nmax, gmax, i);
       fflush(stdout);
    }
    result[0] = nmax; result[1] = gmax;
    return result;
}

#define min(x,y) ((x) < (y) ? (x) : (y))

void init_cache(I64 n){
    cachesize = min(n, CACHE_SIZE);
    cache     = (U16 *)calloc(cachesize, sizeof(U16));
    if (cache == NULL) exit(-1);
}

int main(int argc, char **argv){
    I64 n = 0xffffffff; /* look @ this! */
    if (argc > 1){
        n = atoll(argv[1]);
    }
    init_cache(n);
    I64 *hg = h(n);
    printf("h(%qd) = %qd where g(%qd) = %qd\n", n, hg[0], hg[0], hg[1]);
    return 0;
}