// thin385.c -- job #385: T1 of research/moving-cutoff-parity.md (4) at x = 2^j, j = jmin..jmax (<= 29), with the // independent-thinning control: for odd n in J = (x/2, x], w(n) = log n * Bernoulli(2/log n) (Cramer), T1_thin = sum w(n) mu^2(n) A_y(n), // E[T1_thin] = 2 sum_{n odd sqfree} A_y(n) exactly, Var = sum_{n odd sqfree} 2 log n (1 - 2/log n) A_y(n)^2 exactly; SEEDS draws. // Derived from census13.c (return #34): full spf sieve to 2^jmax, divisor subsets per n, long double accumulators. // Columns: j | x | y | T1/x - C2 | E[T1_thin]/x | sd_thin/x | draws (T1_thin - E)/x ... | A_y^2 sum/x #include #include #include #include static const long double C2 = 0.6601618158468695739278121100145557784326L; static uint64_t rng_s[2]; static inline uint64_t rotl(uint64_t v, int k) { return (v << k) | (v >> (64 - k)); } static uint64_t xs128p(void) { uint64_t s0 = rng_s[0], s1 = rng_s[1], r = s0 + s1; s1 ^= s0; rng_s[0] = rotl(s0, 55) ^ s1 ^ (s1 << 14); rng_s[1] = rotl(s1, 36); return r; } static double unif(void) { return (xs128p() >> 11) * (1.0 / 9007199254740992.0); } #define SEEDS 4 int main(int argc, char **argv) { if (argc < 3) { fprintf(stderr, "usage: thin385 jmin jmax\n"); return 2; } int jmin = atoi(argv[1]), jmax = atoi(argv[2]); if (jmin < 4 || jmax > 29 || jmin > jmax) { fprintf(stderr, "4 <= jmin <= jmax <= 29\n"); return 2; } uint64_t X = 1ULL << jmax; uint32_t *spf = calloc(X + 1, sizeof(uint32_t)); for (uint64_t i = 2; i <= X; i++) if (!spf[i]) { spf[i] = (uint32_t)i; if (i * i <= X) for (uint64_t k = i * i; k <= X; k += i) if (!spf[k]) spf[k] = (uint32_t)i; } printf("j | x | y | T1/x - C2 | E[T1_thin]/x | sd_thin/x"); for (int s = 0; s < SEEDS; s++) printf(" | draw%d (T1_thin-E)/x", s); printf(" | sum A_y^2 / x | sum log n A_y^2 / x | P_J/x\n"); for (int j = jmin; j <= jmax; j++) { uint64_t x = 1ULL << j, h = x / 2; uint64_t y = (12 * j) % 25 == 0 ? (1ULL << (12 * j / 25)) : (uint64_t)ceil(pow(2.0, 12.0 * j / 25.0)); long double T1 = 0, E = 0, V = 0, A2s = 0, LA2s = 0, draw[SEEDS]; for (int s = 0; s < SEEDS; s++) draw[s] = 0; uint64_t seedstate[SEEDS][2]; for (int s = 0; s < SEEDS; s++) { seedstate[s][0] = 0x9E3779B97F4A7C15ULL * (s + 1) + j; seedstate[s][1] = 0xD1B54A32D192ED03ULL ^ (uint64_t)(s + 17) * 0x100000001B3ULL; } long double PJ = 0; for (uint64_t n = h + 1; n <= x; n++) { // all n for the real T1 and P_J; the thinning control uses odd n only uint64_t u = n, pr[16]; int k = 0, sqf = 1; while (u > 1) { uint64_t q = spf[u]; int c = 0; while (u % q == 0) { u /= q; c++; } pr[k++] = q; if (c > 1) sqf = 0; } { uint64_t m0 = n - 2, p0 = spf[m0], t0 = m0; while (t0 % p0 == 0) t0 /= p0; if (t0 == 1) PJ += logl((long double)p0); } if (!sqf) continue; long double Ay = 0; for (uint32_t s = 0; s < (1u << k); s++) { uint64_t d = 1; long double logd = 0; int bits = 0; for (int i = 0; i < k; i++) if (s >> i & 1) { d *= pr[i]; logd += logl((long double)pr[i]); bits++; } if (d <= y) Ay += -((bits & 1) ? -1.0L : 1.0L) * logd; } // real: Lambda(n-2) uint64_t m = n - 2, p = spf[m], t = m; while (t % p == 0) t /= p; if (t == 1) T1 += logl((long double)p) * Ay; if (!(n & 1)) continue; long double ln = logl((long double)n), pn = 2.0L / ln; E += 2 * Ay; V += ln * ln * pn * (1 - pn) * Ay * Ay; A2s += Ay * Ay; LA2s += ln * Ay * Ay; for (int s = 0; s < SEEDS; s++) { rng_s[0] = seedstate[s][0]; rng_s[1] = seedstate[s][1]; double r = unif(); seedstate[s][0] = rng_s[0]; seedstate[s][1] = rng_s[1]; if (r < pn) draw[s] += ln * Ay - 0; } } long double xl = (long double)x; printf("%d | %llu | %llu | %.7Lf | %.7Lf | %.7Lf", j, (unsigned long long)x, (unsigned long long)y, T1 / xl - C2, E / xl, sqrtl(V) / xl); for (int s = 0; s < SEEDS; s++) printf(" | %.7Lf", (draw[s] - E) / xl); printf(" | %.6Lf | %.6Lf | %.8Lf\n", A2s / xl, LA2s / xl, PJ / xl); fflush(stdout); } return 0; }