インテジャーズ

INTEGERS

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

ラッキー数定理

この記事ではラッキー数を紹介します。Wikipediaでは幸運数という訳語で紹介されていますが、Eulerの幸運数とは異なるものです。Eulerの幸運数については

tsujimotter.hatenablog.com

を参照してください。

ラッキー数の定義

素数はEratosthenesの篩という篩によってふるい分けられる数と言えます。

エラトステネスの篩 - Wikipedia

Ulamによって素数の類似物として考案されたラッキー数は、Eratosthenesの篩に似た別の篩によってふるい分けられる数のことを言います。

篩のルール S_n=\{a_{n, m}\}_{m=1}^{\infty}が自然数からなる数列であるとき、次のルールで篩を行い、新しい数列S_{n+1}を定義する:
N=a_{n, n}に着目し、Nの倍数番目の項である
a_{n, N}, a_{n, 2N}, a_{n, 3N}, \dots
S_nから取り除いて出来る数列をS_{n+1}とする。

Step1

スタートは自然数列

\begin{align}S_1= &1, \  2, \  3, \  4, \  5, \  6, \  7, \  8, \  9, \  10, \  11, \  12, \  13, \  14, \  15, \  16, \  17, \  18, \  19, \  20, \  21, \  22, \  23, \  24, \  25, \ \\ &26, \  27, \  28, \  29, \  30, \  31, \  32, \  33, \  34, \  35, \  36, \  37, \  38, \  39, \  40, \  41, \  42, \  43, \  44, \  45, \  46, \  47, \  \\ &48, \  49, \  50, \  51, \  52, \  53, \  54, \  55, \  56, \  57, \  58, \  59, \  60, \  61, \  62, \  63, \  64, \  65, \  66, \  67, \  68, \  69, \ \\ &70, \  71, \  72, \  73, \  74, \  75, \  76, \  77, \  78, \  79, \  80, \  81, \  82, \  83, \  84, \  85, \  86, \  87, \  88, \  89, \  90, \  91, \  \\ &92, \  93, \  94, \  95, \  96, \  97, \  98, \  99, \  \dots \end{align}

です。自然数を篩って特殊な数を取り出そうとするのですから。

ところが、S_1篩のルールを適用してしまうと、着目する数がN=a_{1, 1}=1であるため、篩ったらいきなり空数列*1となってしまいます。

というわけで、スタートステップだけ特別ルールで始めます。

「都合のいいやつだな〜」と思われるかもしれませんが、Eratosthenesの篩のときもある意味そうでしたよね?

1は意図的にすっとばして、2に丸をつけて、2以外の2の倍数を消すことから始めるのでした(最初の素数が2と定義から決まっているということでもあります)。

今回も1はすっとばして、着目する数を特別にN=a_{1, 2}=2としましょう。

そうして、

\begin{align}&a_{1, 2}, \  a_{1,4}, \  a_{1,6}, \  a_{1, 8}, \  a_{1, 10}, \  a_{1, 12}, \  a_{1, 14}, \  a_{1, 16}, \  a_{1, 18}, \  a_{1, 20}, \  a_{1, 22}, \  a_{1, 24}, \  a_{1, 26}, \  a_{1, 28}, \  a_{1, 30}, \ \\ &a_{1, 32}, \  a_{1, 34}, \  a_{1, 36}, \  a_{1, 38}, \  a_{1, 40}, \  a_{1, 42}, \  a_{1, 44}, \  a_{1, 46}, \  a_{1, 48}, \  a_{1, 50}, \  a_{1, 52}, \  a_{1, 54}, \  a_{1, 56}, \  a_{1, 58}, \  a_{1, 60}, \ \\ &a_{1, 62}, \  a_{1, 64}, \  a_{1, 66}, \  a_{1, 68}, \  a_{1, 70}, \  a_{1, 72}, \  a_{1, 74}, \  a_{1, 76}, \  a_{1, 78}, \  a_{1, 80}, \  a_{1, 82}, \  a_{1, 82}, \  a_{1, 84}, \  a_{1, 86}, \  a_{1, 88}, \ \\ &a_{1, 90}, \  a_{1, 92}, \  a_{1, 94}, \  a_{1, 96}, \  a_{1, 98}, \  \dots\end{align}


を篩い落とします。すなわち、

\begin{align}&2, \  4, \  6, \  8, \  10, \  12, \  14, \  16, \  18, \  20, \  22, \  24, \  26, \  28, \  30, \  32, \  34, \  36, \  38, \  40, \  42, \  44, \  46, \  48, \  50, \ \\ &52, \  54, \  56, \  58, \  60, \  62, \  64, \  66, \  68, \  70, \  72, \  74, \  76, \  78, \  80, \  82, \  84, \  86, \  88, \  90, \  92, \  94, \  96, \  98, \ \\ &\dots\end{align}

を篩い落として

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65, 66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99, \dots

\begin{align}S_2= &1, \  3, \  5, \  7, \  9, \  11, \  13, \  15, \  17, \  19, \  21, \  23, \  25, \  27, \  29, \  31, \  33, \  35, \  37, \  39, \  41, \  43, \  45, \  47, \ \\ &49, \  51, \  53, \  55, \  57, \  59, \  61, \  63, \  65, \  67, \  69, \  71, \  73, \  75, \  76, \  77, \  79, \  81, \  83, \  85, \  87, \  89, \ \\ &91, \  93, \  95, \  97, \  99, \ \dots\end{align}

となります(奇数列。スタートステップはEratosthenesの篩とほぼ同じで、1が残るか2が残るかの違いがあります。後でも採用することになりますが、2を残して(1は消して)残りを奇数列とする、スタートはEratosthenesの篩に合わせる流儀もあります)。

Step2

ここからは、篩のルール通りに篩っていきましょう(あるいは、スタートステップの特別性が気に入らなければS_2から開始することにしても構いません)。注目する数はN=a_{2,2}=3です。

\begin{align}&a_{2, 3}, \  a_{2, 6}, \  a_{2, 9}, \  a_{2, 12}, \  a_{2, 15}, \  a_{2, 18}, \  a_{2, 21}, \  a_{2, 24}, \  a_{2, 27}, \  a_{2, 30}, \  a_{2, 33}, \  a_{2, 36}, \  a_{2, 39}, \  a_{2, 42}, \  a_{2, 45}, \ \\ &a_{2, 48}, \  a_{2, 51}, \  \dots\end{align}

すなわち、

5, \  11, \  17, \  23, \  29, \  35, \  41, \  47, \  53, \  59, \  65, \  71, \  76, \  81, \  87, \  93, \  99, \  \dots

S_2から篩い落とします。そうして、

1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21, 23, 25, 27, 29, 31, 33, 35, 37, 39, 41, 43, 45, 47, 49, 51, 53, 55, 57, 59, 61, 63, 65, 67, 69, 71, 73, 75, 76, 77, 79, 81, 83, 85, 87, 89, 91, 93, 95, 97, 99, \dots

\begin{align}S_3= &1, \ 3, \ 7, \ 9, \ 13, \ 15, \ 19, \ 21, \ 25, \ 27, \ 31, \ 33, \ 37, \ 39, \ 43, \ 45, \ 49, \ 51, \ 55, \ 57, \ 61, \ 63, \ 67, \ \\ &69, \ 73, \ 75, \ 77, \ 79, \ 83, \ 85, \ 89, \ 91, \ 95, \ 97, \ \dots \end{align}

となります。

Step3

注目する数はN=a_{3, 3}=7です。

a_{3, 7}, \ a_{3, 14}, \ a_{3, 21}, \ a_{3, 28}, \dots

すなわち、

19, \ 39, \ 61, \ 79, \dots

S_3から篩い落とします。そうして、

1, 3, 7, 9, 13, 15, 19, 21, 25, 27, 31, 33, 37, 39, 43, 45, 49, 51, 55, 57, 61, 63, 67, 69, 73, 75, 77, 79, 83, 85, 89, 91, 95, 97, \dots

\begin{align}S_4= &1, \ 3, \ 7, \ 9, \ 13, \ 15, \ 21, \ 25, \ 27, \ 31, \ 33, \ 37, \ 43, \ 45, \ 49, \ 51, \ 55, \ 57, \ 63, \ 67, \ 69, \ 73, \ 75, \ \\ &77, \ 83, \ 85, \ 89, \ 91, \ 95, \ 97, \ \dots\end{align}

となります。

Step4

注目する数はN=a_{4, 4}=9です。

a_{4, 9}, \ a_{3, 18}, \ a_{3, 27}, \dots

すなわち、

27, \ 57, \ 89, \dots

S_4から篩い落とします。そうして、

1, 3, 7, 9, 13, 15, 21, 25, 27, 31, 33, 37, 43, 45, 49, 51, 55, 57, 63, 67, 69, 73, 75, 77, 83, 85, 89, 91, 95, 97, \dots

\begin{align}S_5= &1, \ 3, \ 7, \ 9, \ 13, \ 15, \ 21, \ 25, \ 31, \ 33, \ 37, \ 43, \ 45, \ 49, \ 51, \ 55, \ 63, \ 67, \ 69, \ 73, \ 75, \ 77, \ 83, \ \\ &85, \ 91, \ 95, \ 97, \ \dots\end{align}

となります。

Step ∞

この操作(篩)を永遠に繰り返して最終的に残る数列の項のことをラッキー数と定義します。

すなわち、S_nの各項を元とする集合を\mathcal{S}_nとして、

\displaystyle \mathcal{S} := \bigcap_{n=1}^{\infty}\mathcal{S}_n

と集合\mathcal{S}を定義し、\mathcal{S}の元を小さい順に並べて出来る狭義単調増加数列をSとすると、Sがラッキー数からなる数列となります。

100以下のラッキー数:

1, \ 3, \ 7, \ 9, \ 13, \ 15, \ 21, \ 25, \ 31, \ 33, \ 37, \ 43, \ 49, \ 51, \ 63, \ 67, \ 69, \ 73, \ 75, \ 79, \ 87, \ 93, \ 99

Eratosthenesの篩との違い

Eratosthenesの篩は印を付けた素数の倍数を全て取り除く篩でした。

ラッキー数を定義するUlamの篩は、それまでの篩で取り除かれた数のことは忘れて、残っている数の中で数えて印の付いた数(ラッキー数)の倍数番目を取り除いていく篩です。

こうして、篩を少し変えることによって素数の類似物が定義されたわけですが、この記事では素数に関するある定理とある予想達のラッキー数での類似物を紹介したいと思います。

なお、素数のときと違って、ラッキー数が無数に存在することは定義から明らかです。

ラッキー数定理

n番目の素数をp_nとしたとき、

p_n \sim n\log n, \ \ n \to \infty

が成り立つというのが、所謂素数定理でした:素数定理 - INTEGERS

この素数定理のラッキー数ヴァージョンが証明されています:

ラッキー数定理 (Hawkins-Briggs, 1958) n番目のラッキー数をs_nとするとき、漸近公式
s_n \sim n\log n, \ \ n \to \infty
が成り立つ。

以下、この定理の証明を紹介しましょう。これは確かに類似物ですが、証明は素数定理のときよりはるかに簡単になります。

ラッキー数定理の証明

この証明では、s_1=1ではなく、s_1=2であるという定義を採用する。まず、

m < s_nを満たすようなn, mに対して(n\geq 2)、s_m=a_{n, m}が成り立つ ー①

ことに注意する。何故ならば、S_nからS_{n+1}へ篩うとき、a_{n, s_n}が最初に取り除かれる数だからである。

\pi_n^{{\rm lucky}}(x)を、x以下であるようなS_nの項の数と定義する。このとき、Ulamの篩の定義からn \geq 2に対して

\displaystyle \pi_n^{{\rm lucky}}(x) = \pi_{n-1}^{{\rm lucky}}(x) - \left[ \frac{\pi_{n-1}^{{\rm lucky}}(x)}{s_{n-1}}\right] ー②

が成り立つ(s_1=2なので、n=1でも成立することに注意)。[\quad ]はGauss記号。n \geq 2に対して、\sigma_n

\displaystyle \sigma_n := \prod_{i=1}^{n-1}\left( 1-\frac{1}{s_i}\right)

と定義する。すると、②を繰り返し用いることによって、n \geq 2に対して

\displaystyle \pi_n^{{\rm lucky}}(x) = [x]\sigma_n + \sum_{i=2}^n\frac{\sigma_n}{\sigma_i}\left\{ \frac{\pi_{i-1}^{{\rm lucky}}(x)}{s_{i-1}}\right\} ー③

が成立することがわかる(\{\quad\}は少数部分)。

\displaystyle R_n(x) :=  \sum_{i=2}^n\frac{\sigma_n}{\sigma_i}\left\{ \frac{\pi_{i-1}^{{\rm lucky}}(x)}{s_{i-1}}\right\}

とすれば、

0 \leq R_n(x) < n ー④

である。n < s_nであることと、①、 ④より、

n = \pi_n^{{\rm lucky}}(s_n) \geq s_n\sigma_n

が成り立つので、

\displaystyle \frac{\sigma_{n+1}}{\sigma_n} = 1-\frac{1}{s_n} \leq 1-\frac{\sigma_n}{n}

と評価される。\rho_n:=\sigma_n^{-1}とすれば、これは

\displaystyle \rho_{n+1}-\rho_n \geq \frac{\rho_{n+1}}{n\rho_n} > \frac{1}{n}

と変形できる。最後の評価は\rho_nが単調増加であることから従う。よって、望遠鏡和を取れば、

\displaystyle \rho_n-2> \sum_{i=1}^{n-1}\frac{1}{i} \geq \log (n-1)

を得る(最後の不等式についてはこちら)。よって、n \geq 2に対しては

\displaystyle \sigma_n < \frac{1}{\log n} ー⑤

が成り立つことが示された。

さて、n > 2ならs_n > 2nが成り立つので(偶数のラッキー数が存在しないことからわかる)、①、③、④より

\begin{align}2n &= \pi_n^{{\rm lucky}}(s_{2n}) = s_{2n}\sigma_n+R_n(s_{2n}) < s_{2n}\sigma_n+n\\ 2n-1 &= \pi_n^{{\rm lucky}}(s_{2n-1}) = s_{2n-1}\sigma_n+R_n(s_{2n-1}) < s_{2n-1}\sigma_n+n\end{align}

なので、⑤より

\begin{align}&s_{2n} > n\log n\\ &s_{2n-1} > (n-1)\log n\end{align}

が成り立つ。これらを合わせれば、n\geq 2に対して

s_n > c_1n\log n ー⑥

が成り立つことが分かる(c_iと書いたら或る正の定数を表すことにする)。よって、

\displaystyle \sigma_n = \prod_{i=1}^{n-1}\left( 1-\frac{1}{s_i} \right) > c_2\prod_{i=n_0}^{n-1}\left( 1-\frac{1}{c_1i\log i} \right)

と評価でき(n_0を適切な番号)、両辺の対数を取れば

\displaystyle 0 > \log \sigma_n > \sum_{i=n_0}^{n-1}\log \left( 1-\frac{1}{c_1i \log i}\right) - c_3.

0 < x \leq 0.5828に対して

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

が成り立つので、n_0が十分大きく取れていれば

\displaystyle 0 > \log \sigma_n > -c_4\sum_{i=n_0}^{n-1}\frac{1}{i\log i} - c_3

と評価できる。アーベルの総和法の漸近公式5より

\displaystyle 0 > \log \sigma_n > -c_5\log \log n

が得られた。対数をはずせば

\displaystyle \sigma_n > \frac{1}{(\log n)^{c_5}} ー⑦

と⑤と逆向きの評価が得られる。n \geq 2に対して、整数\alpha_n

s_{\alpha_n-1} < n \leq s_{\alpha_n}

が成り立つように定める。このとき、⑥より

n > s_{\alpha_n-1} > c_6\alpha_n\log \alpha_n

であり、⑦より

\displaystyle \alpha_n \geq s_{\alpha_n}\sigma_{\alpha_n} > n\sigma_n > \frac{n}{(\log n)^{c_5}}

であることから(\alpha_nの定義とs_n > nから\alpha_n < nであることに注意)、

\displaystyle \alpha_n < \frac{c_7n}{\log \alpha_n} < \frac{c_7n}{\log n - c_5\log \log n} < \frac{c_8n}{\log n} ー⑧

が示された。これを元に、R_n(s_n)を次のように二分割する:

\displaystyle R_{n, 1}:=\sum_{2 \leq i \leq \frac{c_8n}{\log n}}\frac{\sigma_n}{\sigma_i}\left\{ \frac{\pi_{i-1}^{{\rm lucky}}(s_n)}{s_{i-1}}\right\} = O\left( \frac{n}{\log n} \right),

\displaystyle R_{n, 2}:=\sum_{\frac{c_8n}{\log n} < i \leq n}\frac{\sigma_n}{\sigma_i}\left\{ \frac{\pi_{i-1}^{{\rm lucky}}(s_n)}{s_{i-1}}\right\}.

\displaystyle \frac{c_8n}{\log n} < i \leq nなるiについては、⑧および①から

\pi_{i-1}^{{\rm lucky}}(s_n)=\pi_{\alpha_n}^{{\rm lucky}}(s_n)=n

が成り立つので、\sigma_n/\sigma_i1で押さえて、中括弧の部分は中括弧を外して評価することにより、⑥から

\displaystyle R_{n, 2} = O \left( \sum_{\frac{c_8n}{\log n} < i \leq n}\frac{n}{i\log i} \right) = O \left( \frac{n\log \log n}{\log n} \right)

を得る*2

以上より、R_n(s_n)=o(n)が示された。すなわち、

n=s_n\sigma_n + o(n)

が成り立つ。よって、

\displaystyle \frac{\sigma_{n+1}}{\sigma_n} = 1-\frac{1}{s_n}=1-\frac{\sigma_n}{n+o(n)}

であり、

\displaystyle \frac{1}{n+o(n)} = \frac{1}{n}+o\left( \frac{1}{n} \right)

に注意すれば、\rho_n=\sigma_n^{-1}に対して

\displaystyle \rho_{n+1}-\rho_n = \frac{\rho_{n+1}}{n\rho_n} + o\left( \frac{\rho_{n+1}}{n\rho_n} \right)

が成り立つ。

\displaystyle \frac{\rho_{n+1}}{\rho_{n}}=\frac{1}{1+o(1)} = 1+o(1)

でもあるので、

\displaystyle \rho_{n+1}-\rho_n = \frac{1}{n}+o\left(\frac{1}{n}\right) ー⑨

が得られた。調和数の記事で示したEuler定数の存在から

\displaystyle \sum_{i=1}^{n}\frac{1}{i} \sim \log n

が成り立つので、⑨に対して望遠鏡和を取れば

\rho_n \sim \log n

が示されたことになる。こうして、

s_n=\rho_n (n+o(n) )\sim n\log n

が証明された。 Q.E.D.


このようにラッキー数定理は驚くべきほど簡単に証明されるのですが、ラッキー数の分布の仕方に自然対数が現れるというのは、定義から考えると素数定理のときと同じく極めて神秘的であります。

証明を見ると、自然対数が現れるからくりを調和数が自然対数に漸近することに求めることができるので、やはり

\displaystyle \int_1^x\frac{dt}{t} = \log x

というのは美しいなあと感じます。

なお、\displaystyle \pi^{{\rm lucky}}(x) = \lim_{n \to \infty}\pi_n^{{\rm lucky}}(x)x以下のラッキー数の個数とすれば、

\displaystyle \pi^{{\rm lucky}}(x) \sim \frac{x}{\log x}, \quad x \to \infty

が成り立つことは素数定理 - INTEGERSでやったのと全く同様にして示せます。

ラッキー数に関する予想

素数定理の類似としてラッキー数定理の証明を紹介しました。素数のときに色々考えてきたことを逐一ラッキー数に対しても考えることは面白いと思いますが、Goldbach予想の類似物が予想されています。すなわち、

予想 任意の正の偶数は二つのラッキー数の和として表すことができるであろう(s_1=1を採用)。

他にも、差が2であるようなラッキー数のペアを双子ラッキー数と呼べば、双子ラッキー数予想*3が出来上がります。

次のような未解決問題もあります:

Ulamの予想 n\geq 3ならば、s_n > p_nが成り立つであろう。

これは十分大きいnに対しては証明されています。

また、ラッキー数かつ素数であるようなものをラッキー素数と言い、ラッキー素数が無数に存在するかは未解決です。

1000以下のラッキー素数:

\begin{align}&3, 7, 13, 31, 37, 43, 67, 73, 79, 127, 151, 163, 193, 211, 223, 241, 283, 307, 331, 349, 367,\\ &409, 421, 433, 463, 487, 541, 577, 601, 613, 619, 631, 643, 673, 727, 739, 769, 787, 823,\\ &883, 937, 991, 997\end{align}

ラッキー数最初の300個

\begin{align}s_{1}&= 1\\
s_{2}&= 3\\
s_{3}&= 7\\
s_{4}&= 9\\
s_{5}&= 13\\
s_{6}&= 15\\
s_{7}&= 21\\
s_{8}&= 25\\
s_{9}&= 31\\
s_{10}&= 33\\
s_{11}&= 37\\
s_{12}&= 43\\
s_{13}&= 49\\
s_{14}&= 51\\
s_{15}&= 63\\
s_{16}&= 67\\
s_{17}&= 69\\
s_{18}&= 73\\
s_{19}&= 75\\
s_{20}&= 79\\
s_{21}&= 87\\
s_{22}&= 93\\
s_{23}&= 99\\
s_{24}&= 105\\
s_{25}&= 111\\
s_{26}&= 115\\
s_{27}&= 127\\
s_{28}&= 129\\
s_{29}&= 133\\
s_{30}&= 135\\
s_{31}&= 141\\
s_{32}&= 151\\
s_{33}&= 159\\
s_{34}&= 163\\
s_{35}&= 169\\
s_{36}&= 171\\
s_{37}&= 189\\
s_{38}&= 193\\
s_{39}&= 195\\
s_{40}&= 201\\
s_{41}&= 205\\
s_{42}&= 211\\
s_{43}&= 219\\
s_{44}&= 223\\
s_{45}&= 231\\
s_{46}&= 235\\
s_{47}&= 237\\
s_{48}&= 241\\
s_{49}&= 259\\
s_{50}&= 261\\
s_{51}&= 267\\
s_{52}&= 273\\
s_{53}&= 283\\
s_{54}&= 285\\
s_{55}&= 289\\
s_{56}&= 297\\
s_{57}&= 303\\
s_{58}&= 307\\
s_{59}&= 319\\
s_{60}&= 321\\
s_{61}&= 327\\
s_{62}&= 331\\
s_{63}&= 339\\
s_{64}&= 349\\
s_{65}&= 357\\
s_{66}&= 361\\
s_{67}&= 367\\
s_{68}&= 385\\
s_{69}&= 391\\
s_{70}&= 393\\
s_{71}&= 399\\
s_{72}&= 409\\
s_{73}&= 415\\
s_{74}&= 421\\
s_{75}&= 427\\
s_{76}&= 429\\
s_{77}&= 433\\
s_{78}&= 451\\
s_{79}&= 463\\
s_{80}&= 475\\
s_{81}&= 477\\
s_{82}&= 483\\
s_{83}&= 487\\
s_{84}&= 489\\
s_{85}&= 495\\
s_{86}&= 511\\
s_{87}&= 517\\
s_{88}&= 519\\
s_{89}&= 529\\
s_{90}&= 535\\
s_{91}&= 537\\
s_{92}&= 541\\
s_{93}&= 553\\
s_{94}&= 559\\
s_{95}&= 577\\
s_{96}&= 579\\
s_{97}&= 583\\
s_{98}&= 591\\
s_{99}&= 601\\
s_{100}&= 613\\
s_{101}&= 615\\
s_{102}&= 619\\
s_{103}&= 621\\
s_{104}&= 631\\
s_{105}&= 639\\
s_{106}&= 643\\
s_{107}&= 645\\
s_{108}&= 651\\
s_{109}&= 655\\
s_{110}&= 673\\
s_{111}&= 679\\
s_{112}&= 685\\
s_{113}&= 693\\
s_{114}&= 699\\
s_{115}&= 717\\
s_{116}&= 723\\
s_{117}&= 727\\
s_{118}&= 729\\
s_{119}&= 735\\
s_{120}&= 739\\
s_{121}&= 741\\
s_{122}&= 745\\
s_{123}&= 769\\
s_{124}&= 777\\
s_{125}&= 781\\
s_{126}&= 787\\
s_{127}&= 801\\
s_{128}&= 805\\
s_{129}&= 819\\
s_{130}&= 823\\
s_{131}&= 831\\
s_{132}&= 841\\
s_{133}&= 855\\
s_{134}&= 867\\
s_{135}&= 873\\
s_{136}&= 883\\
s_{137}&= 885\\
s_{138}&= 895\\
s_{139}&= 897\\
s_{140}&= 903\\
s_{141}&= 925\\
s_{142}&= 927\\
s_{143}&= 931\\
s_{144}&= 933\\
s_{145}&= 937\\
s_{146}&= 957\\
s_{147}&= 961\\
s_{148}&= 975\\
s_{149}&= 979\\
s_{150}&= 981\\
s_{151}&= 991\\
s_{152}&= 993\\
s_{153}&= 997\\
s_{154}&= 1009\\
s_{155}&= 1011\\
s_{156}&= 1021\\
s_{157}&= 1023\\
s_{158}&= 1029\\
s_{159}&= 1039\\
s_{160}&= 1041\\
s_{161}&= 1053\\
s_{162}&= 1057\\
s_{163}&= 1087\\
s_{164}&= 1093\\
s_{165}&= 1095\\
s_{166}&= 1101\\
s_{167}&= 1105\\
s_{168}&= 1107\\
s_{169}&= 1117\\
s_{170}&= 1123\\
s_{171}&= 1147\\
s_{172}&= 1155\\
s_{173}&= 1167\\
s_{174}&= 1179\\
s_{175}&= 1183\\
s_{176}&= 1189\\
s_{177}&= 1197\\
s_{178}&= 1201\\
s_{179}&= 1203\\
s_{180}&= 1209\\
s_{181}&= 1219\\
s_{182}&= 1231\\
s_{183}&= 1233\\
s_{184}&= 1245\\
s_{185}&= 1249\\
s_{186}&= 1251\\
s_{187}&= 1261\\
s_{188}&= 1263\\
s_{189}&= 1275\\
s_{190}&= 1281\\
s_{191}&= 1285\\
s_{192}&= 1291\\
s_{193}&= 1303\\
s_{194}&= 1309\\
s_{195}&= 1323\\
s_{196}&= 1329\\
s_{197}&= 1339\\
s_{198}&= 1357\\
s_{199}&= 1365\\
s_{200}&= 1369\\
s_{201}&= 1387\\
s_{202}&= 1389\\
s_{203}&= 1395\\
s_{204}&= 1401\\
s_{205}&= 1417\\
s_{206}&= 1419\\
s_{207}&= 1435\\
s_{208}&= 1441\\
s_{209}&= 1455\\
s_{210}&= 1459\\
s_{211}&= 1471\\
s_{212}&= 1473\\
s_{213}&= 1485\\
s_{214}&= 1491\\
s_{215}&= 1495\\
s_{216}&= 1497\\
s_{217}&= 1501\\
s_{218}&= 1503\\
s_{219}&= 1519\\
s_{220}&= 1533\\
s_{221}&= 1543\\
s_{222}&= 1545\\
s_{223}&= 1563\\
s_{224}&= 1567\\
s_{225}&= 1575\\
s_{226}&= 1579\\
s_{227}&= 1585\\
s_{228}&= 1587\\
s_{229}&= 1597\\
s_{230}&= 1599\\
s_{231}&= 1611\\
s_{232}&= 1639\\
s_{233}&= 1641\\
s_{234}&= 1645\\
s_{235}&= 1659\\
s_{236}&= 1663\\
s_{237}&= 1675\\
s_{238}&= 1693\\
s_{239}&= 1701\\
s_{240}&= 1705\\
s_{241}&= 1711\\
s_{242}&= 1723\\
s_{243}&= 1731\\
s_{244}&= 1737\\
s_{245}&= 1749\\
s_{246}&= 1765\\
s_{247}&= 1767\\
s_{248}&= 1771\\
s_{249}&= 1773\\
s_{250}&= 1777\\
s_{251}&= 1797\\
s_{252}&= 1801\\
s_{253}&= 1809\\
s_{254}&= 1819\\
s_{255}&= 1827\\
s_{256}&= 1831\\
s_{257}&= 1833\\
s_{258}&= 1839\\
s_{259}&= 1857\\
s_{260}&= 1869\\
s_{261}&= 1879\\
s_{262}&= 1893\\
s_{263}&= 1899\\
s_{264}&= 1915\\
s_{265}&= 1921\\
s_{266}&= 1923\\
s_{267}&= 1933\\
s_{268}&= 1941\\
s_{269}&= 1945\\
s_{270}&= 1959\\
s_{271}&= 1963\\
s_{272}&= 1965\\
s_{273}&= 1977\\
s_{274}&= 1983\\
s_{275}&= 1987\\
s_{276}&= 1995\\
s_{277}&= 2001\\
s_{278}&= 2019\\
s_{279}&= 2023\\
s_{280}&= 2031\\
s_{281}&= 2053\\
s_{282}&= 2059\\
s_{283}&= 2065\\
s_{284}&= 2067\\
s_{285}&= 2079\\
s_{286}&= 2083\\
s_{287}&= 2085\\
s_{288}&= 2095\\
s_{289}&= 2113\\
s_{290}&= 2115\\
s_{291}&= 2121\\
s_{292}&= 2125\\
s_{293}&= 2127\\
s_{294}&= 2133\\
s_{295}&= 2163\\
s_{296}&= 2173\\
s_{297}&= 2187\\
s_{298}&= 2209\\
s_{299}&= 2211\\
s_{300}&= 2215\end{align}

*1:そんな言葉ないかもしれません笑。

*2:最後の計算はアーベルの総和法の漸近公式5をもう少し精密に見れば分かる。大体

\begin{align}\log \log n-\log\log \frac{n}{\log n} &= \log \log n- \log \left\{ \log n \left( 1-\frac{\log \log n}{\log n} \right) \right\}\\ &= - \log  \left( 1-\frac{\log \log n}{\log n}\right) = O\left( \frac{\log \log n}{\log n} \right)\end{align}
なる計算で\displaystyle \frac{\log \log n}{\log n}が出てくることが分かる。実際には非本質的な定数が色々つくが、同じである。

*3:「双子ラッキー数は無数に存在するであろう」という予想。

マーティン・ガードナーのラッキー数 2187

マーティン・ガードナーが住んでいた家の住所に2187という数があったそうです。

2187=3^7

2187+7812=9999

21\times 87 = 1827

27\times 81=2187

何故この数がマーティン・ガードナーのラッキー数と言われているかというと、ラッキー数になっているからです。
integers.hatenablog.com

他にも次のような式が成り立ちます:

\begin{align}&2187 + 1234 = 3421\\
&2187 + 12345 = 14532\\
&2187 + 123456 = 125643\\
&2187 + 1234567 = 1236754\\
&2187 + 12345678 = 12347865\\
&2187 + 123456789 = 123458976\end{align}

ハッピー・ゴー・ラッキー数

ハッピー・ゴー・ラッキー数とは、ハッピー数かつラッキー数であるような自然数のことを言います。

integers.hatenablog.com

integers.hatenablog.com

ハッピー・ゴー・ラッキー数最初の100個

\begin{align}&1, 7, 13, 31, 49, 79, 129, 133, 193, 219, 319, 331, 367, 391, 409, 487, 655, 673, 739, 931, \\ &937, 1009, 1029, 1039, 1093, 1209,1233, 1251, 1275, 1281, 1285, 1303, 1309, 1323,\\ &1339, 1533, 1575, 1587, 1599, 1663, 1771, 1857, 1933, 1959, 1995, 2019, 2115, 2121,\\ &2133, 2211, 2221, 2257, 2511, 2527, 2545, 2557, 2571, 2575, 2715, 2725, 2755, 2815,\\ &2845, 2851, 2899, 2901, 3031, 3091, 3097, 3109, 3123, 3133, 3153, 3213, 3301, 3313,\\ &3351, 3355, 3465, 3607, 3661, 3709, 3763,3789, 3879, 3897, 3931, 4069, 4255, 4257,\\ &4285, 4287, 4363, 4441, 4455, 4609, 4653, 4663, 4725, 4741\end{align}

10000番目のハッピー・ゴー・ラッキー数941547を僕は「串行こーよ、な!」で覚えています。

ハッピー・ゴー・ラッキー素数

ハッピー・ゴー・ラッキー数であって素数であるようなものをハッピー・ゴー・ラッキー素数と言います。

なんだか幸福感半端なさそうな数ですネ!

ハッピー・ゴー・ラッキー素数最初の100個

\begin{align}&7, 13, 31, 79, 193, 331, 367, 409, 487, 673, 739, 937, 1009, 1039, 1093, 1303, 1663, 1933,\\ &2221, 2557, 2851, 3109, 3301, 3313, 3607, 3709, 3931
, 4363, 4441, 4663, 5527, 5569,\\ &6163, 6367, 6373, 6661, 6733, 6763, 7603, 8233, 10009, 10903, 11113, 11197, 11491,\\ &13009, 13177, 13309, 14281, 14347, 14407, 14437, 14449, 14461, 15121, 16417, 17713,\\ &18253, 18523, 18757, 19333, 19963, 20899, 21787, 21841, 22381, 22651, 22921, 23893,\\ &24181, 25057, 25237, 25561, 25621, 25657, 26251, 27283, 27793, 28123, 28351, 28393,\\ &28513, 28771, 28837, 28933, 30013, 30103, 30313, 30367, 30643, 31033, 31039, 31699,\\ &32803, 33091, 33289, 34603, 36037, 36067, 37117\end{align}


100番目のハッピー・ゴー・ラッキー素数の覚え方は「皆いいな」、

1000番目のハッピー・ゴー・ラッキー素数786271を僕は「悩むトゥナイッ☆」で覚えています。

「兄さんヤクザ」23893もハッピー・ゴー・ラッキー素数ですね。

局所有限性に関する補題

定義 位相空間Xの部分集合族\mathcal{F}局所有限であるとは、Xの各点が高々有限個の\mathcal{F}の元としか共通部分を持たないような近傍を持つときにいう。

補題1 Xを位相空間、\mathcal{F}Xの局所有限な部分集合族とし、\mathcal{F}の元は全て閉集合であるとする。このとき、\displaystyle \bigcup_{F\in \mathcal{F}}Fも閉集合となる。

証明.O\displaystyle \bigcup_{F\in \mathcal{F}}Fの補集合としてOが開集合であることを示す。O \neq \emptysetのときに示せばよい。x \in Oを任意に取る。\mathcal{F}が局所有限なので、x \in Vであり、Vと共通部分を持つ\mathcal{F}の元が有限個(それらをF_1, \dots, F_kとする)であるような開集合Vが存在する。\displaystyle U:=\bigcap_{i=1}^k(X\setminus F_i) \cap Vとおくと、これは開集合でx \in Uであり、\displaystyle U \cap \bigcup_{F \in \mathcal{F}}F=\emptysetなのでU \subset Oを満たす。よって、Oは開集合である。 Q.E.D.

補題2 Hausdorff位相群の任意の離散部分群は閉部分群である。

証明. HGの離散部分群とする。\displaystyle H=\bigcup_{h \in H}\{h\}であるが、任意のh \in Hに対して\{h\}は閉集合(GはHausdorff)なので、\displaystyle \mathcal{F}:=\{\{h\}\mid h\in H\}が局所有限であることを示せば補題1よりHGの閉部分群となる。よって、\mathcal{F}が局所有限であることを示そう。Gの単位元をeとする。\mathcal{F}が局所有限でないと仮定して矛盾を導く。すなわち、あるg \in Gが存在してgの任意の近傍が\mathcal{F}の無限個の元と共通部分を持つ(すなわち、Hの元を無数に含む)と仮定する。HGの離散部分群であることからU\cap H=\{e\}を満たすようなGの開部分集合Uが存在する。更にGが位相群であることからe \in V, V^{-1}V \subset Uを満たす開集合Vが存在する。gVgの近傍なので、仮定よりh_1, h_2 \in Hが存在してh_1, h_2 \in gVおよびh_1 \neq h_2が成り立つ。すると、h_1^{-1}h_2 \in V^{-1}V \subset Uなので、e \neq h_1^{-1}h_2 \in U \cap Hとなり、Uの取り方に矛盾する。 Q.E.D.

当然、Hausdorffという仮定の部分はT_0でもよいです。ちなみにT_0位相群はHausdorffです。

図形の問題の解答

先日紹介した思い出の図形問題

integers.hatenablog.com

の解答を幾つか紹介します。

解答1

f:id:integers:20161015072626j:plain

AB=CDという条件から、図のように

\triangle ABD \equiv \triangle CDE

となるように点Eを導入する。このとき、AD=CEかつ\angle ADE=\angle CED=110^{\circ}が成り立ち、この状況において四角形ADECが等脚台形になっていることはよく知られた通り。よって、錯角を見れば\angle ACB=40^{\circ}がわかる。

解答2

f:id:integers:20161015075150j:plain

図のようにBE=BAとなるように(すなわち、\angle AEB=70^{\circ}となるように)補助線AEを引く。このとき、二辺夾角相等により

\triangle ABE \equiv \triangle DCA

が示せるので、\angle ACB=\angle EBA=40^{\circ}を得る。


以上、二つの解答は直接的な証明ですが、解答1は補助線を2本使うのに対し、解答2は補助線1本で済むというのが中学生時代の私の小さな喜びだったわけです。この問題を色々なところで人に話すと、解答2を答えてくれる人もたくさんいます。一方、以下で述べる解答3、4は間接法です*1

同一法

問題の条件を満たす図形の存在は"up to similarity"で一意的であることがすぐに分かります。なので、\angle ACB=40^{\circ}であって問題の条件が全て成立するような図形を構成出来れば証明が完了します。論理的にはそれだけの話ですが、受験業界では同一法という用語を用いることが多いようです。同一法による証明を紹介しましょう。

解答3

f:id:integers:20161015081131j:plain

図のように底角が40^{\circ}であるような二等辺三角ABCを考え、\angle BAD=30^{\circ}となるように線分BC上に点Dをとる。このとき、AB=CDを示せばよいが、\angle CAD=\angle CDA=70^{\circ}なので、AC=CDであり、AB=AC=CDを得る。

なお、この図形は正十八角形の対角線のみで作ることができます(正十八角形の一辺に対する円周角は10^{\circ}なので、容易に角度計算ができます)。

f:id:integers:20161015093827j:plain

解答4は背理法です。

解答4

f:id:integers:20161012224246j:plain

? < 40^{\circ}と仮定する。このとき、AB < ACとなり、従ってDC < ACとなる。すると、\angle CAD < \angle ADC = 70^{\circ}となって、\triangle ACDの内角の和が180^{\circ}より小さくなってしまう。しかし、我々は今Euclid幾何学の世界にいるのであった。? > 40^{\circ}としても同様の矛盾が生じ、?=40^{\circ}でなければならない。

*1:それぞれ、同僚のゼリーさん、あーくさんから教えていただきました。

猫が大好き

めっきり寒くなってきましたね〜


夜中目が覚めると、異常に寒いですブルブル


そういえば、私は猫が大好きです。飼ってないですが、野良猫が大好きなのです。



野良猫と素数について語り合う時間が至福ですね。彼らは日本語を喋らないのでただの私の独り言の可能性もありますが。



最近のニュースですが、ディオファントスの5つ組予想を解決したと主張するプレプリントがプレプリントサーバに投稿されました:

[1610.04020] There is no Diophantine quintuple


ディオファントスの5つ組予想については

integers.hatenablog.com

を参照してください。


それでは