// t1main.c -- job #385: the deterministic Bombieri-Vinogradov main term of T1 of research/moving-cutoff-parity.md (4) // at x = 2^j with y as printed by the census for that j. No prime above max(y, sqrt x) is used. // sigma(x,y) = sum_{d<=y odd sqfree} sum_{b odd sqfree, [d,b^2]<=x} -mu(d) mu(b) log d / phi([d,b^2]) (sharp: the model expectation of T1 is P_J * sigma, P_J = sum_J Lambda(n-2) ~ x/2) // sigma_inf(x,y) = A2 * sum_{d<=y odd sqfree} -mu(d) g(d) log d / phi(d), g(p) = (p-1)^2/(p(p-1)-1) (the note's (8) form, b unbounded; limit 2 C2 / A2 * A2 = 2 C2 as y -> inf) // For squarefree d, b with g = gcd(d,b): [d,b^2] = d b^2 / g and phi([d,b^2]) = phi(d) b phi(b) / phi(g). // Enumeration: for each d, for each divisor g of d, b = g * c with gcd(c, d) = 1, c odd squarefree, d b^2 / g <= x. // usage: t1main j y -> j | x | y | sigma/2 - C2 | sigma_inf/2 - C2 | (sigma - sigma_inf)/2 | pairs #include #include #include #include static const double C2 = 0.6601618158468696; static const double A2 = 0.7479116272384044; static uint64_t gcdu(uint64_t a, uint64_t b) { while (b) { uint64_t t = a % b; a = b; b = t; } return a; } int main(int argc, char **argv) { if (argc < 3) { fprintf(stderr, "usage: t1main j y\n"); return 2; } int j = atoi(argv[1]); uint64_t y = strtoull(argv[2], 0, 10); long double x = ldexpl(1.0L, j); uint64_t BMAX = (uint64_t)sqrtl(x) + 2, N = y > BMAX ? y : BMAX; int8_t *mu = malloc(N + 1); uint32_t *phi = malloc((N + 1) * 4); uint32_t *spf = calloc(N + 1, 4); for (uint64_t i = 2; i <= N; i++) if (!spf[i]) for (uint64_t k = i; k <= N; k += i) if (!spf[k]) spf[k] = (uint32_t)i; mu[1] = 1; phi[1] = 1; for (uint64_t n = 2; n <= N; n++) { uint32_t p = spf[n]; uint64_t m = n / p; if (m % p == 0) { mu[n] = 0; phi[n] = phi[m] * p; } else { mu[n] = -mu[m]; phi[n] = phi[m] * (p - 1); } } long double sharp = 0, inf = 0; uint64_t pairs = 0; for (uint64_t d = 1; d <= y; d += 2) { if (!mu[d]) continue; long double ld = logl((long double)d), w = -(long double)mu[d] * ld; long double gd = 1; uint64_t pr[16]; int k = 0; uint64_t u = d; while (u > 1) { uint32_t p = spf[u]; u /= p; pr[k++] = p; gd *= (long double)(p - 1) * (p - 1) / ((long double)p * (p - 1) - 1); } inf += w * gd / phi[d]; long double sb = 0; for (uint32_t s = 0; s < (1u << k); s++) { // g = product of a subset of the primes of d uint64_t g = 1; for (int i = 0; i < k; i++) if (s >> i & 1) g *= pr[i]; // b = g c, gcd(c, d) = 1, c odd squarefree, d g c^2 <= x -> c <= sqrt(x / (d g)) uint64_t cmax = (uint64_t)sqrtl(x / ((long double)d * g)); while ((long double)d * g * cmax * cmax > x) cmax--; while ((long double)d * g * (cmax + 1) * (cmax + 1) <= x) cmax++; for (uint64_t c = 1; c <= cmax; c += 2) { if (!mu[c] || gcdu(c, d) != 1) continue; uint64_t b = g * c; long double ph = (long double)phi[d] * b * (long double)phi[g] * phi[c] / phi[g]; // phi(b) = phi(g) phi(c), / phi(g) sb += (long double)(mu[g] * mu[c]) / ph; pairs++; } } sharp += w * sb; } printf("%d | %.0Lf | %llu | %.8Lf | %.8Lf | %.3Le | %llu\n", j, x, (unsigned long long)y, sharp / 2 - C2, A2 * inf / 2 - C2, (sharp - A2 * inf) / 2, (unsigned long long)pairs); return 0; }