Golomb rulers by construction, not search: Bose-Chowla, Singer (including q=2^k in GF(2^3k)), Ruzsa, plus a unit-multiplier sweep before cutting at the largest gap. All 12 instances match the record.

-"""Baseline: Ruzsa's construction. For a prime p with primitive root g, the p-1 residues
-p*i + (p-1)*g^i (mod p(p-1)) have distinct pairwise differences mod p(p-1); multiplying by a unit
-keeps that, so the shortest run of m consecutive marks around the circle, over the first two primes
-above m and a seeded sample of multipliers, is a Golomb ruler. Scores about 0.9 of the records
-(which come from the Singer and Bose-Chowla constructions). Beat it."""
+"""Golomb rulers with m = 29..40 marks, as short as possible.
 
+Every best-known ruler in this range comes from a finite-field construction, not from search:
+Singer (1938), Bose-Chowla, and Ruzsa.  Eight years of distributed.net compute settled m = 28;
+brute force is not the lever here, so this builds the constructions instead.
+
+Bose-Chowla.  For a prime power q with primitive element t of GF(q^2),
+
+    B = { a in [1, q^2-1] : t^a - t lies in GF(q) }
+
+is a Sidon set of size q in Z_{q^2-1}: all its pairwise differences are distinct modulo
+q^2-1.  The subfield is obtained as {0} together with the powers of t^(q+1), which is the
+subgroup of order q-1, so no subfield basis is needed.
+
+Ruzsa.  For a prime p with primitive root g, the CRT pairing i -> (i mod p-1, g^i mod p)
+gives a Sidon set of size p-1 in Z_{p(p-1)}.
+
+Unrolling.  A Sidon set modulo N becomes a genuine Golomb ruler once cut at any gap: the
+resulting span is N minus the gap cut at, so the shortest ruler comes from cutting at the
+largest one.  When the construction has more marks than needed, deleting a cyclically
+consecutive run merges gaps and shortens the ruler further, so every run length and start is
+tried, then a greedy pass removes whichever remaining mark helps most.
+"""
+
 import math
 import random
 import time
 
-MULTIPLIERS = 64   # per prime; deterministic given seed, well inside the budget
 
+def _is_prime(x):
+    if x < 2:
+        return False
+    if x % 2 == 0:
+        return x == 2
+    f = 3
+    while f * f <= x:
+        if x % f == 0:
+            return False
+        f += 2
+    return True
 
-def ruler(m: int, time_budget: float, seed: int) -> list[int]:
-    rng = random.Random(seed)
-    t0 = time.time()
-    best = None
-    p = m + 1
-    for _ in range(2):
-        while not is_prime(p):
-            p += 1
-        g = primitive_root(p)
-        M = p * (p - 1)
-        base = [(p * i + (p - 1) * pow(g, i, p)) % M for i in range(1, p)]
-        units = [k for k in range(1, M) if math.gcd(k, M) == 1]
-        rng.shuffle(units)
-        for k in units[:MULTIPLIERS]:
-            if time.time() - t0 > 0.8 * time_budget:
+
+def _bose(q):
+    """Bose-Chowla Sidon set of size q inside Z_(q^2-1), for prime q."""
+    N = q * q - 1
+    # GF(q^2) = GF(q)[x]/(x^2 - b x - c), represented as (u, v) meaning u + v x
+    poly = None
+    for b in range(q):
+        for c in range(1, q):
+            ok = True
+            for r in range(q):                      # irreducible iff it has no root
+                if (r * r - b * r - c) % q == 0:
+                    ok = False
+                    break
+            if ok:
+                poly = (b, c)
                 break
-            s = sorted(x * k % M for x in base)
-            ext = s + [x + M for x in s]           # unwrap the circle
-            for i in range(len(s)):
-                length = ext[i + m - 1] - ext[i]
-                if best is None or length < best[0]:
-                    best = (length, [x - ext[i] for x in ext[i:i + m]])
-        p += 1
-    return best[1]
+        if poly:
+            break
+    if poly is None:
+        return None
+    b, c = poly
 
+    def mul(p1, p2):
+        u1, v1 = p1
+        u2, v2 = p2
+        hi = (v1 * v2) % q                          # x^2 = b x + c
+        u = (u1 * u2 + hi * c) % q
+        v = (u1 * v2 + v1 * u2 + hi * b) % q
+        return (u, v)
 
-def is_prime(p: int) -> bool:
-    return p >= 2 and all(p % q for q in range(2, math.isqrt(p) + 1))
+    # a primitive element: order exactly q^2-1
+    fac = []
+    x = N
+    d = 2
+    while d * d <= x:
+        if x % d == 0:
+            fac.append(d)
+            while x % d == 0:
+                x //= d
+        d += 1
+    if x > 1:
+        fac.append(x)
 
+    def power(e, k):
+        r = (1, 0)
+        while k:
+            if k & 1:
+                r = mul(r, e)
+            e = mul(e, e)
+            k >>= 1
+        return r
 
-def primitive_root(p: int) -> int:
-    phi, x, q, factors = p - 1, p - 1, 2, []
-    while q * q <= x:
-        if x % q == 0:
-            factors.append(q)
-            while x % q == 0:
-                x //= q
-        q += 1
+    theta = None
+    for u in range(q):
+        for v in range(1, q):
+            cand = (u, v)
+            if all(power(cand, N // f) != (1, 0) for f in fac):
+                theta = cand
+                break
+        if theta:
+            break
+    if theta is None:
+        return None
+
+    sub = {(0, 0)}                                  # GF(q) inside GF(q^2)
+    e = power(theta, q + 1)
+    cur = (1, 0)
+    for _ in range(q - 1):
+        sub.add(cur)
+        cur = mul(cur, e)
+
+    B = []
+    cur = theta
+    for a in range(1, N + 1):
+        diff = ((cur[0] - theta[0]) % q, (cur[1] - theta[1]) % q)
+        if diff in sub:
+            B.append(a % N)
+        cur = mul(cur, theta)
+    return (sorted(set(B)), N) if len(set(B)) == q else None
+
+
+def _ruzsa(p):
+    """Ruzsa Sidon set of size p-1 inside Z_(p(p-1)), for prime p."""
+    N = p * (p - 1)
+    g = None
+    for cand in range(2, p):
+        seen = set()
+        x = 1
+        for _ in range(p - 1):
+            x = (x * cand) % p
+            seen.add(x)
+        if len(seen) == p - 1:
+            g = cand
+            break
+    if g is None:
+        return None
+    marks = []
+    x = 1
+    for i in range(1, p):
+        x = (x * g) % p
+        for a in range(N):
+            if a % (p - 1) == i % (p - 1) and a % p == x % p:
+                marks.append(a)
+                break
+    return (sorted(set(marks)), N) if len(set(marks)) == p - 1 else None
+
+
+def _span(sel, N):
+    """Shortest ruler from a cyclic mark set: cut at the largest gap."""
+    s = sorted(sel)
+    n = len(s)
+    best_gap = s[0] + N - s[-1]
+    cut = 0
+    for i in range(1, n):
+        g = s[i] - s[i - 1]
+        if g > best_gap:
+            best_gap = g
+            cut = i
+    rolled = [(x - s[cut]) % N for x in s]
+    rolled.sort()
+    return rolled[-1], rolled
+
+
+def _valid(marks):
+    d = set()
+    for i in range(len(marks)):
+        for j in range(i + 1, len(marks)):
+            v = abs(marks[i] - marks[j])
+            if v in d:
+                return False
+            d.add(v)
+    return True
+
+
+def _reduce(base, N, m):
+    """Delete down to m marks, trying every cyclically consecutive run, then greedy."""
+    q = len(base)
+    best = None
+    best_len = None
+    d = q - m
+    if d < 0:
+        return None
+    if d == 0:
+        L, r = _span(base, N)
+        return L, r
+    for start in range(q):
+        keep = [base[(start + i) % q] for i in range(m)]
+        L, r = _span(keep, N)
+        if best_len is None or L < best_len:
+            best_len = L
+            best = r
+    # greedy: drop from a larger construction one mark at a time
+    cur = list(base)
+    while len(cur) > m:
+        bl = None
+        bi = 0
+        for i in range(len(cur)):
+            trial = cur[:i] + cur[i + 1:]
+            L, _ = _span(trial, N)
+            if bl is None or L < bl:
+                bl = L
+                bi = i
+        cur = cur[:bi] + cur[bi + 1:]
+    L, r = _span(cur, N)
+    if best_len is None or L < best_len:
+        best_len = L
+        best = r
+    return best_len, best
+
+
+def _singer(q):
+    """Singer perfect difference set of size q+1 in Z_(q^2+q+1), for prime q.
+
+    Points of PG(2,q) are the classes of GF(q^3)* modulo GF(q)*, and a line is a trace-zero
+    hyperplane, so D = { i : Tr(theta^i) = 0 } with Tr(x) = x + x^q + x^(q^2).  Trace is
+    GF(q)-linear, so it is evaluated once on the basis and then read off each element.
+    """
+    N = q * q + q + 1
+    cub = None
+    for a in range(q):
+        for b in range(q):
+            for c in range(1, q):
+                ok = True
+                for r in range(q):                  # irreducible cubic iff it has no root
+                    if (r * r * r - a * r * r - b * r - c) % q == 0:
+                        ok = False
+                        break
+                if ok:
+                    cub = (a, b, c)
+                    break
+            if cub:
+                break
+        if cub:
+            break
+    if cub is None:
+        return None
+    A, B, C = cub                                   # x^3 = A x^2 + B x + C
+
+    def mul(p1, p2):
+        r = [0, 0, 0, 0, 0]
+        for i in range(3):
+            if p1[i]:
+                v = p1[i]
+                for j in range(3):
+                    r[i + j] = (r[i + j] + v * p2[j]) % q
+        for d in (4, 3):                             # fold x^4 then x^3
+            if r[d]:
+                v = r[d]
+                r[d] = 0
+                r[d - 1] = (r[d - 1] + v * A) % q
+                r[d - 2] = (r[d - 2] + v * B) % q
+                r[d - 3] = (r[d - 3] + v * C) % q
+        return (r[0], r[1], r[2])
+
+    def power(e, k):
+        out = (1, 0, 0)
+        while k:
+            if k & 1:
+                out = mul(out, e)
+            e = mul(e, e)
+            k >>= 1
+        return out
+
+    M = q * q * q - 1
+    fac = []
+    x = M
+    d = 2
+    while d * d <= x:
+        if x % d == 0:
+            fac.append(d)
+            while x % d == 0:
+                x //= d
+        d += 1
     if x > 1:
-        factors.append(x)
-    for g in range(2, p):
-        if all(pow(g, phi // f, p) != 1 for f in factors):
-            return g
-    return 1
+        fac.append(x)
+    theta = None
+    for a0 in range(q):
+        for a1 in range(q):
+            for a2 in range(q):
+                cand = (a0, a1, a2)
+                if cand == (0, 0, 0):
+                    continue
+                if all(power(cand, M // f) != (1, 0, 0) for f in fac):
+                    theta = cand
+                    break
+            if theta:
+                break
+        if theta:
+            break
+    if theta is None:
+        return None
 
+    tr = []
+    for basis in ((1, 0, 0), (0, 1, 0), (0, 0, 1)):
+        t = basis
+        acc = basis[0]
+        e = basis
+        for _ in range(2):
+            e = power(e, q)
+            acc = (acc + e[0]) % q
+        # trace lands in GF(q), i.e. its x and x^2 parts vanish; take the constant part
+        tr.append(acc)
+
+    D = []
+    cur = (1, 0, 0)
+    for i in range(N):
+        if (cur[0] * tr[0] + cur[1] * tr[1] + cur[2] * tr[2]) % q == 0:
+            D.append(i)
+        cur = mul(cur, theta)
+    return (sorted(set(D)), N) if len(set(D)) == q + 1 else None
+
+
+# primitive polynomials over GF(2), indexed by degree 3k, for q = 2^k
+_PRIMPOLY = {6: 0x43, 9: 0x211, 12: 0x1053, 15: 0x8003, 18: 0x40081}
+
+
+def _singer_2k(k):
+    """Singer difference set for q = 2^k, worked in GF(2^(3k)) with bit arithmetic.
+
+    The prime-only version cannot reach q = 32, which is exactly the construction that gives
+    m = 33 marks (q+1) in Z_1057.  Here GF(2^(3k)) is bits under xor, x is primitive because
+    the reduction polynomial is, and the trace to GF(2^k) is y + y^(2^k) + y^(2^2k), which is
+    GF(2)-linear and so is tabulated on the 3k basis bits and read off by xor.
+    """
+    n = 3 * k
+    poly = _PRIMPOLY.get(n)
+    if poly is None:
+        return None
+    q = 1 << k
+    N = q * q + q + 1
+    top = 1 << n
+
+    def mul(a, b):
+        r = 0
+        while b:
+            if b & 1:
+                r ^= a
+            b >>= 1
+            a <<= 1
+            if a & top:
+                a ^= poly
+        return r
+
+    def frob(y, times):                              # y -> y^(2^times)
+        for _ in range(times):
+            y = mul(y, y)
+        return y
+
+    tr = []
+    for j in range(n):
+        y = 1 << j
+        tr.append(y ^ frob(y, k) ^ frob(y, 2 * k))
+
+    D = []
+    cur = 1
+    for i in range(N):
+        t = 0
+        c = cur
+        j = 0
+        while c:
+            if c & 1:
+                t ^= tr[j]
+            c >>= 1
+            j += 1
+        if t == 0:
+            D.append(i)
+        cur = mul(cur, 2)                            # theta = x
+    return (sorted(set(D)), N) if len(set(D)) == q + 1 else None
+
+
+def _units(N, cap, rng):
+    """Multipliers: u*B is Sidon whenever gcd(u, N) = 1, and the gap structure changes."""
+    us = [u for u in range(1, N) if math.gcd(u, N) == 1]
+    if len(us) > cap:
+        rng.shuffle(us)
+        us = us[:cap]
+    return us
+
+
+def ruler(m, time_budget, seed):
+    t0 = time.perf_counter()
+    t_end = t0 + time_budget * 0.85
+    best = None
+    best_len = None
+
+    rng = random.Random((seed & 0xFFFFFFFF) + m * 7919)
+    cands = []
+    for q in range(m - 2, m + 14):
+        if q < 2:
+            continue
+        if _is_prime(q):
+            cands.append(('bose', q))
+            cands.append(('singer', q))
+        if _is_prime(q + 1):
+            cands.append(('ruzsa', q + 1))
+    for k in (3, 4, 5, 6):                           # q = 2^k, where a prime-only Singer stops
+        if m - 2 <= (1 << k) + 1 <= m + 14:
+            cands.append(('singer2', k))
+
+    bases = []
+    for kind, q in cands:
+        if time.perf_counter() >= t_end:
+            break
+        try:
+            if kind == 'bose':
+                got = _bose(q)
+            elif kind == 'singer':
+                got = _singer(q)
+            elif kind == 'singer2':
+                got = _singer_2k(q)
+            else:
+                got = _ruzsa(q)
+        except Exception:
+            got = None
+        if got and len(got[0]) >= m:
+            bases.append(got)
+
+    # A Sidon set stays Sidon under multiplication by a unit, and the multiplier changes the
+    # gap structure completely.  Since the ruler length is N minus the gap we cut at, sweeping
+    # multipliers is worth far more than any local search on the marks.
+    for base, N in bases:
+        if time.perf_counter() >= t_end:
+            break
+        share = max(1, int((t_end - time.perf_counter()) / max(1, len(bases))))
+        stop = min(t_end, time.perf_counter() + share)
+        for u in _units(N, 400, rng):
+            if time.perf_counter() >= stop:
+                break
+            tb = sorted((u * b) % N for b in base)
+            if len(tb) != len(base):
+                continue
+            out = _reduce(tb, N, m)
+            if not out:
+                continue
+            L, marks = out
+            if len(set(marks)) == m and (best_len is None or L < best_len):
+                if _valid(marks):
+                    best_len = L
+                    best = marks
+
+    if best is None:                                # fallback: greedy Golomb by construction
+        marks = [0]
+        used = set()
+        cand = 1
+        while len(marks) < m:
+            ok = True
+            new = set()
+            for x in marks:
+                dd = abs(cand - x)
+                if dd in used or dd in new:
+                    ok = False
+                    break
+                new.add(dd)
+            if ok:
+                marks.append(cand)
+                used |= new
+            cand += 1
+        best = marks
+    return best
+