「1つ前の項とは共通の素因子を持つが、2つ前の項とは互いに素」なルールで最小の整数を並べ続けると、素因数を2種類以上持つ正の整数はすべてこの数列に現れる

次のような数列を考えます。

$$ 1,2,6,15,35,14,12,33,55,10,\ldots $$

一見するとランダムです。

でも、各項の間には、次のようなルールがあります。

• 直前の項とは、1より大きい共通因子を持つ。
• 2つ前の項とは、互いに素である。
• まだ使っていない数のうち、条件を満たす最小のものを選ぶ。

たとえば$15\text{ と }35$は共通因子$5$を持ち、$35\text{ と }14$も共通因子$7$を持っています。

一方、$15\text{ と }14$は互いに素です。

この奇妙な数列は Enots Wolley sequence と呼ばれています。

2026年9月に Nathan Myles Nichols が公開したプレプリント Surjectivity of the Enots Wolley Sequence (Ni arXiv:2609.18054 )で、次の主張が証明されました。

素因数を2種類以上持つ正の整数は、すべてこの数列に現れる。

つまり、数列に出てこないのは基本的に「素数冪」の仲間だけです。

この記事では、この結果を単に紹介するだけでなく、「なぜそんな数列になるのか」から出発して、証明の核心にある

• 無限に続けられるための条件
• 「新しい素数」の出現
• 固定した素因子集合を追う方法
• covered episode という短いブロック
• prime exchange という交換法
• 最後の有限被覆の矛盾

を追ってみたいと思います。

Enots Wolley sequence のルール

正の整数の素因子全体を

$$ P(m)=\{p:p\text{ は素数で }p\mid m\} $$

と書きます。たとえば

$$ P(12)=\{2,3\}, $$

$$ P(35)=\{5,7\}. $$

また、異なる素因子の個数を

$$ \omega(m)=|P(m)| $$

と書きます。すると

$$ \omega(12)=2, \qquad \omega(60)=3 $$

です。

Enots Wolley sequence$a_1,a_2,a_3,\ldots$は

$$ a_1=1,\qquad a_2=2 $$

から始めて、$n\ge3$ では、

$$ \gcd(a_n,a_{n-1})>1 $$

かつ

$$ \gcd(a_n,a_{n-2})=1 $$

を満たす未使用の最小の整数を選ぶ、と考えることができます。

最初の部分は

$$ 1,2,6,15,35,14,12,33,55,10,18,21,77,22,20,\ldots $$

です。

序盤

まず $1,2$ の次を考えます。

なぜ $4$ ではない？

$4$ は $2$ と共通因子を持つので、一見すると良さそうです。

しかし、

$$ 1,\ 2,\ 4 $$

とすると、次の項は

• $4$ と共通因子を持つ
• $2$ とは互いに素

でなければなりません。

ところが、$4$ の素因子は $2$ しかありません。

したがって、次の項も $2$ を含まなければならず、同時に $2$ と互いに素でなければならないという矛盾が起こります。

だから $4$ では続きません。

では $6$ はどうでしょう。

$$ P(6)=\{2,3\}. $$

次の項は $2$ と共通因子を持たず、$6$ と共通因子を持つものを選べばよい。

たとえば $15$ なら

$$ P(15)=\{3,5\} $$

なので、

$$ P(15)\cap P(6)=\{3\}, $$

しかも

$$ P(15)\cap P(2)=\varnothing. $$

さらに $5$ という「新しい素数」も入っています。

したがって

$$ a_3=6,\qquad a_4=15 $$

となります。

同じように $35$ が続きます。

「共通因子がある」だけでは足りない

ここがこの数列の重要なポイントです。

直前の項と共通因子を持ち、2つ前の項とは互いに素でも、

$$ P(a_n)\subseteq P(a_{n-1}) $$

だったらダメです。

なぜなら次の項 $a_{n+1}$ は $a_n$ と共通因子を持つ必要があります。

ところが $a_n$ の素因子が全部 $a_{n-1}$ にも入っていると、

$$ \gcd(a_{n+1},a_n)>1 $$

から、その共通素因子は必ず $a_{n-1}$ にも入ってしまいます。

すると

$$ \gcd(a_{n+1},a_{n-1})>1 $$

となって、2つ前の項との互いに素条件に反します。

つまり、

次の項を作り続けるには、現在の項が「前の項にはない素因子」を持っていなければならない。

これがこの問題の最初の核心です。

補題：無限に続けられるための条件

論文では、この考えが次の補題として整理されています。

補題：Infinite continuation criterion

有限列

$$ a_1,\ldots,a_n $$

がここまでの条件を満たしているとします。

このとき $a_n$ から先を無限に続けられるための条件は、

$$ P(a_n)\setminus P(a_{n-1})\ne\varnothing $$

です。つまり、

現在の項には、直前の項にない素因子が少なくとも1つ必要

となります。

この補題の「逆」

必要条件だけなら、さきほどの説明で分かります。

でも面白いのは、

新しい素因子が1つあれば、本当に無限に続けられる

ということです。

$P(a_n)\setminus P(a_{n-1})$ から素数 $r$ を1つ取ります。

すると

$$ r\mid a_n, \qquad r\nmid a_{n-1}. $$

ここで、まだ一度も登場していない新しい素数

$$ Q_1,Q_2,Q_3,\ldots $$

を次々に用意します。

最初に

$$ rQ_1 $$

を置きます。

これは

• $a_n$ と $r$ を共有する
• $a_{n-1}$ とは互いに素
• 新しい素数 $Q_1$ を導入する

ので条件を満たします。

次には

$$ Q_1Q_2 $$

を置けばよい。

その次は

$$ Q_2Q_3, $$

さらに

$$ Q_3Q_4,\ldots $$

と続けられます。

したがって、

$$ a_n,\ rQ_1,\ Q_1Q_2,\ Q_2Q_3,\ Q_3Q_4,\ldots $$

と無限に続けられます。

この「新しい素因子」が、後の証明でもずっと重要な役割を果たします。

greedy rule のもう1つの重要な性質

この数列では、毎回

条件を満たす未使用の最小整数

を選びます。

この単純な greedy rule から、非常に強い事実が出てきます。

補題：Smaller admissible integers are historical

$a_n$ が選ばれたとき、$m< a_n$ がその時点で条件を満たしているなら、$m$ はすでに過去に登場しています。

これは当たり前に見えますが、証明では非常に重要です。

もし $m< a_n$ が未使用なのに条件を満たしていたら、$a_n$より小さい $m$ を選べたはずだからです。

さらに重要なのは、

一度「小さいのに未使用」という状態になった整数が、後から突然復活して選ばれることはない

ということです。

後でそれが admissible になったなら、その時点でもっと小さい未使用数なので、やはり先に選ばれていなければなりません。

この greedy 性質を使って、「ある整数が永遠に出てこない」という仮定を、後半の証明で扱えるようにします。

Pythonで実験してみよう

実際に最初の何項かを生成してみましょう。

      from sympy import factorint
def prime_support(n):
    return set(factorint(n).keys())
def enots_wolley(N):
    a = [1, 2]
    seen = {1, 2}
    yield 1
    if N == 1:
        return
    yield 2
    if N == 2:
        return
    for _ in range(3, N + 1):
        candidate = 1
        P1 = prime_support(a[-1])
        P2 = prime_support(a[-2])
        while True:
            if candidate not in seen:
                P = prime_support(candidate)
                overlap = len(P & P1) > 0
                lag_two = len(P & P2) == 0
                novelty = len(P - P1) > 0
                if overlap and lag_two and novelty:
                    a.append(candidate)
                    seen.add(candidate)
                    yield candidate
                    break
            candidate += 1
seq = list(enots_wolley(70))
print(seq)
    

実行すると、最初のほうは

      1, 2, 6, 15, 35, 14, 12, 33, 55, 10,
18, 21, 77, 22, 20, 45, 39, 26, 28, 63, ...
    

となります。

出てこない数は？

ここで、実験として

$$ 1,2,\ldots,N $$

の中で、まだ登場していない数を調べてみましょう。

      N = 2000
seq = list(enots_wolley(N))

seen = set(seq)

missing = [m for m in range(1, 500) if m not in seen]

print(missing)
    

初期の段階では、

$$ 4,5,7,8,9,11,13,\ldots $$

のような数が大量に見つかります。

これらを素因数分解すると、

$$ 4=2^2, $$

$$ 8=2^3, $$

$$ 9=3^2, $$

$$ 25=5^2 $$

のような 素数冪 が目立ちます。

一方、

$$ 6=2\cdot3, $$

$$ 10=2\cdot5, $$

$$ 12=2^2\cdot3, $$

$$ 15=3\cdot5, $$

$$ 35=5\cdot7 $$

などは登場しています。

そこで自然な予想が生まれます。

1, 2 と、異なる素因子を2つ以上持つ整数は、全部この数列に現れるのではないか？

これが Enots Wolley sequence の surjectivity conjecture です。

当論文Niはこの予想を肯定的に解決しました。

主定理

論文の主定理は、

異なる素因子を2つ以上持つすべての正整数は、Enots Wolley sequence に現れる

というものです。

言い換えると、

$$ \{a_n:n\ge1\} = \{1,2\} \cup \{m:\omega(m)\ge2\} $$

です。

したがって、

• $1,2$ は出てくる
• 素数は出てこない
• $4,8,9,16,25,\ldots$ のような素数冪も出てこない
• $6,10,12,15,18,21,35,\ldots$ は全部出てくる

ということになります。

「全部出てくる」をどう証明するのか

ここからが論文の肝の部分に少しずつ入っていきます。

任意の正整数$h$が$\omega(h)\ge2$を満たしているとします。

そして、

もし $h$ が数列に出てこなかったら？

と仮定して矛盾を作ります。

$h$ の素因子集合を

$$ T=P(h) $$

と置きます。

たとえば

$$ h=60=2^2\cdot3\cdot5 $$

なら、

$$ T=\{2,3,5\}. $$

この $T$ を固定して数列全体を見るのが、証明の大きなアイデアです。

exact support という考え方

$T$ を固定します。

「素因子集合がちょうど $T$」である整数を集めます。

たとえば

$$ T=\{2,3\} $$

なら、

$$ 6,12,18,24,36,48,\ldots $$

のように、素因子がちょうど $2,3$ だけの数です。

これを論文では exact-support queue として扱います。

重要なのは、

同じ support $T$ を持つ候補は、数値の小さい順に選ばれていく。

ということです。

なぜなら、ある support $T$ がその時点で admissible なら、同じ $T$ を持つ未使用の整数は、どれも同じ「素因子レベル」の条件を満たすからです。

したがって、greedy rule によって最小のものから順に処理されます。

saturation

そこで、

support $T$ の整数が全部出てくる

という性質を

$$ \operatorname{Sat}(T) $$

と書くことにします。

つまり、

$$ \operatorname{Sat}(T) $$

とは、

exact support が $T$ である整数を、すべて Enots Wolley sequence が選ぶ

という意味です。

先ほどの主定理は、

$\operatorname{Sat}(T)$がすべての有限$T,\ |T|\ge2$で成り立つ

と言い換えられます。

もし saturation が失敗したら？

$T$ が飽和していないと仮定します。

つまり、

$$ \operatorname{Sat}(T) $$

が偽だとします。

すると、先ほどの greedy 性質から、

あるところから先では、support $T$ が局所的に admissible になることがなくなる

ことが分かります。

その「それより後はもう $T$ を exact support に持つ項を選べない」という境目を、論文では Sat-cutoff と呼びます。

この一歩は非常に大きいです。

「ある整数が一個出てこなかった」

という問題を、

ある素因子集合$T$に関する現象が、ある時点以降ずっと続く

という無限時間の問題に変換できたからです。

$T$-free, $T$-proper, $T$-full

ここから、数を3種類に分けます。

固定した$T$に対して、

$T$-free

$$ P(m)\cap T=\varnothing $$

なら、$m$ は $T$-free と呼びます。

つまり、$T$ の素数を1つも含みません。

$T$-full

$$ T\subseteq P(m) $$

なら、$m$ は $T$-full と呼びます。

つまり、$T$ の素数を全部含みます。

$T$-proper

$$ P(m)\cap T\ne\varnothing $$

だが

$$ T\nsubseteq P(m) $$

なら、$T$-proper と呼びます。

つまり、

$T$ の素数を一部だけ含んでいる

数です。

たとえば

$$ T=\{2,3,5\} $$

なら、

$$ 70=2\cdot5\cdot7 $$

は $T$-proper です。

一方、

$$ 210=2\cdot3\cdot5\cdot7 $$

は $T$-full。

$$ 49=7^2 $$

は $T$-free です。

covered episode

$T$-proper と $T$-full をまとめて

$$ T\text{-covered} $$

と呼びます。

つまり、

$$ P(m)\cap T\ne\varnothing. $$

そして数列の中で、$T$-covered な項が連続して現れる最大のブロックを$T$-covered episodeと呼びます。

たとえば

$$ \cdots,\underbrace{35,14}_{T\text{-covered}},\underbrace{9}_{T\text{-free}},\cdots $$

のように、

$T$ に関係する項が連続している区間

を見るわけです。

ここから、局所的な divisibility rule が強烈に効いてきます。

キー補題：Full-return rule

Sat-cutoff より後を考えます。

もし

$$ B=a_n $$

が $T$-free で、その次の

$$ F=a_{n+1} $$

が $T$-covered だったとします。

このとき $F$ は、実は

$$ T\text{-full} $$

でなければなりません。

これが Full-return rule です。

Full-return rule の証明

$F$ が $T$-proper だったと仮定します。つまり、

$$ P(F)\cap T\ne\varnothing $$

なのに

$$ T\nsubseteq P(F). $$

したがって、

$$ T $$

の中に $F$ に入っていない素数 $r$ があります。

ところが $B$ は $T$-free なので、

$$ r\nmid B. $$

一方、

$$ r\mid a_{n+2} $$

となる候補を作ることを考えると、

• $F$ と共通の素因子を持たせる
• $B$ とは互いに素にする
• $F$ にない $T$ の素数を使って novelty を満たす

ことができます。

すると $T$ の support 自体が、Sat-cutoff より後で admissible になってしまいます。

これは

Sat-cutoff より後では $T$ は admissible ではない

ことに反します。

したがって $F$ は proper ではありません。

よって

$$ F\text{ は }T\text{-full} $$

です。

episode は長くは続かない

ここから次の系が出ます。

系：Post-Sat episode grammar

Sat-cutoff より後の $T$-covered episode は、

$$ \text{必ず full で始まり、長さは高々2} $$

です。

つまり形としては

$$ \text{free}\to\text{full}\to \begin{cases} \text{free}\\ \text{proper}\to\text{free} \end{cases} $$

のどちらかしか起こりません。

なぜ3項以上続けられないのでしょうか。

full starter を

$$ F=a_n $$

とすると、次の項 $a_{n+1}$ は $F$ と共通因子を持ちます。

すると $a_{n+2}$ は $F$ と互いに素でなければならないので、

$$ a_{n+2} $$

は $T$ の素数を1つも持てません。

したがって episode はそこで終了します。

この「長さ2」という制約は、後の数え上げで決定的に重要です。

ここまでの構造を図式化すると

Sat-cutoff より後では、

$$ \text{free} \longrightarrow \text{full} \longrightarrow \text{free} $$

または

$$ \text{free} \longrightarrow \text{full} \longrightarrow \text{proper} \longrightarrow \text{free} $$

のような形しかありません。

つまり、

proper が現れるたびに、その直前に full が必要になる。

この「proper と full のペアリング」が、証明の次の段階につながります。

prime debut

もう1つ重要なのが、

新しい素数が初めてどこで登場するか？

という問題です。

ある素数 $Q$ が初めて数列の項の素因子として現れたとします。

その項を$H=a_n$とします。

すると論文では、$n\ge3$ なら

$$ H=bQ $$

という非常に強い結論が得られます。

ここで $b$ は predecessor に現れる素数です。

つまり、

新しい素数が初登場するとき、その項は「古い素数 × 新しい素数」という非常に単純な形になります。

prime debut の証明のアイデア

$Q$ は初めて出てきた素数なので、

$$ Q\nmid a_1,\ldots,a_{n-1}. $$

一方、$H$ は predecessor

$$ a_{n-1} $$

と共通素因子を持つので、

$$ b\mid H $$

かつ

$$ b\mid a_{n-1} $$

となる素数 $b$ が存在します。

しかも lag-two condition により、

$$ b\nmid a_{n-2}. $$

したがって$bQ$は、

• $a_{n-1}$ と共通因子 $b$ を持つ
• $a_{n-2}$ と共通因子を持たない
• 新しい素数 $Q$ を導入する

という条件を満たします。

だから greedy rule により、

$$ H\le bQ. $$

一方、$b$ と $Q$ はともに $H$ の素因子なので、

$$ bQ\mid H $$

です。したがって

$$ bQ\le H. $$

両方合わせれば、

$$ H=bQ. $$

この議論から、

1回の選択で新しく登場する素数は高々1つ

という事実も分かります。

すべての素数は最終的に登場する

さらに、この prime debut の性質から、

すべての素数は、どこかの項を割る

ことが示せます。

これは後半の矛盾に不可欠です。

証明のアイデアは簡単で、$Q$ をその時点でまだ見えていない最小の素数とします。

すると各過去の項について、新しい $Q$ を使って$rQ$という admissible candidate を作れるので、

$$ a_n< Q^2 $$

のような上からの評価が得られます。

もし $Q$ がずっと現れなければ、無限個の異なる項が

$$ 1,2,\ldots,Q^2-1 $$

の範囲に閉じ込められてしまいますので、これは不可能です。

したがって、$Q$はいつか登場します。

最小の unseen prime がどんどん大きくなるので、

prime debut は無限に続き、すべての素数が現れる

ことになります。

ここで「個数を数える」発想へ

固定した$T$について、もし saturation が失敗したと仮定します。

すると Sat-cutoff より後では、$T$-covered episode は

$$ \text{full}\quad\text{または}\quad \text{full}\to\text{proper} $$

という短い形しかありません。

したがって、十分後ろだけを見れば、

proper の出現回数は full の出現回数を大きく上回れない。

より正確には、有限個の初期部分を無視すれば、

$$ \#(\text{proper}) \le \#(\text{full}) $$

という形の制約になります。

なぜなら、各 proper に、その直前の full を対応させられるからです。

ところが数論的には逆になる

ここが論文のアイデアです。

「そんなに full ばかり出てくることは、本当に可能なのか？」

と考えます。

$T$-full は

$$ T\subseteq P(m) $$

なので、$T$ のすべての素数を含まなければなりません。

一方 $T$-proper は、

$$ P(m)\cap T $$

が一部だけでよい。

普通に考えると、

proper のほうがずっと作りやすい

はずです。

これを「作りやすい」という感覚だけで済ませず、素数の個数を使って定量化するのが、論文の prime-exchange construction です。

prime exchange とは？

ある素因子を、別の素因子に交換する

という操作を考えます。

固定した $T$ に対して、full な数は $T$ の素数を全部持っています。

そこで、その中の1つを「T の外側の素数」と交換すると、proper な数を作れる可能性があります。

たとえば

$$ T=\{2,3,5\} $$

なら、

$$ 2\cdot3\cdot5\cdot q $$

のような full source から、どこか1つの $T$-prime を外して、

$$ 2\cdot3\cdot q, \qquad 2\cdot5\cdot q, \qquad 3\cdot5\cdot q $$

のような proper 候補を考える、という発想です。

もちろん、実際の証明では

• greedy rule
• 数値の大きさ
• 例外的な source
• 交換後の admissibility

まで全部確認する必要があります。

そこで論文では、例外集合を捨てても十分な数の交換が残ることを示し、重み付き二重カウントを行います。

なぜ「重み」が必要なのか？

単純に

$$ \#\{\text{proper}\} > \#\{\text{full}\} $$

と言えれば簡単です。

しかし prime exchange では、1つの full source から出てくる候補数や、1つの proper term に対応する source 数が完全には一様ではありません。

だから、「全部を1票ずつ数える」のではなく、「それぞれに重みを付けて数える」必要があります。

このとき、同じ対象を「出ていく側」と「入ってくる側」の2通りで数えることで、

$$ \text{proper 側の重み} > C\cdot \text{full 側の重み} $$

という固定された比率の差が作られます。

ここで $C>1$ は適切な定数です。

これは論文の §6~8 に対応する、証明の最も技術的な部分です。

素数定理と Mertens の公式

ここで突然、素数の分布が必要になります。

論文で使われる主要な解析的道具は、

$$ \pi(x)\sim\frac{x}{\log x} $$

という素数定理と、

$$ \sum_{p\le x}\frac1p = \log\log x+O(1) $$

という Mertens 型の評価です。

「交換できる素数がどれくらいあるか」を数えるために、素数が無限にあるというだけでは足りません。

十分たくさん存在することを、定量的に知る必要があります。

例外集合を捨てても大丈夫？

prime exchange では、すべての source がきれいに交換できるわけではありません。

たとえば、

• 数値が小さすぎる
• ある素数と共通因子を持ってしまう
• 交換後に別の条件に違反する

などの「悪い source」があります。

しかし論文では、これらの例外を集めても、十分大きな範囲では全体に比べて無視できる量になります。

そのため、

$$ \text{良い source} = \text{全 source} - \text{例外 source} $$

について、

$$ \text{良い source の割合} \to1 $$

という状況を作れます。

ここで素数定理や Mertens の評価が使われます。

episode の数え上げと prime exchange の衝突

ここまでをまとめます。

一方では episode の構造から、

$$ \text{proper の数} \le \text{full の数} + O(1) $$

のような制約が出ます。

これは 組合せ論的な上界 です。

一方、prime exchange からは、大きな範囲では

$$ \text{proper の重み} \ge (1+\delta) \text{full の重み} $$

のような 数論的な下界 が得られます。

ここで $\delta>0$ は固定値です。

つまり、

$$ \text{proper は、episode の構造からは少ないはず} $$

なのに、

$$ \text{prime exchange からは、proper のほうが十分多い} $$

という衝突が起きます。

これが矛盾です。

したがって、covered episode は無限には存在できない

以上から、

Sat-cutoff より後に $T$-covered episode が無限個ある

という仮定が不可能になります。

よって、

$$ T\text{-covered episode は有限個しかない} $$

という結論になります。

ここは証明の大きな転換点です。

「ある support が飽和していない」という仮定から、

$$ \text{無限に続く構造} $$

を作ろうとしたところ、

$$ \text{proper/full の個数比較} $$

によって潰れました。

最後に残る問題

ここまで来ると、

では、その後の項たちはどうなっているのか？

という問題が残ります。

論文では prime recurrence を使い、

固定した有限個の素数によって、十分後ろの項がすべて被覆されてしまう

という形の問題へ持っていきます。

これを eventual prime cover と呼びます。

有限個の素数の集合$S$があって、

$$ \exists N_S \quad \forall n\ge N_S,\quad P(a_n)\cap S\ne\varnothing $$

なら、$S$ を eventual prime cover と呼びます。

なぜ有限被覆がまずいのか？

直感的には、

そのうち全部の項が、有限個の素数のどれかで割り切れる

というのは、Enots Wolley の「新しい素数を導入し続ける」という greedy dynamics と相性が悪そうです。

実際、論文では最終段階で、

$$ S=\{p_1,\ldots,p_k\} $$

という有限集合で全ての十分大きな項を覆えると仮定し、各素数がどこで active になるかを調べています。

そして、異なる素数によって被覆される部分をうまく分離して考えると、

有限個の素数で永遠に全項を覆うことはできない

という disjoint-cover argument が得られます。

ここで prime recurrence と lag-two disjointness が効いてきます。

ここで最初の仮定に戻る

最初は、

$h$ が数列に出てこない

と仮定していました。

すると $T=P(h)$ が saturation していません。

そこから、

$$ \text{Sat-cutoff} $$

を作り、

$$ \text{episode は短い} $$

ことを示し、さらに

$$ \text{prime exchange} $$

によって、

$$ \text{episode は無限には続けられない} $$

としました。そして最後に、

$$ \text{有限 prime cover} $$

という状況へ追い込み、それ自体を disjoint-cover argument で否定します。したがって、

$$ \operatorname{Sat}(T) $$

は偽ではありません。つまり、

$$ \operatorname{Sat}(T) $$

が成り立ちます。

改めて主定理

$T$ は任意の$|T|\ge2$の素数集合でした。

したがって、どんな$m$についても

$$ \omega(m)\ge2 $$

なら、support

$$ T=P(m) $$

に対応する exact-support queue がすべて使い切られます。

つまり $m$ は必ず数列に現れます。

よって、

$$ \{a_n:n\ge1\} = \{1,2\} \cup \{m\ge1:\omega(m)\ge2\} $$

です。

2020年からの予想が、2026年に決着したことになります。

数列を眺めるだけでも、いろいろ見えてくる

ここまで証明を見たあとで、もう一度数列を眺めてみましょう。

$$ 1,2,6,15,35,14,12,33,55,10,18,21,77,\ldots $$

例えば

$$ 35=5\cdot7 $$

から

$$ 14=2\cdot7 $$

へ行くと、共通素因子は $7$。

次の

$$ 12=2^2\cdot3 $$

とは

$$ \gcd(12,14)=2 $$

ですが、

$$ \gcd(12,35)=1. $$

つまり、

$$ 35 \longrightarrow 14 \longrightarrow 12 $$

では、

$$ 7 \longrightarrow 2 $$

と「active な素数」が切り替わっているように見えます。

この active prime の動きが、Enots Wolley sequence のダイナミクスを理解する鍵になっています。

「新しい素数」が数列を前へ進める

たとえば

$$ 15=3\cdot5 $$

から

$$ 35=5\cdot7 $$

へ行くと、

$$ 5 $$

が共通因子として残り、

$$ 7 $$

が新しく登場します。

そして次の項では $7$ を使う。

このように、

$$ \text{現在の active prime} \rightarrow \text{新しい prime} $$

というリレーのような構造が生まれます。

最初に見た

$$ P(a_n)\setminus P(a_{n-1})\ne\varnothing $$

という条件は、単なる technical condition ではなく、

数列を無限に走らせるレールのようなもの

だったわけです。

もう1つ面白いところ：素数そのものは出ない

主定理では、

$$ \omega(m)\ge2 $$

の整数が全部出てくる一方で、

$$ \omega(m)=1 $$

の整数は出てきません。

つまり、

$$ 2,3,5,7,11,13,\ldots $$

のような素数も、

$$ 4,8,9,16,25,\ldots $$

のような素数冪も対象外です。

これは「たまたま実験で見つからない」のではなく、

無限 continuation のためには、2種類の素因子が必要

という局所ルールから必然的に出てきます。

自分で確かめる実験

改めて、少し研究っぽい実験をしてみましょう。

$1$ から $N$ までについて、

$$ \omega(m)\ge2 $$

なのにまだ数列に出ていない数の個数を調べます。

      from sympy import factorint


def omega(n):
    return len(factorint(n))


N = 5000
seq = list(enots_wolley(N))
seen = set(seq)

missing_eligible = [
    m for m in range(1, N + 1)
    if omega(m) >= 2 and m not in seen
]

print("missing eligible =", len(missing_eligible))
print(missing_eligible[:50])
    

定理によれば、「最終的には」この集合は空になります。

ただし、

最初の $N$ 項を見た

ことと、

$1$ から $N$ までの整数が全部出た

ことは別なので注意してください。

数列の項数と、調べたい整数の上限を混同しないことが大切です。

発展課題

この論文を読んでみると、次のような問いも自然に出てきます。

問題1

素数 $p$ が初めて登場するとき、$a_n=pq$ の $q$ はどんな順序で現れるでしょうか？

問題2

「新しい素数が初登場する項」は、どのくらいの頻度で現れるでしょうか？

問題3

固定した$T=\{2,3\}$に対して、$T$-full / $T$-proper / $T$-free のパターンを大量に生成してみましょう。

問題4

最初の100万項について$a_n-n$を調べると何が見えるでしょうか？

まとめ

今回の数列は、

$$ 1,2,6,15,35,14,12,\ldots $$

から始まる、一見するとランダムな数列でした。

ところがルールは単純です。

$$ \gcd(a_n,a_{n-1})>1, $$

$$ \gcd(a_n,a_{n-2})=1. $$

さらに、無限に続くためには

$$ P(a_n)\setminus P(a_{n-1})\ne\varnothing $$

という「新しい素因子」の条件が必要です。

そこから、

$$ \text{prime debut} $$

$$ \text{exact support} $$

$$ \text{Sat-cutoff} $$

$$ \text{covered episode} $$

という構造が現れます。

そして証明の核心では、

$$ \text{proper と full の個数比較} $$

を行います。

episode の構造からは proper が増えすぎることは許されない。

しかし、

$$ \text{prime exchange} $$

による weighted double count では、逆に proper 側に固定倍率の余剰が生まれます。

この2つが衝突することで、saturation の失敗を排除します。

最後に finite eventual prime cover も排除して、

$$ \text{異なる素因子を2つ以上持つ整数はすべて登場する} $$

という結論に到達します。

感想

個人的に、この論文で最も面白いと思うポイントは、

数列を作るルール

と

素数の分布

が、離れた場所からつながってくることです。

最初は最大公約数しか出てきません。

ところが最終的には、素数定理や

$$ \sum_{p\le x}\frac1p \sim\log\log x $$

まで登場します。

つまり、

「最小の整数を選ぶだけ」という greedy な数列の性質を調べるために、素数全体の分布を使う必要が出てくる。

ここが、この問題を単なる「面白い数列」から、本格的な数論の問題へ変えているところです。