■

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

typedef unsigned long long U64;
typedef unsigned short gtype;

gtype gmax = 1;
U64 kmax = 1;

#define LEAP_BITS 10
#define LEAP_N (1<<LEAP_BITS)
#define LMASK (LEAP_N-1)
U64 atab[LEAP_N], btab[LEAP_N];
U64 thtab[LEAP_N];
gtype gtab[LEAP_N];

#define SKIP_BITS 16
#define SKIP_MASK ((1<<SKIP_BITS)-1)
char skip_tab[1<<SKIP_BITS];

#define GTABLE_MAX ((1<<20)*32)
gtype gtable[GTABLE_MAX];

#define LOONG_MASK ((1LL<<48)-1)
#define LOONG_BITS 48
/*   64  48  32  16  01
 *XH ******************
 *               64  48  32  16  01
 *XL             MARGIN************
 */
// b < 1^16 is assumed
#define LOONG_ADD(xh,xl,b) {xl+=b;xh += xl>>LOONG_BITS;xl&=LOONG_MASK;}
#define LOONG_MUL(xh,xl,b) {xl*=b;xh = xh*b + (xl>>LOONG_BITS);xl&=LOONG_MASK;}

void handle_loong(U64 *x, gtype *g)
{
    int g0 = 0;
    U64 xh, xl;
    U64 x64 = *x;
    xl = x64&LOONG_MASK;
    xh = x64 >>LOONG_BITS;

    while ( xh != 0)
    {
	int c = xl & LMASK;
	U64 a = atab[c];
	U64 b = btab[c];
	xl >>=LEAP_BITS;
	xl |= (xh&LMASK) << (LOONG_BITS-LEAP_BITS);
	xh >>= LEAP_BITS;
        LOONG_MUL(xh, xl, a);
        LOONG_ADD(xh, xl, b);
	g0 += gtab[c];
    }
    *x = xl;
    (*g) += g0;
}

void do_check(U64 k)
{
    int i;
    #define H_BUFSIZE (1<<16)
    U64 x_log[H_BUFSIZE];
    gtype g_log[H_BUFSIZE];

    gtype g=0;
    int n_log = 0;
    U64 x = k;

   while(1)
    {
        if (x <= GTABLE_MAX)
        {
    	    if (gtable[x-1] != 0) break;
	    x_log[n_log] = x;
	    g_log[n_log] = g;
	    n_log++;
            if (x & 1) x = x*3+1;
	    else x >>=1;
	    g++;
	}
	else
	{
	    //Hot Spot
	    U64 m = x>>LEAP_BITS;
	    int c = x & LMASK;
            if (m >= thtab[c]) handle_loong(&x, &g);
	    else
	    {
	        x = m*atab[c]+btab[c];
	        g += gtab[c];
	    }
        }
    }
    g += gtable[x-1];

    for(i=0;i<n_log;i++)
    {
        gtable[x_log[i]-1] = g-g_log[i];
    }

    if (g>=gmax)
    {
        gmax = g;
        kmax = k;
        printf("g(%lld)=%d\n",kmax,gmax);
    }
}

int  main(int argc, char **argv)
{
    //U64 n = atoll(argv[1]);
    U64 n = 1LL<<atoll(argv[1]);

    U64 k, i, n0;

    gtable[0] = 1;
    for(i=1;i<GTABLE_MAX;i++)
	gtable[i] = 0;

    init_leap_table(LEAP_BITS, atab,btab,gtab,thtab);

    init_skip_tab(SKIP_BITS, skip_tab);

    n0=n/2;
    n0 >>=SKIP_BITS;
    n0/=6;
    n0*=6;
    n0 <<=SKIP_BITS;

    for(k=n0;k<=n;)
    {
	if(skip_tab[k&SKIP_MASK])do_check(k);k++; //0
	if(skip_tab[k&SKIP_MASK])do_check(k);k+=2; //1
	if(skip_tab[k&SKIP_MASK])do_check(k);k+=3; //3
	if(k%(n/600)==0)printf("%lld/%lld\n",k,n);
    }
    printf("g(%lld)=%d\n",kmax,gmax);
}