自然数の複雑度

自然数 $n$ の複雑度とは、足し算と掛け算と括弧の使用のみを許して $n$ を $1$ だけで表示するのに必要な $1$ の個数の最小値のことを言います。

例えば、 $7$ と $9$ の複雑度は $6$ です。

$7=(1+1)\times (1+1+1)+1,\quad 9=(1+1+1)\times (1+1+1)$

$n$ の複雑度を $c(n)$ と表すことにしましょう。

$\begin{align}&c(1)=1, c(2)=2, c(3)=3, c(4)=4, c(5)=5, c(6)=5, c(7)=6, c(8)=6, c(9)=6, \\ &c(10)=7, c(11)=8, c(12)=7, c(13)=8, c(14)=8, c(15)=8, c(16)=8, c(17)=9, \\ &c(18)=8, c(19)=9, c(20)=9, c(21)=9, c(22)=10, c(23)=11, c(24)=9, c(25)=10, \\ &c(26)=10, c(27)=9, c(28)=10, c(29)=11, c(30)=10, c(31)=11, c(32)=10\end{align}$

Question１ $2^n=\prod_{i=1}^n(1+1)$ という表示があるが、 $c(2^n)=2n$ は一般に成り立つだろうか？

複雑度が $n\geq 1$ となるような最小の自然数を $e_n$ とすると、 $e_1$ から $e_{89}$ は次のようになることが知られています*1：

$\begin{align}e_{1}&=1\\ e_{2}&=2\\ e_{3}&=3\\ e_{4}&=4\\ e_{5}&=5\\ e_{6}&=7\\ e_{7}&=10\\ e_{8}&=11\\ e_{9}&=17\\ e_{10}&=22\\ e_{11}&=23\\ e_{12}&=41\\ e_{13}&=47\\ e_{14}&=59\\ e_{15}&=89\\ e_{16}&=107\\ e_{17}&=167\\ e_{18}&=179\\ e_{19}&=263\\ e_{20}&=347\\ e_{21}&=467\\ e_{22}&=683\\ e_{23}&=719\\ e_{24}&=1223\\ e_{25}&=1438\\ e_{26}&=1439\\ e_{27}&=2879\\ e_{28}&=3767\\ e_{29}&=4283\\ e_{30}&=6299\\ e_{31}&=10079\\ e_{32}&=11807\\ e_{33}&=15287\\ e_{34}&=21599\\ e_{35}&=33599\\ e_{36}&=45197\\ e_{37}&=56039\\ e_{38}&=81647\\ e_{39}&=98999\\ e_{40}&=163259\\ e_{41}&=203999\\ e_{42}&=241883\\ e_{43}&=371447\\ e_{44}&=540539\\ e_{45}&=590399\\ e_{46}&=907199\\ e_{47}&=1081079\\ e_{48}&=1851119\\ e_{49}&=2041199\\ e_{50}&=3243239\\ e_{51}&=3840479\\ e_{52}&=6562079\\ e_{53}&=8206559\\ e_{54}&=11696759\\ e_{55}&=14648759\\ e_{56}&=22312799\\ e_{57}&=27494879\\ e_{58}&=41746319\\ e_{59}&=52252199\\ e_{60}&=78331679\\ e_{61}&=108606959\\ e_{62}&=142990559\\ e_{63}&=203098319\\ e_{64}&=273985919\\ e_{65}&=382021919\\ e_{66}&=495437039\\ e_{67}&=681327359\\ e_{68}&=1006290359\\ e_{69}&=1406394359\\ e_{70}&=1857794399\\ e_{71}&=2728424159\\ e_{72}&=3743197919\\ e_{73}&=5008227839\\ e_{74}&=6872690159\\ e_{75}&=9839491199\\ e_{76}&=13485479039\\ e_{77}&=16724776319\\ e_{78}&=24679458719\\ e_{79}&=35524698479\\ e_{80}&=44211625919\\ e_{81}&=62391692159\\ e_{82}&=93753213119\\ e_{83}&=121551917759\\ e_{84}&=163539961199\\ e_{85}&=250585241759\\ e_{86}&=320429329919\\ e_{87}&=424847520719\\ e_{88}&=630371064959\\ e_{89}&=872573642639 \end{align}$

数値観察としては、 $e_1=1, e_4 = 4, e_7 = 10, e_{10} = 22, e_{25} = 1438$ を除くと全て素数です。また、 $e_4, e_7, e_{10}, e_{25}$ については素数の $2$ 倍です。

Question２ $e_n$ は $n=1, 5, 7, 10, 25$ を除いて全て素数だろうか？

更に、 $\frac{e_n-1}{2}$ も素数が多い傾向がみられます。例えば $37 \leq n \leq 89$ では $n=75$ を除いて素数です。つまり、 $e_n$ はSophie Germain素数を量産している可能性があります*2。

$e_n$ のことがよくわかっていないのに対して、複雑度が $n\geq 1$ となるような最大の自然数 $M(n)$ は決定されています。

定理(Selfridge) $\epsilon \in \{0, \pm 1\}, \ k \geq 1$ とする。このとき、 $M(3k+\epsilon)=3^k+\epsilon 3^{k-1}$ である。

略証. 複雑度の定義から

$\displaystyle M(m)=\max_{a+b=m}\{M(a)+M(b), M(a)M(b)\}$ –①

が成り立つことがわかる。明らかに $M(1)=1$ であり、①を使えば $M(2)=2, M(3)=3$ がわかる。あとは①を利用して $m$ に関する数学的帰納法によって証明できる*3。 Q.E.D.

一般に $c(n) \leq n$ なので、 $c(n), c(c(n) ), c(c(c(n) ) ), \dots$ と複雑度を取る操作を反復すると、有限回で $c(m)=m$ なる不動点 $m$ に到達します。不動点に到達するまでの回数が $h$ であるような最小の $n$ が $h=1$ から $h=5$ までは知られています。それはすなわち次の六つの数です。