シルベスター数列

こんにちは｜こんばんは。カエルのアイコンで活動しております @kyamaz です。

はじめに

シルベスターシーケンスという数列をご存知でしょうか。シルベスタースタローンでもシルバニアファミリーでもジルベスターコンサートでもありません（寒ッ）。Wikipediaにも日本語の頁¹がありますので、名前のついた数列としてはそこまでマイナーな数列ではないようです。
本稿では、このシルベスター数列について紹介します。

シルベスター数列（Sylvester's sequence）

Wikipedia¹によると、その名称は1880年にこの数列を最初に調査したジェームス・ジョセフ・シルベスターに由来しています。各項が、その前項までの項の総積に1を足した数である数列で、数式で書くと次のようになります。

$$\begin{flalign}
s_n &= 1 + \prod _{i=0} ^{n-1} s_i \qquad (s_0 = 2) & \tag{A}
\end{flalign}$$

$0$個の項の積 (空積) は $1$ であるため、初項である$s_0 = 2$ でとなります。また、この定義から容易に次の漸化式が導けます。

$$\begin{flalign}
s_n &= s_{n-1} (s_{n-1} - 1) + 1 \qquad (s_0 = 2) & \tag{B}
\end{flalign}$$

漸化式（B）からiterateを使うとHaskellでは簡単に処理がかけます。

シルベスター数列

sylv = iterate (\x -> x*(x-1)+1) 2

そしてこの計算式で最初の10個を計算で求めて出力してみましょう。
数列の最初のリストは、オンライン整数列大辞典の数列 A000058 を参照して、出力と比較してみてください。

ghci> take 10 sylv
[2,3,7,43,1807,3263443,10650056950807,
113423713055421844361000443,
12864938683278671740537145998360961546653259485195807,
165506647324519964198468195444439180017513152706377497841851388766535868639572406808911988131737645185443]

この数列は急激に大きな桁数の数になっていきます。漸化式から想定されるように、桁数がおおよそ倍々に増えていきます。$s_{30}$ では次に示すとおり、2.1億桁の数になります。（その数を表示するのは、時間とメモリを浪費しますので避けておきましょう）

ghci> length . show $ sylv !! 30
218562698

エジプト分数（Egyptian fraction）

分数をいくつかの異なる単位分数（分子が $1$ の分数）の和で表す方式を『エジプト分数』（エジプト式分数、とも呼ぶ）²といいます。
シルベスター数列にまつわる話題として、エジプト分数に関わる性質があり、WikiPedia¹と以下のサイトで紹介されています。

シルベスター数列の逆数和による無限級数 $\displaystyle \sum _{n=0} ^{\infty} \frac{1}{s_n} $を考えると、この級数全体が $1$ に収束します。
つまり、この無限級数は $1$ を無限長で表したエジプト分数表示と考えられます。すなわち、
$$\begin{flalign}
\sum _{n=0} ^{\infty} \frac{1}{s_n} &= \frac{1}{2} + \frac{1}{3} + \frac{1}{7} + \frac{1}{43} + \frac{1}{1807} + \cdots = 1&
\end{flalign}$$となります。

エルデシュ・シュトラウス予想

また、余談としてシルベスター数列とは関係がありませんが、エジプト分数に関連して次のような予想が知られています。³

エルデシュ・シュトラウス予想

$2$ 以上の全ての整数 n に対し， $$\begin{flalign} \frac{4}{n} &= \frac{1}{x} + \frac{1}{y} + \frac{1}{z} & \end{flalign}$$を満たす正の整数 $x, y, z$ が必ず存在する．という予想

計算機を用いた探索により、少なくとも $n \le 10^{17}$ までは予想が成り立つことが知られているそうですが、厳密な証明は与えられておらず、未解決問題の１つです。

おわりに

ご一読いただきまして有り難うございます。

最後に、本稿を記載するために検証したHaskell環境を記しておきます。お手元の環境で検証する際に、動作が異なるときには参考になるかもしれません。

本稿の環境

本稿のために使用した環境は以下となります。

• macOS: Sonoma 14.6.1 (chip: Apple M1)
• GHCup: 0.1.30.0
• GHC: 9.6.6

（●）（●） Happy Hacking!
/""　＿＿""＼

1. Wikipedia: シルベスター数列 ↩ ↩² ↩³

2. Wikipedia: エジプト式分数 ↩

3. Wikipedia: エルデシュ・シュトラウス予想 ↩