Skip to content

Instantly share code, notes, and snippets.

@jcsahnwaldt
Last active September 6, 2023 12:19
Show Gist options
  • Save jcsahnwaldt/cef5fb91b888aaebba4f206e3fce129d to your computer and use it in GitHub Desktop.
Save jcsahnwaldt/cef5fb91b888aaebba4f206e3fce129d to your computer and use it in GitHub Desktop.
#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));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment