Skip to content

Instantly share code, notes, and snippets.

@lifthrasiir
Created June 7, 2019 14:51
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save lifthrasiir/069791c1a56459f3938ab0930121de6b to your computer and use it in GitHub Desktop.
Save lifthrasiir/069791c1a56459f3938ab0930121de6b to your computer and use it in GitHub Desktop.
reasonably efficient enumerator for https://oeis.org/A033178
#include <stdio.h>
#include <stdlib.h>
int recur(int n, int m, int k, int prevsum, int prevprod) {
if (m <= 0 || prevprod >= n) return 0;
int sum = prevsum + k, prod = prevprod * k, rem = (sum + m - 1) - prod;
int count = (rem >= 0 && prevprod > 1 && rem % (prevprod - 1) == 0);
for (; sum <= 2 * n && prod < n; ++k, ++sum, prod += prevprod) count += recur(n, m - 1, k, sum, prod);
return count;
}
int a(int n) {
if (n <= 0) return 0;
if (n == 1) return -1;
return recur(n, n, 2, 0, 1) + (n == 2);
}
int main(int argc, char **argv) {
if (argc < 2) return 1;
int limit = atoi(argv[1]);
for (int i = 2; i <= limit; ++i) printf("%d %d\n", i, a(i));
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment