Corollaryは必然に。

2021年9月23日に行われたロマンティック数学ナイト@オンライン #16 で
「オンライン整数列大辞典の未解決問題が解けた話」
というプレゼンをさせていただきました。今回の話はこのイベントで紹介した未解決問題の解説および証明になります（おせーよ）。

素数ものさしってご存知でしょうか？その名の通り、目盛りが素数しかないものさしで、現在でも京大生協でのみ販売されています*1。

なんとも不便なものさしですが、 $3-2=1$ なので「3歩進んで2歩下がる」を繰り返せば、一応すべての自然数を測ることは可能です。しかし、これでは芸がないですね。せっかくならたくさんの素数を使いこなしたいところ。

そこで、すべての自然数を、2から順番に目盛りを1回だけ使って測ってみるのはいかがでしょう？例えば3なら
\[
3 = 2 + 3 + 5 - 7
\]なので、「2歩進んで、3歩進んで、5歩進んで、7歩下がる」ことで3を測れます。素数に囚われた水前寺清子みたいで楽しい。

さて、この方法ですべての自然数を測ることはできるのでしょうか？

あ、素数は無限にあるので素数ものさしは無限に長いこととします。

問題設定と考察
主定理の紹介
3つの補題
主定理の証明
あとがき
演習問題（奇数バージョン）

問題設定と考察

本日は次の問題を考えます。

問題1

任意の自然数を2から連続する有限個の素数の足し引きで表すことができるか？

例えば $1$ から $20$ までを考えるとこんな感じになります。
\begin{alignat*}{2}
1 &= &- 2& + 3\\
2 &= &2&\\
3 &= &2& + 3 + 5 - 7\\
4 &= &2& - 3 + 5\\
5 &= &2& + 3\\
6 &= &- 2& + 3 + 5\\
7 &= &2& + 3 - 5 + 7\\
8 &= &2& - 3 + 5 - 7 + 11\\
9 &= &2& + 3 - 5 + 7 - 11 + 13\\
10 &= &2& + 3 + 5\\
11 &= &2& - 3 + 5 + 7\\
12 &= &2& - 3 - 5 + 7 + 11\\
13 &= &- 2& + 3 + 5 + 7\\
14 &= &2& + 3 + 5 - 7 + 11\\
15 &= &2& + 3 + 5 + 7 + 11 - 13\\
16 &= &2& - 3 + 5 - 7 - 11 + 13 + 17\\
17 &= &2& + 3 + 5 + 7\\
18 &= &2& + 3 - 5 + 7 + 11\\
19 &= &2& + 3 + 5 + 7 - 11 + 13\\
20 &= &2& - 3 - 5 + 7 - 11 + 13 + 17
\end{alignat*}ただし、\begin{alignat*}{2}
1 &= &- 2& + 3\\
&= &2& - 3 - 5 + 7,\\
7 &= &2& + 3 - 5 + 7\\
&= &-2& - 3 + 5 + 7
\end{alignat*}のように、表示は一通りであるとは限りません。また、2から連続する有限個の素数の足し引きで表せない自然数がある可能性があります。ですが、もし表せたとすると「最低限必要な素数の数」が求まります。ということで、次の問題を考えます。

問題2

$p_k$ は小さい方から数えて $k$ 番目の素数を表すことにする．自然数 $n$ に対して，2から連続する $k$ 個の素数に符号を与えて
\[
n=\pm2\pm3\pm5\cdots\pm p_k
\]と表せるような最小の $k$ を $a_n$ とおく（もし表せなければ $a_n=\infty$ とする）．このとき，数列 $(a_n)_n$ はどのように表せるか？

例として $n=20$ を考えましょう。先ほど $20 = 2 - 3 - 5 + 7 - 11 + 13 + 17$ と表せることを紹介しましたが、これだけでは $a_{20}=7$ とは言い切れません（ $a_{20}\le7$ ならOK）。というのも、
\[
20 > 17 \ge \pm 2 \pm 3 \pm 5 \pm 7
\]なので7よりも少なく表示できないことは分かりますが、 $20=\pm 2 \pm 3 \pm 5 \pm 7 \pm 11 \pm 13$ や， $20=\pm 2 \pm 3 \pm 5 \pm 7 \pm 11$ の形で表せる可能性があるからです。このくらいであれば総探索で求められますが、後で効率的な方法を紹介します。

なんやかんやで、 $n=80$ くらいまでの数列 $(a_n)_n$ をグラフにするとこのようになります：

んー。てけてけ動いてて、よく分からない。でもこの調子だと $a_n=\infty$ とはならなそう…ですかね？

ちなみに、この数列に関する記事はすでにオンライン整数列大辞典（OEIS）にありますが、2021年9月23日時点では $(a_n)_n$ を表す公式はありませんでした*2。
oeis.org

ちょっと大げさに言えば、（オンライン整数列大辞典上の）未解決問題ということになります。本日はこの問題を解決します！！

主定理の紹介

さっそくですが、主定理の紹介です。

定理1

自然数 $n$ に対して， $k$ を $n\le \sum\limits_{i=1}^k p_i$ をみたす最小の自然数とする（ $p_i$ は小さい方から数えて $i$ 番目の素数を表す）．このとき，以下が成り立つ：

$n=9, 16$ のとき， $a_n=k+3$ ．すなわち $a_9=6$ ， $a_{16}=7$ ．
$n\neq9, 16$ かつ $\sum\limits_{i=1}^k p_i - n$ が奇数のとき， $a_n=k+1$ ．
$\sum\limits_{i=1}^k p_i - n = 2, 8, 12$ のとき， $a_n=k+2$ ．
$\sum\limits_{i=1}^k p_i - n$ が $2$ ， $8$ ， $12$ 以外の偶数のとき， $a_n=k$ ．

我ながら、場合分け、えっぐ。いきなりこんなの見せられてもいまいちピンと来ないと思いますので、定理1の使用例をいくつか見てみましょう。

$n=4$ のとき、 $2 < 4 < 5 = 2+3$ なので $k = 2$ です。また、 $5-4=1$ （奇数）なので、定理1 (2)によると $a_4=k+1=3$ となります。つまり、 $4$ は $2$ ， $3$ ， $5$ の足し引きで表すことができ、これ以上素数の数は減らせないことが分かります。実際、 $4 = 2-3+5$ と表せます。

では、 $n=96$ のときはどうでしょうか。
\begin{alignat*}{2}
&2+3+5+7+11+13+17+19 &=& 77,\\
&2+3+5+7+11+13+17+19+23 &=& 100
\end{alignat*}なので $k = 9$ です。また、 $100-96=4$ （ $2$ , $8$ , $12$ 以外の偶数）なので、定理1 (4)によれば $a_{96}=k=9$ が分かります。実際、

\begin{equation*}
96 = -2+3+5+7+11+13+17+19+23
\end{equation*}

と表せます。

また、 $n=98$ のときは $k = 9$ かつ $100-98=2$ なので $a_{98}=k+2=11$ となります。調べてみると、

\begin{equation*}
98 = 2+3+5-7-11-13+17+19+23+29+31
\end{equation*}

と表すことができ、29以下の素数では表すことができません。

いかがでしょうか？手順としては、まず最初は $2+3+5+\cdots$ のように素数を足していき、初めて $n$ に到達するときの素数の個数 $k$ を見つけます。

次に、 $2+3+\cdots+p_k - n$ の偶奇を調べれば、（ $n=9, 16$ 以外の） $n$ は多くても $k+2$ 番目の素数までの足し引きで表せることが分かる、ということになります。まあまあ便利でしょ？

ただし、具体的にどこをマイナスにすればよいかまでは教えてくれないことに注意です。

それでは、証明に取り掛かりましょう。

3つの補題

主定理を証明する上で重要となる補題を3つ紹介します。最初の補題は $n=\pm2\pm3\pm\cdots\pm p_k$ の形で表せることの同値な言い換えについてです。

補題1

自然数 $n$ を $n=\sum\limits_{i=1}^{a} p_i - b$ （ $a, b$ は自然数）という形で表したとする．このとき， $n=\pm2\pm3\pm\cdots\pm p_{a}$ の形で表せることと，相異なる素数 $p_{a_1}, \ldots, p_{a_j}$ （ $1 \le a_1< a_2 < \cdots < a_j \le a$ ）を用いて $b=2(p_{a_1}+\cdots+p_{a_j})$ と表せることは同値．特に $b$ が奇数のときは $n=\pm2\pm3\pm\cdots\pm p_{a}$ の形で表せない．

証明
うまく符号を選んで $n=\pm2\pm3\pm\cdots\pm p_{a}$ の形で表せたとする．マイナスの符号をつけた素数を $p_{a_1}, \ldots, p_{a_j}$ （ $1 \le a_1< a_2 < \cdots < a_j \le a$ ）とすれば
\[
n=\sum_{i=1}^{a}p_i -2(p_{a_1}+\cdots+p_{a_j})
\]と表せる．逆に相異なる素数 $p_{a_1}, \ldots, p_{a_j}$ （ $1 \le a_1< a_2 < \cdots < a_j \le a$ ）を用いて $b=2(p_{a_1}+\cdots+p_{a_j})$ と表せたとすると
\begin{align*}
n&=\sum_{i=1}^{a}p_i -2(p_{a_1}+\cdots+p_{a_j})\\
&=p_1 + \cdots - p_{a_1} + \cdots - p_{a_j} + \cdots + p_a
\end{align*}となる．■

証明は大したことないですが、補題1によって今考えている問題は相異なる素数の和が本質的に絡んでいることが分かりました。

再び例として、 $n=20$ の場合を考えます。20は
\begin{align*}
20 &= 2 + 3 + 5 + 7 + 11 \color{red}{- 8}\\
&= 2 + 3 + 5 + 7 + 11 + 13 \color{red}{- 21}\\
&= 2 + 3 + 5 + 7 + 11 + 13 + 17 \color{red}{- 38}
\end{align*}と表せますが、 $8=2\times4$ であり、 $4$ は明らかに相異なる素数の和で表せません。また、 $21$ は奇数なので論外です（ $20$ と $\pm2\pm3\pm\cdots\pm13$ の偶奇が異なると考えてもOK）。そして $38=2\times19=2(3+5+11)$ なので
\[
20 = 2 \color{red}{-}3 \color{red}{-}5 + 7 \color{red}{-}11 + 13 + 17
\]という表示が得られます。なるほど、相異なる素数の組とマイナスをつける素数の組が対応しているわけですねー。

ところで、さらっと $19=3+5+11$ と分解しましたが、どんなに大きい自然数でも相異なる素数の和で表せるんでしょうか？そういえば、「4以上の偶数は2つの素数の和で表せる」というゴールドバッハ予想がありますが、これと同じノリで未解決問題だったりして…？

そんな不安を払拭してくれるのが次の補題です。

補題2

任意の整数 $k\ge5$ に対して，次をみたす自然数 $s_k$ が存在する：

区間 $[7,\, 6+s_k]$ に含まれる連続する $s_k$ 個の自然数はすべて $p_1, \ldots, p_k$ の相異なる素数の和で表せる．
$s_k\ge p_{k+1}.$

素数は無限に存在するので、補題2により7以上の自然数は相異なる素数の和で表せることが分かります（H. E. Richert, 1949）。Richert先生、Danke schön!

注意　素数自身は相異なる素数の和で表せると見なします。2つ以上の相異なる素数の和を考える場合、11が反例になります。

なお、1，4，6は相異なる素数の和で表せません。何となくですけど、それぞれ2倍すれば2，8，12になります。おやぁ？どこかで見たような気がしますねぇ…？

それはさておき、補題2は割と単純な（？）数学的帰納法で証明できます。詳細は以下の記事に任せることにします。
integers.hatenablog.com

ただし、補題2はとある定理を使って証明されております。

その定理とは…Bertrandの仮説です*3。

Bertrandの仮説

任意の自然数 $n$ に対して， $n \le p \le 2n$ を満たす素数 $p$ が存在する．

Bertrandの仮説から、
\[
p_{k+1}\le 2p_{k}\quad(k\ge 1)
\]が従います。この形で定理1の証明に利用しますので、お見逃しなく。

主定理の証明

それでは定理1の証明を行います。補題を適用させるために、小さい $n$ についてはしらみつぶしに証明することになりますが、それ以外は気持ちよく証明できたと思います。ぜひ、絶妙な不等式評価に注目してご覧ください。

定理1（再掲）

$n=9, 16$ のとき， $a_n=k+3$ ．すなわち $a_9=6$ ， $a_{16}=7$ ．
$n\neq9, 16$ かつ $\sum\limits_{i=1}^k p_i - n$ が奇数のとき， $a_n=k+1$ ．
$\sum\limits_{i=1}^k p_i - n = 2, 8, 12$ のとき， $a_n=k+2$ ．
$\sum\limits_{i=1}^k p_i - n$ が $2$ ， $8$ ， $12$ 以外の偶数のとき， $a_n=k$ ．

(1)の証明

$n=9$ のとき， $2+3 < 9 < 2+3+5$ なので $k=3$ であり，
\[
9 = 2 + 3 - 5 + 7 - 11 + 13
\]なので $a_9 \le 6$ ．また，
\begin{align*}
9 &= 2+3+5\color{red}{-1}\\
&= 2+3+5+7\color{red}{-8}\\
&= 2+3+5+7+11\color{red}{-19}
\end{align*}と表せるが，1，19は奇数なので補題1により $a_9\neq 3, 5$ ．また， $8=2\times4$ であるが4は相異なる素数の和で表せないので $a_9\neq 4$ ．したがって $a_9 = 6 = k+3$ ．

$n=16$ のときは $2+3+5 < 16 < 2+3+5+7$ なので $k=4$ である． $n=9$ のときと同様の議論をすることで $a_{16} = 7 = k+3$ が分かる．

(2)の証明

$n\neq9, 16$ ， $\sum\limits_{i=1}^k p_i - n = 2l-1$ とおく（ $1\le l < \frac{p_k + 1}{2}$ ）．このうち， $n\le 17=2+3+5+7$ をみたすのは $n=1, 4, 7, 12, 14$ である．このときそれぞれ $k=1, 2, 3, 4, 4$ であり，
\begin{alignat*}{2}
1 &= &- 2& + 3\\
4 &= &2& - 3 + 5\\
7 &= &2& + 3 - 5 + 7\\
12 &= &2& - 3 - 5 + 7 + 11\\
14 &= &2& + 3 + 5 - 7 + 11
\end{alignat*}と表せるが，確かに $a_n=k+1$ をみたしている（ $a_n < k+1$ とはならない証明は $n=9$ と同様の議論をすればよい）．

$n > 17$ のときは $k\ge5$ である． $2l-1$ は奇数であるから $n=\sum\limits_{i=1}^k p_i - (2l-1)$ は $\pm 2\pm 3\pm\cdots\pm p_{k}$ の形で表せない．また
\begin{equation}
n=\sum_{i=1}^{k+1} p_i - (2l+p_{k+1}-1) \tag{eq1}\label{eq1}
\end{equation}であるが， $2l+p_{k+1}-1$ は偶数であるから $m=l+\frac{1}{2}(p_{k+1}-1)$ とおくと
\[
m\ge 1+\frac{1}{2}(p_{6}-1)=7.
\]また，
\begin{align*}
m&< \frac{1}{2}(p_{k}+1)+\frac{1}{2}(p_{k+1}-1)\\
&\le p_{k+1}
\end{align*}であるから $7\le m \le p_{k+1}$ ．ここで補題2よりある自然数 $s_{k}$ が存在して， $s_{k}\ge p_{k+1}$ かつ区間 $[7, 6+s_{k}]$ 内の自然数は $p_1, \ldots, p_k$ の相異なる素数の和で表せる．したがって $m$ は $p_1, \ldots, p_k$ の相異なる素数の和で表せることができ，補題1と\eqref{eq1}により $n=\pm2\pm3\pm\cdots\pm p_{k+1}$ の形で表せる．よって $a_n = k+1$ ．

(3)の証明

$\sum\limits_{i=1}^k p_i - n = 2l$ とおく（ $l=1, 4, 6$ かつ $l < \frac{p_k}{2}$ ）．このうち， $n\le17$ をみたすのは $n=3, 8, 15$ である．このときそれぞれ $k=2, 3, 4$ であるが
\begin{alignat*}{2}
3 &= &2& + 3 + 5 - 7\\
8 &= &2& - 3 + 5 - 7 + 11\\
15 &= &2& + 3 + 5 + 7 + 11 - 13
\end{alignat*}と表せるので， $a_n=k+2$ が確認できる．以後 $n > 17$ （よって $k\ge5$ ）とする．

$l=1, 4, 6$ は相異なる素数の和で表せないので $a_n\neq k$ ．また，
\begin{align}
n &= \sum_{i=1}^{k+1} p_i - (2l+p_{k+1})\notag\\
&= \sum_{i=1}^{k+2} p_i - (2l+p_{k+1}+p_{k+2}) \tag{eq2}\label{eq2}
\end{align}という表示ができるが， $2l+p_{k+1}$ は奇数なので $a_n\neq k+1$ ．一方 $2l+p_{k+1}+p_{k+2}$ は偶数なので $m=l+\frac{1}{2}(p_{k+1}+p_{k+2})$ とおくとBertrandの仮説より
\begin{align*}
m - p_{k+1} &= l+\frac{1}{2}(p_{k+2} - p_{k+1})\\
& \le 6+\frac{1}{2}(2p_{k+1} - p_{k+1})\\
& = 6+\frac{p_{k+1}}{2}\\
& \le p_{k+1}.\\
\end{align*} $m - p_{k+1}\ge7$ のとき，補題2より $m - p_{k+1}$ は $p_1, \ldots, p_{k}$ の相異なる素数の和で表せる．よって $m$ は $p_1, \ldots, p_{k+1}$ の相異なる素数の和で表せるので\eqref{eq2}と合わせて $a_n=k+2$ が得られる．

$m - p_{k+1} < 7$ のとき，すなわち

\begin{align*}
(l, p_{k+2}-p_{k+1}) =& (1, 2),\,(1, 4),\,(1, 6),\,(1, 8),\,(1, 10),\\
&(4, 2),\,(4, 4)
\end{align*}

の場合を考える． $(l, p_{k+2}-p_{k+1}) = (1, 2t)$ （ $1\le t\le5$ ）のときは
\begin{align*}
m &= l+\frac{1}{2}(p_{k+1}+p_{k+2})\\
&= 1+\frac{1}{2}(p_{k+2}-2t+p_{k+2})\\
&= p_{k+2}-t+1\\
&\le p_{k+2}.
\end{align*}また， $m\ge 1+\frac{1}{2}(p_{6}+p_{7})=16 > 7$ なので，補題2より $m$ は $p_1, \ldots, p_{k+1}$ の相異なる素数の和で表せる．したがって\eqref{eq2}と合わせて $a_n=k+2$ ．

$(l, p_{k+2}-p_{k+1}) = (4, 2t)$ （ $1\le t\le 2$ ）のときは
\begin{align*}
m &= 4+\frac{1}{2}(p_{k+2}-2t+p_{k+2})\\
&= p_{k+2}-t+4.
\end{align*}よって $m= p_{k+2}+3$ または $m=p_{k+2}+2$ となるが，いずれも相異なる素数の和になっているので
\[
n = 2 - 3 + \cdots + p_{k+1} - p_{k+2}
\]または
\[
n = - 2 + 3 + \cdots + p_{k+1} - p_{k+2}
\]と表せる．ゆえに $a_n=k+2$ ．

(4)の証明

$\sum\limits_{i=1}^k p_i - n = 2l$ とおく（ $l\neq1, 4, 6$ かつ $l < \frac{p_k}{2}$ ）．

このうち， $n\le17$ をみたすのは $n=2, 5, 6, 10, 11, 13, 17$ である．このときそれぞれ $k=1, 2, 3, 3, 4, 4, 4$ であるが
\begin{alignat*}{2}
2 &= &2&\\
5 &= &2& + 3\\
6 &= &- 2& + 3 + 5\\
10 &= &2& + 3 + 5\\
11 &= &2& - 3 + 5 + 7\\
13 &= &- 2& + 3 + 5 + 7\\
17 &= &2& + 3 + 5 + 7
\end{alignat*}と表せるので， $a_n=k$ が確認できる．以後 $n > 17$ （よって $k\ge5$ ）とする．

$l=2$ のときは $n=-2+3+\cdots+ p_{k}$ と表せる（ $l=3, 5$ も同様）． $l\ge7$ のときは $7\le l < p_{k+1}$ であり，補題2より $l$ は $p_1, \ldots, p_{k}$ の相異なる素数の和で表せる．■

あとがき

これにてOEIS上の未解決問題は無事解決しました（万一証明に不備があればご連絡ください。質問でもOKです）。達成感がはんぱない。

証明に手こずったのは、やはり(3)ですね（ $\sum\limits_{i=1}^k p_i - n = 2, 8, 12$ のとき）。2021年9月23日の時点では完全に証明したつもりになっていましたが、ブログに公開するにあたって証明をもう一度読み直したら、不備がありました。添え字を見誤ったり、 $m - p_{k+1} < 7$ になる可能性を考えてなかったり…。(3)だけ色々ありました。

でも証明を頑張った分、以下のグラフの例外的にピョコっと出てくる3人組に共感できるようになりました（ $9, 16$ はガチの例外だから知らん）。

僕にはわかるよ。君たちが周りよりちょっと素数が必要なのは、 $1, 4, 6$ が相異なる素数の和で表せないからだもんね。いいこいいこ。今から素数ものさしで測ってあげるね～。

さて、今回の問題は、2020年5月末に「1から連続する有限個の自然数を足し引きして、すべての整数をつくることができるか？」という問題をTwitterで見かけたのが発端でした。この問題を深掘りして数学デーで議論していたところ、なんとオンライン整数列大辞典（OEIS）上の未解決問題に辿り着きました。

また、n=1~nまでを順に足したり引いたりしたとき、任意の整数を表せる数列bnの必要十分条件を探しました。ＯＥＩＳに関連する数列があり、どうやら三角数が関係しそうであることまではわかりました。未解決のopen questionが関わってくるようです。（キグロ）#数学デー #オンライン数学デー pic.twitter.com/VSdB3T81eU
— 「数学デー」公式 (@sugaku_day) 2020年5月29日

oeis.org

その後、独自に証明を考えてみたところ、証明ができてしまった、という経緯がありました。
corollary2525.hatenablog.com
一応、高校数学で分かるので、よろしければこちらもご覧ください。

身近な問題を深堀りして出くわした未解決問題のことを個人的に“野生の未解決問題”と呼んでいます。特にOEISは野生の未解決問題の宝庫なので、OEISを漁るのも面白いかもしれません。

演習問題（奇数バージョン）

最後に、OEIS上に類似の未解決問題があるので、演習問題として掲載したいと思います（暗黒微笑）。

問題3

自然数 $n$ に対して，1から連続する $k$ 個の奇数に符号を与えて
\[
n=\pm1\pm3\pm5\cdots\pm (2k-1)
\]と表せるような最小の $k$ を $a_n$ とおく（もし表せなければ $a_n=\infty$ とする）．このとき，数列 $(a_n)_n$ はどのように表せるか？

OEISのリンクはこちら（Conjecture（予想）も載っています）。
oeis.org

ヒントを書いておくと、奇数（なんなら任意の数列）の場合も全体の証明の流れは一緒です。

つまり、補題1および補題2の奇数バージョンに相当する命題を考えるのです。要するに

$n=\pm1\pm3\pm5\cdots\pm (2k-1)$ と表せることは、相異なる $2k-1$ 以下の奇数 $b_1,\ldots,b_j$ を使って $n=k^2 -2(b_1+\cdots+b_j)$ と表せることと同値（ただし $\sum\limits_{i=1}^{k}(2i-1)=k^2$ を用いた）
相異なる奇数の和で表せない例外的な自然数はあるか？