yura1685
3進法との関係
整数を小さい順に選んでいき、「選んだ整数の中に3項等差数列ができない」という条件を課してみます。
例えば最初に $0$ を選んだとします。次の $1$ は問題なく選べますが、$2$ を選ぶと $0,1,2$ が等差数列になってしまうため選べません。$3$ は選べ、$4$ も選べます。一方、$5$ は $1,3,5$ を作るため選べません。
この操作を続けると、\(S(0)=0,1,3,4,9,10,12,13,27,\ldots\) という数列が得られます。このように、最初に3項等差数列を含まない有限集合を決め、そこから現在の最大値より大きい整数のうち、条件を壊さない最小のものを順に加えて得られる数列を Stanley sequence と呼びます。
かなり唐突ですが、これを3進法で書き並べてみます。
| 10進法 | $0$ | $1$ | $3$ | $4$ | $9$ | $10$ | $12$ | $13$ | $27$ |
|---|---|---|---|---|---|---|---|---|---|
| 3進法 | $(0)_3$ | $(1)_3$ | $(10)_3$ | $(11)_3$ | $(100)_3$ | $(101)_3$ | $(110)_3$ | $(111)_3$ | $(1000)_3$ |
どの項にも $2$ が現れていません。実際、
$S(0)$ は、3進表示に $2$ が一度も現れない非負整数全体である。
が成り立ちます。
証明
3進表示が $0,1$ だけからなる $x<y<z$ が $x+z=2y$ を満たすと仮定し、それぞれの $3^i$ の位を $x_i,y_i,z_i\in{0,1}$ とします。$1$ の位では $x_0+z_0\equiv2y_0\pmod 3$ ですが、$x_0,y_0,z_0$ が $0,1$ のどちらかであることを考えると、これを満たすのは $x_0=y_0=z_0$ の場合しかありません。それぞれから共通の $1$ を引いて $3$ で割れば、次の桁でも同じことが言えます。結局すべての桁が一致し、$x=y=z$ となります。したがって、3進表示に $2$ を含まない相異なる3整数だけで3項等差数列ができることはありません。
3進表示に $2$ を含む数が選ばれないことは、$z$ に関する強い帰納法で示せます。$z$ 未満では「選ばれること」と「3進表示に $2$ が現れないこと」が同値であると仮定します。
$z$ に $2$ が現れない場合、帰納法の仮定より、それまでに選ばれている数もすべて $0,1$ だけで表されます。これらと $z$ から3項等差数列は作れないため、$z$ は選ばれます。
$z$ の3進表示に $2$ がある場合は、$z$ より小さい $x,y$ で $x+z=2y$ となるものを構成します。$z$ の $3^i$ の位を $z_i\in{0,1,2}$ とし、各桁について \(z_i=0\Rightarrow(x_i,y_i)=(0,0),\qquad z_i=1\Rightarrow(x_i,y_i)=(1,1),\qquad z_i=2\Rightarrow(x_i,y_i)=(0,1)\) と置きます。各桁で $x_i+z_i=2y_i$ なので繰り上がりはなく、そのまま $x+z=2y$ です。また、$x,y$ の3進表示には $0,1$ しか現れません。$z_i=2$ となる最上位の桁 $i$ を見ると、それより上では $x,y,z$ が一致し、第 $i$ 桁で $x_i=0<1=y_i<2=z_i$ なので $x<y<z$ です。帰納法の仮定から $x,y$ はすでに選ばれており、$z$ を加えると $x,y,z$ が3項等差数列になります。よって $z$ は選ばれません。
よって、\(S(0)=\{x\ge0\mid \text{$x$ の3進表示に $2$ が現れない}\}\) です。
この特徴付けから増加速度も決まります。$0$ 以上 $3^k$ 未満では3進表示の各桁を $0,1$ の2通りから選べるので、$S(0)$ の要素はちょうど $2^k$ 個あります。添字を $0$ から始めて $S(0)={a_n}{n\ge0}$ とすると、$a{2^k}=3^k=(2^k)^{\log_2 3}$ です。
$2^k\le n<2^{k+1}$ として単調性を使えば、\(a_n=\Theta\left(n^{\log_2 3}\right)\) となります。3進法の各桁で使える数字が2種類しかないことが、そのまま指数 $\log_2 3$ に現れています。
初期値を変える
初期集合を ${0,m}$ に変えて同じ貪欲法を行った数列を $S(0,m)$ とします。
$m=3$ では \(S(0,3)=0,3,4,7,9,12,13,16,27,30,31,34,\ldots\) ですが、$m=4$ にすると \(S(0,4)=0,4,5,7,11,12,16,23,26,31,33,37,\ldots\) となります。$S(0,3)$ には $S(0)$ に近い規則性がありますが、$S(0,4)$ はかなり様子が違います。
Odlyzko と Stanley は、Stanley sequence の増加には大きく2種類あるのではないかと予想しました。大まかには、Type 1 は $n^{\log_2 3}$、Type 2 は $n^2/\log n$ 程度で増加するというものです。ただし、この二分は一般には証明されておらず、Type 2 については具体例ですら事情がかなり複雑です。
$m=1,2,\ldots,10$ について最初の $1000$ 項を計算した結果は、明確に二群へ分かれます。
（分かりづらいですが）$m=1,2,3,6,9$ は下側に固まり、それ以外はかなり上に離れています。前者が Type 1 であることは知られていますが、後者まで Type 2 と分かっているわけではありません。
第1000項 $a_{999}$ だけ抜き出しても、この差はかなり大きいです。
| $m$ | $1$ | $2$ | $3$ | $4$ | $5$ | $6$ | $7$ | $8$ | $9$ | $10$ |
|---|---|---|---|---|---|---|---|---|---|---|
| $a_{999}$ | $29416$ | $29417$ | $29419$ | $64435$ | $75315$ | $29422$ | $61855$ | $66327$ | $29425$ | $69215$ |
下側の5つは $29416,29417,29419,29422,29425$ と、かなり近い値になっています。
$m$ の範囲を広げると、$m=1,2,3,6,9,18,27,54,\ldots$ でも同じような振る舞いが現れます。これらは、\(m=3^r\quad\text{または}\quad m=2\times3^r\) と書ける値です。
Odlyzko と Stanley は $S(0,3^r)$ と $S(0,2\times3^r)$ に3進表示を使った明示的な記述を与えており、これらは Type 1 になります。Rolnick はさらに、このような自己相似性を持つ Stanley sequence を independent Stanley sequence として定式化しました。
$3^r,\ 2\times3^r$ から始める場合
$S(0,3^r)$ や $S(0,2\times3^r)$ では、十分先まで進むと、それまでの並びをそのままコピーするような構造が現れます。
$S(A)={a_n}_{n\ge0}$ が independent であるとは、ある整数 $\lambda$ が存在し、十分大きな $k$ に対して \(a_{2^k+i}=a_{2^k}+a_i\quad(0\le i<2^k)\quad\text{および}\quad a_{2^k}=2a_{2^k-1}-\lambda+1\) が成り立つことをいいます。（$S(0,3^r)$ と $S(0,2\times3^r)$ が independent になることも証明できますが、少し長くなるのでここでは省略します。詳しくは参考文献 [2] にあります。）
前半の式は、$a_{2^k}$ から始まる次の $2^k$ 項が、最初の $2^k$ 項を $a_{2^k}$ だけ平行移動したものになっている、という意味です。基本的な $S(0)$ なら
\[0,1\mid3,4\mid9,10,12,13\mid27,28,30,31,36,37,39,40\mid\cdots\]となり、ブロックがそのまま次へコピーされています。
この自己相似性から $a_{2^{k+1}-1}=a_{2^k}+a_{2^k-1}$ なので、
\[\begin{aligned} a_{2^{k+1}} &=2a_{2^{k+1}-1}-\lambda+1\\ &=2(a_{2^k}+a_{2^k-1})-\lambda+1\\ &=2a_{2^k}+(2a_{2^k-1}-\lambda+1)\\ &=3a_{2^k} \end{aligned}\]です。十分大きな $k$ では、ある定数 $C>0$ を使って $a_{2^k}=C3^k$ と書けます。
$3^k=(2^k)^{\log_2 3}$ なので $a_{2^k}=C(2^k)^{\log_2 3}$ です。$2^k\le n<2^{k+1}$ と取れば、単調性から $a_{2^k}\le a_n<a_{2^{k+1}}$ となり、\(a_n=\Theta\left(n^{\log_2 3}\right)\) を得ます。
$m$ が $3^r$ または $2\times3^r$ でない場合に、必ず Type 2 になるかどうかは未解決です。$S(0,4)$ は長い間 Type 2 の代表的な候補として研究されていますが、$a_n=\Theta(n^2/\log n)$ であることは証明されていません。2025年には、この $n^2/\log n$ という予想自体に疑問を投げかける数値実験も報告されています。
最初の1000項では、グラフはきれいに二群へ分かれています。一方で、その上側にある $S(0,4)$ の増加速度すらまだ決着していません。初期値が $3$ か $4$ かというわずかな違いで、明示的な自己相似構造を持つ場合から、増加速度さえ未解明な場合へ移ることになります。
参考文献
- A. M. Odlyzko, R. P. Stanley, Some curious sequences constructed with the greedy algorithm, 1978.
- David Rolnick, On the classification of Stanley sequences, arXiv:1408.1940, 2014.
- David Rolnick, Praveen S. Venkataramana, On the growth of Stanley sequences, arXiv:1408.4710, 2014.
- Nat Sothanaphan, Irregular Stanley sequences plausibly do not have growth $\Theta(n^2/\log n)$, arXiv:2512.11983, preprint, 2025.