φ⊢⟦⟧

Σ = { 0 1 2 3 4 5 6 7 8 9 n + × ( ) = φ ₀ ₁ ₂ ₃ ₄ ₅ ₆ ₇ ₈ ₉ }
N ::= 0 | [1-9][0-9]*            ⟵ ℕ⊢×
E ::= N | n | φᵢ(E) | (E) | E + E | E × E      ·   × ≻ +
D₁ ::= φᵢ(0) = E ;  φᵢ(n+1) = E
D₂ ::= φᵢ(0) = E ;  φᵢ(1) = E ;  φᵢ(n+2) = E
⟦⟧ : φᵢ(k) = E  ⟹  ⟦φᵢ⟧(k) = ⟦E⟧   ·   φᵢ(n+s) = E  ∧  k ≥ s  ⟹  ⟦φᵢ⟧(k) = ⟦E⟧[n ↦ k−s]
≺ : φᵢ(n+s) = E  ∧  φⱼ(A) ⊑ E  ⟹  j < i  ∨  (j = i  ∧  ⟦A⟧ < n+s)
⊨ φᵢ ↦ ⟨v₀,…,v₉⟩  ⟺  ∀k ∈ [0, 9]: ⟦φᵢ⟧(k) = vₖ
𝕂 = { (Dᵢ, ⟨v₀,…,v₉⟩) | ⊨ }   ·   ⇅ i

使う記号は、数字、n、+、×、括弧、=、関数の名前 φ と下付きの番号です。プログラムは漸化式で、D₁ は「0 のときの値」と「一つ前の値から次の値を作る式」、D₂ は「0 と 1 のときの値」と「二つ前までの値から次の値を作る式」です。⟦⟧ は実行の規則で、k が左辺の数と一致すればその式を、そうでなければ n に k−s を入れた漸化式を使います。式 E の中（⊑ は「中に現れる」）では、自分より前の番号の関数（φⱼ、j < i）と、自分自身のより小さい引数での値だけを使えます（≺）。これで、上から順に読めば、前の項目だけで次の項目が読めます。⊨ は「実行すると n = 0〜9 の出力が表のとおりになる」ことです。

既知の区画です。後者・倍数・三角数・平方・立方・べき・階乗・フィボナッチ数など、古典的な関数 20 個を、前の関数を使って積み上げる順に並べました。たとえば平方数 φ₆ は奇数 φ₄ を順に足して作り、立方数 φ₇ は平方数 φ₆ を使って作ります。各項目の下の行は n = 0〜9 の出力で、2〜1000 の数は数字原典の項目へ、⟵ φⱼ はそのプログラムが使っている前の関数へ移動できます。⟶ g の付いた項目は、記号原典の 𝔾 に同じ多項式の組があります。

ψ ::= ψ(0) = a ;  ψ(n+1) = E    ·   a ∈ {0, 1, 2}
𝔓 = { ψ | E ∈ 𝕋(1, 2, n, ψ(n); +, ×),  #(+,×) ≤ 4 }    ·   |𝔓| = 3 × 240,164 = 720,492
≅ : ψ ≅ ψ′  ⟺  a = a′  ∧  [E] = [E′]   ([E] ∈ ℤ[ψ, n])
≡ : ψ ≡ ψ′  ⟺  ∀n: ⟦ψ⟧(n) = ⟦ψ′⟧(n)        ·   𝔾 ∋ [ψ]≡  ⟺  |[ψ]≡ / ≅| ≥ 2
𝔠 = Σ q·nʲ·cⁿ   (q ∈ ℚ, c ∈ ℤ, 0ⁿ = [n = 0])
⊨𝔠 : 𝔠(0) = a  ∧  [E][ψ ↦ 𝔠] = 𝔠(n+1)  ⟹  ⟦ψ⟧ = 𝔠
⊨𝔯 : ∀φ ⊑ L, R :  φ(n+2) = α·φ(n+1) + β·φ(n)  ∧  L, R ∈ ⟨φ(n+k)⟩  ∧  L = R  (n = 0, 1)  ⟹  L ≡ R
ℓ : E = c·ψ(n) + p(n), ∂p = e  ⟹  ψ ⊲ (x−c)(x−1)^(e+1)  ·  c = 1 ⟹ (x−1)^(e+2)
D = ∂(ℓ(ψ) ∨ ℓ(ψ′)) :  ψ = ψ′ (n < D)  ⟹  ψ ≡ ψ′
≟ : L = R  (n < 16)  ∧  ¬⊨     ·   ⊭ : ∃n: ⟦ψ⟧(n) ≠ ⟦ψ′⟧(n)

𝔾 は「書き方は違うのに、同じ数列を出すプログラムの組」の区画です。ψ は 𝔾 用の小さなプログラムで、0 のときの値 a（0, 1, 2 のどれか）と、一つ前の値 ψ(n) と n から次の値を作る式 E で書きます。E は 1、2、n、ψ(n) を + と × で最大 4 回つないだ式で、その全部（𝔓、720,492 本）を機械で作りました。式を展開して同じ多項式になるもの（≅、たとえば ψ(n)×2 と 2×ψ(n)）は自明な言い換えとして一つにまとめ、それでも同じ数列になる組だけを載せています。
証明には二つの方法を使います。⊨𝔠 は「閉じた式 𝔠 を予想し、0 での値が合うことと、𝔠 を ψ(n) に代入すると 𝔠(n+1) になることを確かめる」帰納法です。⊨𝔯 は、どちらの辺も同じ 2 項の漸化式を満たすときに「最初の 2 項が合えば全部合う」ことを使います。どちらもページの中で計算し直しています。≟ は 16 項まで一致を確かめたが、このページの方法では証明できていないもの、⊭ は途中までは一致して、その後に食い違う組です。ℓ は一次の形のプログラムが満たす漸化式の特性多項式（∂ はその次数）、D は二つの特性多項式の最小公倍数（∨）の次数で、一次の形のプログラムどうしなら「何項一致すれば同じと言えるか」の上限を与える規則で、下の ≡? 実験台で使います。

帯は五つです。𝔓 · #≤3 は演算が 3 回以下の式で見つかった組、𝔓 · #=4 は 4 回に広げて新しく増えた組です（番号は q01 から順で、後から足しても変わりません）。𝕂 ≡ は 𝕂 の関数どうしの有名な等式、⊭ は「最初の 5 項は一致するのに 6 項目で食い違う」組（この空間で一致が続く最長の長さが 5 でした）、𝕂 ↦ 𝔠 は 𝕂 の関数の閉じた式で、それぞれ元のプログラムに代入して帰納法で確かめています。𝕂 ≡ の ⊨𝔠 はこの閉じた式を使います。

二つのプログラムを入れると、24 項まで実行して比べます。どちらも「c×ψ(n) + n の多項式」の一次の形なら、規則 ℓ から D 項一致すれば全部一致するという上限 D を計算し、D 項まで一致していれば ⊨ と判定します（二つの数列の差が次数 D の漸化式を満たすので、最初の D 項が 0 なら全部 0 になります）。一次の形でない式（ψ(n)×ψ(n) など）では上限が出せないので、一致していても ≟ に留めます。下の小さなボタンは ⊭ の帯の組で、D = 6 の組では 5 項一致して 6 項目で分かれる、つまり上限がちょうど効いていることが見られます。

事前登録した予測と実測です。計算を始める前に予測と 90% の区間を記録し、その後に実測しました（P は演算 3 回以下、Q は 4 回以下に広げたときの予測で、Q は P の結果を見たうえで立てています）。緑が区間内、橙が区間外です。いちばん大きく外したのは P1〜P3 で、1 万本以上ある式も展開すると 281 種類の多項式にまで潰れることを見込めていませんでした。P4 と Q6（証明できる割合）は 100% で、区間の上を超えました。最初に作った証明の方法（一次の形の成員から閉じた式を作る）では 2 つの類（1, 0, 0, … と 2, 0, 0, …）が残り、0ⁿ を基底に足して全部証明できました。その方法を足す前でも 90.5% と 95.5% で、どちらも区間外です。