/* Written by Antti Karttunen August 13 & 16 2015. */

#include "stdio.h"
#include "stdlib.h"

typedef unsigned long long int u64;

#define tou64(x) ((u64)(x))

u64 A000244(u64 n)
{
    u64 i;
    u64 x = 1;
    i = n; while(i != 0) { x += (x << 1); i--; }
    return(x);
}


u64 A261234(u64 n, u64 *last1p, u64 *last2p, u64 *p1, u64 *p2)
{


    if(0 == n)
     {
       *p1 = 0;
       *p2 = 1;
       *last1p = 0; /* In this case: the last with msd < 2, because 2 - 2 = 0. */
       *last2p = 2;
       return(1);
     }
    else
     {
       u64 k = (A000244(n+1)-1)-(2*(n+1)); /* We start iterating from after the first subtraction from 3^(n+1)-1 */
       u64 steps = 0;
       int all_are_2s;
       u64 prev_k = 8;
       u64 prev_m = 2;

       *p1 = *p2 = 0;

       do {
            all_are_2s = 1; /* Until proved contrariwise... */
            u64 h = k;
            u64 m;
            u64 ds = 0;

            steps++;

            while(h != 0)
             {
               m = (h%3);
               if(m < 2) /* A ternary digit 0 or 1 encountered? */
                {
                  all_are_2s = 0;
                }
               ds += m;
               h = (h - m)/3;
             }

/* Note that although we skip the first 22222..222 in the start,
   that will be compensated in the end when we bump to one digit shorter string of 2's:
 */

            if(1 == m) /* The most significant digit is 1 this time? */
             {
               ++*p1;
               if(prev_m != m) { *last2p = prev_k; } /* And it changed (it was 2 in the previous iteration)? */
             }
            else if(2 == m) /* The most significant digit is 2 this time? */
             {
               ++*p2;
               if(prev_m != m)
                {
                  *last1p = prev_k;
                }
             }

            prev_m = m;
            prev_k = k;
            k -= ds;
          } while(!all_are_2s);

       return(steps);
     }

}

#define bfilename_Alast_msd1 "blast_msd1.txt" /* Cf. A034472 3^n + 1. */
#define bfilename_Alast_msd2 "blast_msd2.txt" /* Cf. A115099. */

#define bfilename_A261236 "b261236.txt"
#define bfilename_A261237 "b261237.txt"


int main(int argc, char **argv)
{
    if(argc < 2)
     {
       fprintf(stderr,"Usage: %s up_to_n\n", *argv);
       exit(1);
     }

    else
     {
       u64 up_to_n = tou64(atol(*(argv+1)));
       u64 n;
       u64 last1, last2;
       u64 msd1, msd2;
       FILE *fp_Alast_msd1, *fp_Alast_msd2;
       FILE *fp_A261236, *fp_A261237;

       if(NULL == (fp_Alast_msd1 = fopen(bfilename_Alast_msd1,"a")))
        {
          fprintf(stderr,"%s: Could not open file \"%s\" for output!\n", *argv, bfilename_Alast_msd1);
          exit(1);
        }

       if(NULL == (fp_Alast_msd2 = fopen(bfilename_Alast_msd2,"a")))
        {
          fprintf(stderr,"%s: Could not open file \"%s\" for output!\n", *argv, bfilename_Alast_msd2);
          exit(1);
        }

       if(NULL == (fp_A261236 = fopen(bfilename_A261236,"a")))
        {
          fprintf(stderr,"%s: Could not open file \"%s\" for output!\n", *argv, bfilename_A261236);
          exit(1);
        }

       if(NULL == (fp_A261237 = fopen(bfilename_A261237,"a")))
        {
          fprintf(stderr,"%s: Could not open file \"%s\" for output!\n", *argv, bfilename_A261237);
          exit(1);
        }

       for(n=0; n <= up_to_n; n++)
        {
          printf("%Lu %Lu\n", n, A261234(n,&last1,&last2,&msd1,&msd2));
          fflush(stdout);
          fprintf(fp_Alast_msd1,"%Lu %Lu\n", n, last1);
          fflush(fp_Alast_msd1);
          fprintf(fp_Alast_msd2,"%Lu %Lu\n", n, last2);
          fflush(fp_Alast_msd2);
          fprintf(fp_A261236,"%Lu %Lu\n", n, msd1);
          fflush(fp_A261236);
          fprintf(fp_A261237,"%Lu %Lu\n", n, msd2);
          fflush(fp_A261237);
        }
     }

}