partition.c

#include <stdio.h>
#include <math.h>

#define MAX 100

static int memo[MAX+1];

static int partitions(int n) {
  int p = memo[n];
  if (p != 0) return p;

  double s = sqrt(24*n + 1);
  int kmin = (int)((1 - s) / 6);
  int kmax = (int)((1 + s) / 6);
  for (int k = kmin; k <= kmax; k++) {
    if (k == 0) continue;
    int a = partitions(n-k*(3*k-1)/2);
    if (k % 2) p += a; else p -= a;
  }

  memo[n] = p;
  return p;
}

int main(void) {
  memo[0] = 1;
  for (int n = 0; n <= MAX; n++) {
    printf("%d %d\n", n, partitions(n));
  }
}