// compile with gcc -std=c99 -o A091333 A091333.c
#include <stdio.h>
#include <stdlib.h>

typedef unsigned long long ul; // unsigned long long is typically 64-bits long
typedef unsigned char ct; // complexity data type (8 bits is sufficient)

ul MAXNM; // calculate complexity with any operation as last operation up to MAXNM
ul MAXN; // calculate complexity with addition or multiplication as last operation up to MAXN
ul* E; // E[x] == largest number of complexity x, A000792 in OEIS, it is the same for both bases {1,+,*} and {1,+,*,-}
ct* complexity; // values of A091333

ct minComplexity(ul n)
{
  ct c = 1;
  while (E[c] < n)
    c++;
  return c;
}

// An upper bound on complexity for all numbers up to n.
ct maxComplexityUpTo(ul n)
{
  ul mc = 0;
  while(n > 3)
  {
    n /= 2;
    mc += 3;
  }
  mc += n;
  return mc;
}

// Returns an upper bound on complexity which is obtained by writing the number in binary.
ct maxComplexity(ul n)
{
  return (62-__builtin_clzll(n))*2+__builtin_popcountll(n)+1;
}

void cleanUp()
{
  free(E);
  free(complexity);
}


void precalcE()
{
  for (ul i = 0; i < 4; i++)
    E[i] = i;
  for (ul i = 4; ; i++)
  {
    switch (i%3)
    {
    case 0:
      E[i] = 3*E[i-3];
      break;
    case 1:
    case 2:
      E[i]= 2*E[i-2];
      break;
    }
    // break when overflows...
    if (E[i] < E[i-1])
      break;
  }
}

// It can be proven that if n = a + b and a >= b, then b < n^(~0.585).
// For so small b, we can say that E[A091333(a)]+E[A091333(b)] monotonically decreases as A091333(b) goes from 1..n/2 if A091333(a) + A091333(b) = A091333(n).
ul maxAddCheck(ul n, ct f)
{
  ul maxBcompl = 0;
  while (E[maxBcompl] < n/2 && E[maxBcompl] + E[f-1-maxBcompl] >= n)
    maxBcompl++;
  return E[maxBcompl] < n/2 ? E[maxBcompl] : n/2;
}

// If A091333(n) = A091333(a) + A091333(b) and n = a - b (a - b gives the shortest expression for n)
// we can write A091333(b) = A091333(n) - A091333(a) <= current A091333(n) - minimum A091333(n).
// Then take E(x) on both sides and note that x <= E(A091333(x)).
ul maxSubCheck(ul n, ct f)
{
  return E[f-(minComplexity(n))];
}

void init()
{
  E = malloc(3*8*sizeof(ul)*sizeof(ul));
  if (!E)
  {
    printf("Unable to allocate memory!\n");
    exit(EXIT_FAILURE);
  }
  precalcE();
  MAXN = MAXNM + maxSubCheck(MAXNM, maxComplexityUpTo(MAXNM));
  complexity = malloc((MAXN+1)*(sizeof(ct)));
  if (!complexity)
  {
    printf("Unable to allocate memory! You need contiguous %lld bytes!\n", MAXN+1);
    exit(EXIT_FAILURE);
  }
}

void calcMinus()
{
  complexity[0] = 0;
  complexity[1] = 1;
  for (ul i = 2; i <= MAXN; i++)
    complexity[i] = maxComplexity(i);
  int changes = 1;
  while (changes)
  {
    changes = 0;
    for (ul i = 2; i*i <= MAXN; i++)
      for (ul ii = i+i, k = 2; ii <= MAXN; ii += i, k++)
	if (complexity[ii] > complexity[i] + complexity[k])
	{
	  complexity[ii] = complexity[i] + complexity[k];
	  changes = 1;
	}
    printf("Multiplication done\n");
    fflush(stdout);
    for (ul i = 1; i <= MAXN; i++)
    {
      ul mac = maxAddCheck(i, complexity[i]);
      for (ul j = 1; j <= mac; j++)
	if (complexity[i] > complexity[j] + complexity[i-j])
	{
	  complexity[i] = complexity[j] + complexity[i-j];
	  mac = maxAddCheck(i, complexity[i]);
	  changes = 1;
	}
    }
    printf("Addition done\n");
    fflush(stdout);
    for (ul i = MAXNM; i >= 1; i--)
    {
      ul msc = maxSubCheck(i, complexity[i]);
      for (ul j = 1; j <= msc; j++)
      {
	if (complexity[i] > complexity[i+j] + complexity[j])
	{
	  complexity[i] = complexity[i+j]+complexity[j];
	  msc = maxSubCheck(i, complexity[i]);
	  changes = 1;
	}
      }
    }
    printf("Subtraction done\n");
    fflush(stdout);
  }
}

void output(char* fn)
{
  FILE* fmdata = fopen(fn, "wb");
  ul written = fwrite(complexity, sizeof(ct), MAXNM+1, fmdata);
  if (written < MAXNM+1)
    printf("Data cannot be written!\n");
  fclose(fmdata);
}

int main(int argc, char** argv)
{
  if (argc != 3)
  {
    printf("Usage: A091333 <n> <filename>\n where\n\tn is the maximum number for which to compute A091333\n\tfilename is the name of the file where to output the results");
  }
  if (sizeof(ul) != 8)
  {
    printf("Recompile with 64 bit unsigned long long!\n");
    exit(EXIT_FAILURE);
  }
  sscanf(argv[1], "%llu", &MAXNM);
  init();
  calcMinus();
  output(argv[2]);
  cleanUp();
  return 0;
}