インテジャーズ

INTEGERS

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

経済的数・倹約的数

正整数n経済的数(resp. 倹約的数)であるとはnの素因数分解表示に用いるアラビア数字の個数がnの桁数を超えない(resp. nの桁数より小さい)ときにいいます。ただし、素因数分解表示は指数表記するものとします。

これらの概念はSantos(1995), Pinch(1998)で導入されました。

Bernardo Recamán Santos, Equidigital representation: problem 2204, J. Rec. Maths 27 (1995), no. 1, 58–59.
R. G. E. Pinch, Economical numbers, arXiv:math/9802046 [math.NT], 1998.

素数は全て経済的数ですが倹約的数ではありません。最小の倹約的数は125=5^3です。n \geq 6に対して2^nは経済的数です。

倹約的数最初の100個(n番目の倹約的数をa_nとする)

\begin{align}&a_1=125 =5^3 \\
&a_{2}=128=2^7 \\
&a_{3}=243=3^5 \\
&a_{4}=256=2^8 \\
&a_{5}=343=7^3 \\
&a_{6}=512=2^9 \\
&a_{7}=625=5^4 \\
&a_{8}=729=3^6 \\
&a_{9}=1024=2^{10} \\
&a_{10}=1029=3\times 7^3 \\
&a_{11}=1215=3^5\times 5 \\
&a_{12}=1250=2\times 5^4 \\
&a_{13}=1280=2^8\times 5 \\
&a_{14}=1331=11^3 \\
&a_{15}=1369=37^2 \\
&a_{16}=1458=2\times 3^6 \\
&a_{17}=1536=2^9\times 3 \\
&a_{18}=1681=41^2 \\
&a_{19}=1701=3^5\times 7 \\
&a_{20}=1715=5\times 7^3 \\
&a_{21}=1792=2^8\times 7 \\
&a_{22}=1849=43^2 \\
&a_{23}=1875=3\times 5^4 \\
&a_{24}=2048=2^{11} \\
&a_{25}=2187=3^7 \\
&a_{26}=2197=13^3 \\
&a_{27}=2209=47^2 \\
&a_{28}=2401=7^4 \\
&a_{29}=2560=2^9\times 5 \\
&a_{30}=2809=53^2 \\
&a_{31}=3125=5^5 \\
&a_{32}=3481=59^2 \\
&a_{33}=3584=2^9\times 7 \\
&a_{34}=3645=3^6\times 5 \\
&a_{35}=3721=61^2 \\
&a_{36}=4096=2^{12} \\
&a_{37}=4374=2\times 3^7 \\
&a_{38}=4375=5^4\times 7 \\
&a_{39}=4489=67^2 \\
&a_{40}=4802=2\times 7^4 \\
&a_{41}=4913=17^3 \\
&a_{42}=5041=71^2 \\
&a_{43}=5103=3^6\times 7 \\
&a_{44}=5329=73^2 \\
&a_{45}=6241=79^2 \\
&a_{46}=6250=2\times 5^5 \\
&a_{47}=6561=3^8 \\
&a_{48}=6859=19^3 \\
&a_{49}=6889=83^2 \\
&a_{50}=7203=3\times 7^4 \\
&a_{51}=7921=89^2 \\
&a_{52}=8192=2^{13} \\
&a_{53}=9375=3\times 5^5 \\
&a_{54}=9409=97^2 \\
&a_{55}=10000=2^4\times 5^4 \\
&a_{56}=10082=2\times 71^2 \\
&a_{57}=10112=2^7\times 79 \\
&a_{58}=10125=3^4\times 5^3 \\
&a_{59}=10201=101^2 \\
&a_{60}=10206=2 \times 3^6 \times 7 \\
&a_{61}=10240=2^{11}\times 5 \\
&a_{62}=10368=2^7\times 3^4 \\
&a_{63}=10375=5^3\times 83 \\
&a_{64}=10443=3\times 59^2 \\
&a_{65}=10449= 3^5\times 43\\
&a_{66}=10496=2^8\times 41 \\
&a_{67}=10609=103^2 \\
&a_{68}=10624=2^7\times 83 \\
&a_{69}=10625=5^4\times 17 \\
&a_{70}=10633=7^3\times 31 \\
&a_{71}=10658=2\times 73^2 \\
&a_{72}=10752=2^9\times 3\times 7 \\
&a_{73}=10935=3^7\times 5 \\
&a_{74}=10976=2^5\times 7^3 \\
&a_{75}=10985=5\times 13^3 \\
&a_{76}=11008=2^8\times 43 \\
&a_{77}=11045=5\times 47^2 \\
&a_{78}=11125=5^3\times 89 \\
&a_{79}=11163=3\times 61^2 \\
&a_{80}=11392=2^7\times 89 \\
&a_{81}=11421=3^5\times 47 \\
&a_{82}=11449=107^2 \\
&a_{83}=11664=2^4\times 3^6 \\
&a_{84}=11767=7\times 41^2 \\
&a_{85}=11776=2^9\times 23 \\
&a_{86}=11875=5^4\times 19 \\
&a_{87}=11881=109^2 \\
&a_{88}=11907=3^5\times 7^2 \\
&a_{89}=12005=5\times 7^4 \\
&a_{90}=12032=2^8\times 47 \\
&a_{91}=12125=5^3\times 97 \\
&a_{92}=12167=23^3 \\
&a_{93}=12288=2^{12}\times 3 \\
&a_{94}=12393=3^6\times 17 \\
&a_{95}=12416=2^7\times 97 \\
&a_{96}=12482=2\times 79^2 \\
&a_{97}=12500=2^2\times 5^5 \\
&a_{98}=12544= 2^8\times 7^2\\
&a_{99}=12691=2^3\times 37 \\
&a_{100}=12769=113^2\end{align}

連続する経済的数・倹約的数

Pinchは次の9連続経済的数を見つけています:


\begin{align}&1034429177995381247=51551\times 20066132140897\\ 
&1034429177995381248=2^9\times 3\times 88651\times 7596716293\\
&1034429177995381249=17\times 60848775176198897\\
&1034429177995381250=2\times 5^5\times 76757\times 2156268073\\
&1034429177995381251=3^5\times 19\times 383\times 584981475541\\
&1034429177995381252=2^2\times 7^5\times 154267\times 99741877\\
&1034429177995381253= 394007\times 2625408122179\\
&1034429177995381254= 2\times 3\times 23\times 59^3\times 1367\times 26699131\\
&1034429177995381255=5\times 26264543\times 7877001157\end{align}


実は、任意の長さの連続倹約的数の存在が

J.-M. De Koninck, F. Luca, On strings of consecutive economical numbers of arbitrary length, INTEGERS (2005), Volume: 5, Issue: 2, #A5.

で示されています。そのことを以下で証明します。

ここから「である調」に転調し、十進法に限らずb進法で考えることにする(b \geq 2)。d(n)nの桁数とする。すなわち、d(n)=[\log_bn]+1 (d(n)=d \Longleftrightarrow b^{d-1}\leq n < b^d)。

nの素因数分解を\displaystyle n=\prod_{p \mid n}p^{e_p}とするとき、\phi(n)

\displaystyle \phi(n):=\sum_{p \mid n}\left(d(p)+d'(e_p)\right)

と定義する。ただし、d'n > 1に対してd'(n)=d(n)およびd'(1)=0で定まる関数とする。h(n):=d(n)-\phi(n)とする。

定義 正整数nh(n) \geq 0を満たすときnは経済的数であるといい、h(n) > 0を満たすときnは倹約的数であるという。

\omega(n)nの相異なる素因数の個数とする: 数論的関数 ω(n) - INTEGERS

\displaystyle d(n) > \frac{\log n}{\log b} および \displaystyle \phi(n) \leq 2\omega(n)+\sum_{p \mid n}\frac{\log(pe_p)}{\log b} なので、

\displaystyle h(n) > \frac{1}{\log b}\cdot \log \prod_{p \mid n}\frac{p^{e_p-1}}{e_p}-2\omega(n) \tag{1}

が成り立つ。

補題 正整数nが素数qの二乗で割り切れるとする。このとき、q > 2b^{\omega(n)}が成り立てばnは倹約的数である。

証明. \displaystyle n=\prod_{p \mid n}p^{e_p}を素因数分解とするとき、\displaystyle \prod_{p \mid n}\frac{p^{e_p-1}}{e_p} \geq \frac{q}{2} > b^{2\omega(n)}が成り立つので、(1)より

\displaystyle h(n) > \frac{1}{\log b}\cdot \log b^{2\omega(n)}-2\omega(n)=0

となって、nは倹約的数である。 Q.E.D.

定理 (De Koninck-Luca) 任意の長さの連続する倹約的数が存在する。

証明. xを十分大きい正の数とし、\varepsilonを十分小さい正の数とする。\displaystyle k:=\left[\frac{\varepsilon \log \log x}{\log b}\right]とおく。素数定理よりx2xの間にある素数の二乗の個数は大体

\displaystyle \frac{2\sqrt{x}}{\log x}(\sqrt{2}-1)

であり、xが十分大きければこれはkより大きい。そこで、[x, 2x]内のk個の素数の平方p_1^2, \dots, p_k^2をとる。P:=\prod_{i=1}^kp_i^2とするとx^k\leq P \leq (2x)^kである。中国式剰余定理によってP-k以下の正整数nが存在して*11 \leq i \leq kに対してm_i:=n+i-1p_i^2の倍数である。過去記事の補題より

\displaystyle \omega(m_i) =O\left(\frac{\log m_i}{\log \log m_i}\right) = O\left(\frac{\log P}{\log \log P}\right) = O\left(\frac{k\log 2x}{\log \log x}\right)

なので、\varepsilonが十分小さければ

\displaystyle \log \left(2b^{2\omega(m_i)}\right)=\log 2+\log b \cdot O\left(\frac{k\log 2x}{\log \log x}\right)=\log 2+\frac{1}{3}\log x

が成り立つ。一方、

\log 2+\frac{1}{3}\log x < \frac{1}{2}\log x \leq \log p_i

であるから、2b^{2\omega(m_i)} < p_iが成り立つ。よって、補題よりm_iは倹約的数である。すなわち、長さkの連続する倹約的数m_1, \dots, m_kが得られた。x \to \inftyk \to \inftyなので定理の証明が完了する。 Q.E.D.

*1:P-k < n \leq Pとすると合同条件から矛盾する。