インテジャーズ

INTEGERS

数、特に整数に関する記事。

自然数の複雑度

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

例えば、79の複雑度は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}


Question1 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倍です。

Question2 e_nn=1, 5, 7, 10, 25を除いて全て素数だろうか?

更に、\frac{e_n-1}{2}も素数が多い傾向がみられます。例えば37 \leq n \leq 89ではn=75を除いて素数です。つまり、e_nSophie 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に関する数学的帰納法によって証明できる*3Q.E.D.

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

683 \to 22 \to 10 \to 7 \to 6 \to 1

ちなみに、683は素数。

*1:Iraids-Balodis-Cernenoks-Opmanis-Opmanis-Podnieks

*2:\frac{e_n-1}{2}の方がSophie Germain素数で、e_nは安全素数。

*3:安直に(a, bも含めて)3で割った余りで分類して計算していけばよいが全部書くと煩雑になるためここでは省略する。