EMIRP EXPLORER — base-5 reversal database

どうやって 10⁵⁰ まで探したのか

1〜10⁵⁰ には10進で51桁分、約10⁵⁰個の数があります。1秒に1兆個調べられる計算機でも 全部見るには宇宙の年齢の10²⁰倍かかります。このデータベースの563解は、アルゴリズムを4世代 改良して手に入れたものです。

世代0: 全数探索

すべての m について rev10(m) と T(m) を計算して比べる、いちばん素直な方法。 GPUで毎秒1.4×10¹¹個まで高速化しましたが、それでも15桁(10¹⁵個)で約2時間。 1桁増えるごとに10倍かかるので、50桁は絶望的です。

世代1: Meet-in-the-middle(半分全列挙)

鍵は 10 = 2×5 という関係です。ここから 10^s ≡ 0 (mod 5^s)、つまり 「mの10進下位s桁だけで、mの5進下位s桁が完全に決まる」ことが従います。 m = A×10^s + B と上下に分けると、条件 rev10(m) = T(m) は

V(B) = W(A, c) (左辺は下位桁Bだけ、右辺は上位桁Aだけの関数)

という形に分離できます。そこで「全Bについて V を表にしておき、各Aについて一致するBを検索」すれば、 調べる回数は 10^d から 10^d/2 程度に落ちます。15桁が2時間→2分になりました。

世代2: 片側リフティング(1桁ずつ育てて枝刈り)

mの下位j桁を決めると、(1) rev10(m) の上位j桁と、(2) 5進下位j桁 = rev5(m)の上位j桁、が同時に確定します。 つまり答えの「両頭」が先に見えてしまう。rev10(m) と T(m) それぞれの存在範囲(区間)を比べ、 交わらない下位桁の組は、その先を見ずに捨てられます(枝刈り)。

生き残る接頭辞は実測でちょうど1桁あたり2倍(新しい5進桁が許容帯に入る確率1/5 × 10分岐)しか 増えません。全数探索の10倍/桁に比べ、2^d ≈ 10^0.3d まで削減。15桁は5秒になりました。

世代3: 両端リフティング(現行) — 下と上から挟み撃ち

同じ構造が上位桁側にもあります: mの上位t桁は rev10(m) の下位t桁を厳密に決め、 T(m) の下位5進桁も区間レベルで決めます。そこで

• 下位側から生存接頭辞の集合 L を育てる(〜2^d/4個)
• 上位側から生存接尾辞の集合 H を育てる(〜2^d/4個)
• 中央で合同式 rev(B)·10ᵗ ≡ rev5(q) − rev(U) (mod 5ʷ) をキーに突き合わせる

計算量は 2^d/2 ≈ 10^0.15d。50桁の完全探索が約5分で終わります (世代1なら26年、世代0なら10³³年)。

正しさの保証

• 相互検証 — 原理の違う4実装(全数・MITM・片側・両端)が同じ解集合を出すことを、桁ごとに突き合わせ
• 形式証明 — 枝刈りが解を取りこぼさない根拠となる10個の補題 (反転の分割公式、mod 5^j の決定性、区間の単調性など)を、定理証明支援系 Lean 4 + Mathlib で 機械的に証明(証明の穴 = sorry ゼロ)
• 素数判定 — 数式処理ライブラリ(sympy)で確定判定し、データに焼き込み済み

計算量の年表

• 世代0(全数・GPU): 10^d — d=50換算 約10³³年
• 世代1(MITM): 10^d/2 — 約26年
• 世代2(片側リフティング): 2^d — 数十年
• 世代3(両端リフティング): 2^d/2 — 約5分

5進数とは

ふだん使う数は「10進数」= 0〜9 の10種類の数字で、桁が1つ上がるごとに値が10倍になります。 5進数は 0〜4 の5種類だけで数を書く方法で、桁が上がるごとに5倍になります。 例: 10進の 13 は、13 = 2×5 + 3 なので5進では 23。 10進の 100 は、100 = 4×25 + 0×5 + 0 なので 400 です。 同じ数でも「書き方」が変わるだけで、値そのものは変わりません。

m とは

このデータベースで調べている対象の自然数のことを、数式の慣習で m と呼んでいます。 表の「m」列がその数本体です。

rev10(m) — 10進の反転

rev は reverse(反転)の略。rev10(m) は「m を10進で書いて左右をひっくり返した数」です。 例: rev10(123) = 321、rev10(13282303) = 30328231。 末尾が0の数は反転すると先頭の0が消えるので桁が減ります(rev10(120) = 21)。

T(m) — 5進で反転して読み直した値

この研究の主役の操作です。3ステップで計算します:

• ① m を5進数で書く — 例: 13282303 → 11400013203
• ② その並びを左右反転 — 30231000411
• ③ それを5進数として読み直す — 3×5¹⁰+0×5⁹+… = 30328231

この最終結果が T(m) です。ワークベンチに数を入れると①〜③が全部表示されます。

「解」とは

rev10(m) = T(m)、つまり「10進でひっくり返した数」と「5進でひっくり返した数」が 偶然一致する m のことです。ほとんどの数では一致しません。1〜10⁵⁰ を全部調べて、 一致したのはわずか563個でした。このデータベースはその563個のカタログです。

エマープとは

英語の emirp は prime(素数)の逆綴りです。一般には「素数で、桁を反転した数も別の素数」 (例: 13 と 31)を指します。この研究では解のうち m も rev10(m) も素数で、m ≠ rev10(m) のものを 「5進数変換エマープ」と呼びます。563解のうち、エマープは 13282303 ↔ 30328231 のたった1組しか存在しません(10⁵⁰まで確認済み)。

分類(回文 / 合成数 / 素数)

• 回文 — m = rev10(m)(ひっくり返しても同じ。例: 1221)。素数条件の「m ≠ rev10(m)」を満たせないのでエマープにはなれません
• 合成数 — 素数でない数(2つ以上の素数の積)
• 素数(反転は合成数) — m は素数だが rev10(m) が合成数で、エマープに一歩届かなかったもの(563個中13個)

構造型(回文 / 反転対 / 末尾0型)

• 反転対 — m が解のとき rev10(m) も必ず解になる(条件式が反転に対して対称なため)。そのペアのこと
• 末尾0型 — m = c×10^z(末尾に0がz個)の形の解。10^z = 2^z×5^z なので 10進でも5進でも末尾に0がz個並び、反転で両方同時に消える特別な族です

家族(ファミリー)と ID の読み方

解は1個ずつバラバラに存在するのではなく、「数の最初と最後のパターンが同じで、真ん中だけ違う」兄弟が まとまって見つかります。これを家族と呼び、d22-F01 のようなIDを付けています (= 22桁の1番目の家族)。563解は225家族にまとまり、最大の家族は22桁の47兄弟です。 ヒートマップ表示で家族を絞り込むと、固定部と可変部が色の模様として見えます。

d と 空白帯・豊作帯

d は m の10進での桁数です。面白いことに、d が 7 の倍数(7, 14, 21, 28, 35, 42, 49)の付近では解が1つもなく、 d を 7 で割って 1 余る桁(8, 15, 22, …, 50)に解が集中します。これは 10⁷ ≈ 5¹⁰ という 「2つの基数の偶然の近さ」が7桁ごとに繰り返すためで、グラフの薄い縦帯がその空白帯です。

0連続・末尾0(z)

「0連続」は数の中で0が連続して並ぶ最大の長さ(10進と5進で別々に数えます)。 「末尾0」= z は末尾に並ぶ0の個数で、末尾0型の説明にある通り特別な意味を持ちます。

通し番号

全563解を「桁数の小さい順、同じ桁数なら数の小さい順」に並べたときの番号(1〜563)。 検索条件を変えても変わらない、その解の固有の背番号です。

このアプリについて

条件 rev10(m) = T(m)(10進の位反転 = 5進表記を位反転して5進として読んだ値)を満たす自然数の、 1〜10⁵⁰ の完全探索で見つかった全563解を探索するデータベースです。 うち素数ペア(エマープ)は 13282303 ↔ 30328231 の1組だけです。

タブ

上部の「+ 新しいタブ」で検索条件セットを増やせます。各タブはフィルタ・表示列・列幅・収納状態を別々に記憶し、 ブラウザに保存されます(次回開いたとき復元)。×でタブを閉じます。

• 名前の変更 — タブ名をダブルクリック、または ⋮ メニューの「✎ 名前を変更」
• ⋮ メニュー — 複製 / グループ色(6色の丸でタブ上部に色帯。関連タブを色でまとめられる) / 書き出し(JSON) / 削除
• 並べ替え — タブをドラッグ&ドロップ
• 書き出し/読み込み — ⋮→「📤 書き出し」でタブの検索条件をJSONとしてコピーでき、「📥 読み込み」に貼ると復元。友達と検索条件を共有するのに使えます

フィルタ(左パネル)

• 桁数 d の範囲 — n〜k桁だけに絞る
• 分類 — 回文 / 合成数 / 素数 / エマープ(複数選択可)
• 構造型 — 回文 / 反転対(m と rev10(m) が両方解)/ 末尾0型(m = c×10^z)
• 0の連続 ≥ t — 10進・5進それぞれで、0が t 個以上連続する解だけに
• 末尾0(z) — 末尾に並ぶ0の個数。m=c×10^z の形の解は10進でも5進でも末尾0がz個になり、「2^zねじれ小問題」に還元される特別な族(表の「末尾0」列)
• 数字列検索 — 「2303」のような部分列を、m / 5進表記 / rev10(m) のどれで探すか選べる
• 家族 — 同じ「両端パターン」を共有する解のグループ。表の家族IDクリックでも絞れる

すべての条件は AND で重なります。「条件クリア」でそのタブだけ初期化。

数式クエリ — ゼロからの使い方

左パネルいちばん下の入力欄に「条件の式」を打ち込むと、その条件に合う解だけが表に残ります。 プログラミング経験がなくても大丈夫。しくみは3つだけです。

① 変数 = その行の値が入る「箱」。 表の1行1行について、m という文字はその行の数そのもの、d は桁数、というように 値が自動で入ります。つまり式は「各行に対する質問」です。

② 式 = 質問文。 m % 7 = 0 は日本語にすると「m を 7 で割った余りは 0 ですか?」。 % は「割った余り」の記号です(÷の答えではなく余りに注目するのがポイント。 余りが0 = 割り切れる = 7の倍数)。答えが「はい」になった行だけが表に残ります。

③ 関数 = 道具。 startswith(m, "13") は「m は 13 で始まりますか?」。 関数名(材料1, 材料2) の形で書き、文字の並びは "13" のように ダブルクォーテーションで囲みます。

まずはこの3ステップで試してください:

• 手順1: 入力欄に d = 8 と打つ → 8桁の解だけになる(「桁数は8ですか?」)
• 手順2: d = 8 && mp に書き足す → さらに「mが素数」の行だけに (&& は「かつ」。mp は はい/いいえ が入っている箱なのでそのまま条件になる)
• 手順3: 間違った式を打ってみる(例: m %% 2)→ 欄の下に ⚠ と理由が出るだけで壊れないので、 気軽に試して大丈夫

Example usage(やりたいこと → 式)

• 7の倍数だけ見たい → m % 7 = 0
• 偶数だけ / 奇数だけ → m % 2 = 0 / m % 2 = 1
• 13 で始まる数 → startswith(m, "13")(終わりなら endswith)
• どこかに 2303 を含む → contains(m, "2303")
• 素数の解だけ → mp(反転も素数なら mp && rp)
• 20桁以上かつ11の倍数 → d >= 20 && m % 11 = 0(「または」は ||)
• 〜ではない → 頭に ! か not: not startswith(m, "1")
• 桁をぜんぶ足すと9の倍数 → sum10(m) % 9 = 0
• 5進表記が回文 → ispal(b5)
• 5解以上の大家族だけ → famsize >= 5
• 1桁目と2桁目が同じ数字 → digit(m, 1) = digit(m, 2)

ありがちなつまずき: 文字は "..." で囲む(startswith(m, 13) でも数値として動きますが、桁の並びの話は文字列が安全)/ 「等しい」は = 1つでOK/ 「かつ」「または」を日本語で書かない(&& || か and or)。

記号は全角でも大丈夫。「以上」は >= と書きますが、 ≧ ≥ や全角の ＞＝、全角数字(ｄ ≧ ２０)、 × ÷、全角カンマなども自動で読み替えます。日本語入力のまま打ってもほぼ通ります。

リファレンス(一覧)

さらに踏み込んだ例:

• m % 7 = 0 — 7の倍数だけ
• startswith(m, "13") — 13 で始まる数(endswith, contains もあります)
• contains(b5, "00000") — 5進表記に0が5連続
• d >= 20 && m % 11 = 0 — 20桁以上かつ11の倍数(and or not も可)
• sum10(m) % 9 = 0 — 10進の桁和が9の倍数(= 9の倍数)
• gcd(m, rev) > 1 — m と反転が共通因数を持つ
• len(b5) - d = 10 — 5進桁数が10進より10桁長い
• mp — m が素数の解だけ(事前計算済みで高速。rp は rev10(m) が素数)。mp && !rp で「素数だが反転は合成数」
• isprime(m + 2) — 任意の式の素数判定(その場で計算。25桁超は確率的判定)
• ispal(b5) — 5進表記が回文の解
• count(m, "0") >= 5 — 0を5個以上含む / maxrun(b5, "0") >= 4 — 5進で0が4連続以上
• first(m, 2) = "13" / last(m, 3) = "303" — 先頭・末尾の桁の文字列
• digit(m, 1) = digit(m, 2) — 1桁目と2桁目が同じ数字
• famsize >= 5 — 5解以上の大家族に属する解だけ(famsize = 1 で一匹狼)
• T(m) = rev — T変換そのもの(解の定義なので全行で真。T(m + 10) のように任意の式に使えます)
• contains(to5(m * 2), "444") — to5(x) は x の5進表記(文字列)を返します

変数: m(本体)・rev(rev10(m))・d(桁数)・z(末尾0)・ run10/run5(0連続)・gidx(通し番号)・ b5(5進表記の文字列)・r5(それを反転した文字列)・fam/cls/type(文字列)・ mp/rp(m / rev10(m) が素数か。真偽値)・famsize(所属家族の解の数)。
演算: + - * /(整数除算)%(余り)、比較 = != < <= > >=、論理 && || !、括弧。
関数: startswith endswith contains len rev abs sum10 sum5 gcd isprime ispal count maxrun first last digit T to5。 数値は何桁でも正確に計算されます(多倍長)。文字列は "…" で囲みます。 式に誤りがあると入力欄の下に ⚠ で理由が出ます。

表示列

• チップ(10進 / 5進 / 反転…)を複数選ぶと、列が横に並びます。選んだ順=並び順
• 列見出しをドラッグ&ドロップ、または ◀▶ で並べ替え
• 見出しの ▾/▸ で列を細い帯に収納/展開
• 列幅スライダーで折り返し幅を調整
• ヒートマップチップをONにすると、数字が桁ごとの色タイルになり、家族内の「固定部/可変部」が一目でわかります

行の操作

• 行クリックで詳細(rev10・5進・0連続・家族)を展開
• 先頭の ☆ で比較トレイにピン留め。トレイはタブや検索をまたいで画面下部に残るので、離れた解を並べて比較できます
• 「#検索内 / 通し」は、いまの検索での順位と、全563解の通し番号(d昇順・m昇順)

グラフ

検索条件に該当する解の桁数分布。薄い縦帯は空白帯(dが7の倍数 — 10⁷≈5¹⁰ の共鳴で解が出ない桁)。

変換ワークベンチ

任意の自然数(60桁まで)を入力すると、5進表記・反転・T(m)・解の判定・素数判定(mとrev10の両方)を即計算。 「反転値を入力にセット」「T(m)を入力にセット」で変換を連鎖できます。25桁超の素数判定は確率的(強擬素数テスト)です。

CSV出力

「CSVで保存」はいまの検索結果だけを書き出します。ファイル名とファイル冒頭に検索条件と出力時刻が記録されるので、 後から「何の検索か」を再現できます。保存ダイアログが使えない環境では、コピー用のテキストが表示されます。

データの出典

両端リフティング法(C実装)による完全探索。結果は独立した4実装(全数探索・MITM・片側/両端リフティング)の 相互一致で検証済み。枝刈りの数学的正当性は Lean 4 + Mathlib で機械証明されています。