#include "flint/fmpz.h"
#include "arb.h"

/* Prerequisites:
 *   http://arblib.org/
 *   http://www.flintlib.org/
 * and either
 *   http://mpir.org/
 * or
 *   https://gmplib.org/
 *
 * Compile with some variant of
 *   gcc -O2 -o A278209 A278209.c -L/usr/local/lib -larb -lflint -lgmp
*/

ulong partmod(const ulong n, const ulong m);
ulong a(ulong n);
int main();

int
main(int argc, char **argv)
{
	(void)argc;
	(void)argv;
	ulong n = 2;
	printf("1");
	for (n = 2; n <= 10000; n++) {
		printf(", %lu", a(n));
		fflush(stdout);
	}
	return 0;
}


ulong a(ulong n)
{
	_Bool *v;	/* You could use a bit array here, but that's probably slower. */
	v = calloc(n, sizeof(_Bool));
	//if (!v) crash_and_burn();
	ulong s = 1;
	ulong k = 1;
	v[1]=1;
	
	
	while (1) {
		ulong t = partmod(++k, n);
		if(v[t]==0) {
			v[t]=1;
			if(++s==n) {
				free(v);
				return(k);
			}
		}
	}
	return 0;	/* can only happen on overflow, return an invalid value */
}


ulong
partmod(const ulong n, const ulong m)
{
	fmpz_t N, M, P, Pm;
	fmpz_init(N);
	fmpz_init(M);
	fmpz_set_ui(N, n);
	fmpz_set_ui(M, m);
	fmpz_init(P);
	partitions_fmpz_fmpz(P, N, 1);
	fmpz_init(Pm);
	fmpz_mod(Pm, P, M);
	ulong ret = fmpz_get_ui(Pm);
	fmpz_clear(N);
	fmpz_clear (M);
	fmpz_clear(P);
	fmpz_clear(Pm);
	return ret;
}