number_bot解説
number_botに現れるいろんな数。Wikipediaだけではわかりにくいものも多いので、ちょっと紹介したいと思います。
青字で数の定義、緑字で実例の部分を強調しています。
素数 Prime number
素数とは、1とその数自身以外に正の約数がない（つまり1とその数以外のどんな自然数によっても割り切れない）、1 より大きな自然数のこと。
素数 - Wikipedia
(中略)
整数の中で、あるいは実数の中での素数の分布の様子は高度に非自明で、リーマン予想のような現代数学の重要な問題との興味深い結びつきが発見されている。
さすがにこれは解説の必要はないかな、と思いますが。number_botの中で一番現れる数です。
素数の分布は上の引用文にもあるように一定ではありません。n番目の素数とn+1番目の素数の間隔は、nが大きくなるほど開く傾向がありますが、一様に大きくなっていくわけではありません。
この性質がnumber_botの「いつ通知がくるかわからないbot」という特徴のもとになっています。
この分布に大きく関係する(らしい)wikipedia:リーマン予想は現在数学の未解決問題の中で最も重要なものの1つで、wikipedia:ミレニアム懸賞問題にもなっています。
| order | number |
| 1 | 2 |
| 2 | 3 |
| 3 | 5 |
| 4 | 7 |
| … | … |
| 10 | 29 |
| … | … |
| 100 | 541 |
| … | … |
| 1000 | 7919 |
| … | … |
| 10000 | 104729 |
| … | … |
| 100000 | 1299709 |
完全数 Perfect number
完全数とは、その数自身を除く約数の和が、その数自身と等しい自然数のことである。
完全数 - Wikipedia
例えば 6 (=1+2+3)、28 (=1+2+4+7+14) が完全数である。
新ピュタゴラス学派は、最初の完全数が 6 なのは「神が6日間で世界を創造した」こと（天地創造）、次の完全数が 28 なのは「月の公転周期が28日である」ことと関連があると考えていたとされる。
「その数自身を除く約数の和が、その数自身と等しい」という条件はかなり厳しく、数の増え方が尋常ではありません。
number_botは100以上の数しか通知しないようにしているので、Twitterでは完全数は3,4番目しか見ることができません。
| order | number |
| 1 | 6 |
| 2 | 28 |
| 3 | 496 |
| 4 | 8128 |
| 5 | 33550336 |
| 6 | 8589869056 |
| 7 | 137438691328 |
| 8 | 2305843008139952128 |
| 9 | 2658455991569831744654692615953842176 |
| 10 | 191561942608236107294793378084303638130997321548169216 |
レピュニット Repunit
レピュニットとは、全ての桁が 1である自然数のことである。つまり 1, 11, 111, 1111,...である。
レピュニット - Wikipedia
repeated unitを省略したものが名前の由来である。
キリ番的で非常にわかりやすいです。number_botは一応「2222」「50000」など、わかりやすいキリ番は通知するようにしているのですが、レピュニットはしっかり名前がついているキリ番なので、大事に思っていただければと。
一度レピュニットが出現したとき、その次のレピュニットに出会うためには、今までの10倍+1のPostをしなければいけませんから。
| order | number |
| 1 | 1 |
| 2 | 11 |
| 3 | 111 |
| 4 | 1111 |
| 5 | 11111 |
| 6 | 111111 |
| 7 | 1111111 |
| 8 | 11111111 |
| 9 | 111111111 |
| 10 | 1111111111 |
| 11 | 11111111111 |
メルセンヌ数 Mersenne number
メルセンヌ数とは、2の冪よりも 1 小さい自然数、すなわち 2^n − 1 の形の自然数である。
メルセンヌ数 - Wikipedia
(中略)
また、素数であるメルセンヌ数をメルセンヌ素数という。後述するように、完全数との関連によって、メルセンヌ素数が特に興味ある対象である。
メルセンヌ数は何がうれしいのかというと、メルセンヌ素数から完全数が作れるのです。
しかも、偶数の完全数はメルセンヌ数から作られる形のみであるということが証明されているため、完全数を発見するためにはメルセンヌ素数を見つけるのが手っ取り早いのです。
巨大な数の約数なんて全部計算してられないですよね。
ちなみに、奇数の完全数は見つかっておらず、存在しない、ということも証明されていません。
number_botは2^nも通知するので、メルセンヌ数と2^nは2連続で通知が来ます。(最近は規制で届かないことも多いみたいでごめんなさい。)
| order | number |
| 1 | 1 |
| 2 | 3 |
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
| … | … |
| 10 | 1023 |
| … | … |
| 20 | 1048575 |
| … | … |
| 30 | 1073741823 |
フィボナッチ数 Fibonacci number
フィボナッチ数とは、イタリアの数学者レオナルド・フィボナッチ（ピサのレオナルド）にちなんで名付けられた数である。
フィボナッチ数 - Wikipedia
n番目のフィボナッチ数をF_nで表すと
F_0 = 0, F_1 = 1
F_n+2 = F_n + F_n+1
で定義される。
この数列はフィボナッチ数列と呼ばれ、最初の数項は
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, …
である。定義より、どの項もその前の2つの項の和となっている。
ある項が前の2つの項の和になっている数列です。
「あれ、最初って1,1からスタートじゃないの？」と感じる方もいると思いますが、0は0番目という定義になっています。
0番目から始めるか1番目から始めるかの違いです。
| order | number |
| 0 | 0 |
| 1 | 1 |
| 2 | 1 |
| 3 | 2 |
| 4 | 3 |
| 5 | 5 |
| 6 | 8 |
| 7 | 13 |
| 8 | 21 |
| 9 | 34 |
| 10 | 55 |
| … | … |
| 20 | 6765 |
| … | … |
| 100 | 354224848179261915075 |
トリボナッチ数 Tribonacci number
トリボナッチ数とは、次のように定義されるトリボナッチ数列に現れる数のことである。
T_0 = 0, T_1 = 0, T_2 = 1
T_n+3 = T_n + T_n+1 + T_n+2フィボナッチ数列が「前の2項の和」なのに対し、トリボナッチ数列は「前の3項の和」である。
フィボナッチ数 - Wikipedia
最初のいくつかの項は、次のようになる。
0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, …
フィボナッチ数の親戚その1。
フィボナッチ数と同じように、今度はある項が前の3つの項の和になっています。
"Fibonacci"に3を表す"Tri"をくっつけて"Tribonacci".
| order | number |
| 0 | 0 |
| 1 | 0 |
| 2 | 1 |
| 3 | 1 |
| 4 | 2 |
| 5 | 4 |
| 6 | 7 |
| 7 | 13 |
| 8 | 24 |
| 9 | 44 |
| 10 | 81 |
| … | … |
| 20 | 35890 |
| … | … |
| 100 | 53324762928098149064722658 |
テトラナッチ数 Tetranacci number
テトラナッチ数は、トリボナッチ数列と同様に次のように定義される、テトラナッチ数列に現れる数のことである。
フィボナッチ数 - Wikipedia
T_0 = 0, T_1 = 0, T_2 = 0, T_3 = 0
T_n+4 = T_n + T_n+1 + T_n+2 + T_n+3
フィボナッチ数列が「前の2項の和」、トリボナッチ数列が「前の3項の和」なのに対し、テトラナッチ数列は「前の4項の和」である。
フィボナッチ数の親戚その2。解説いらないよね？フィボナッチ数とトリボナッチ数を参照してください。
| order | number |
| 0 | 0 |
| 1 | 0 |
| 2 | 0 |
| 3 | 1 |
| 4 | 1 |
| 5 | 2 |
| 6 | 4 |
| 7 | 8 |
| 8 | 15 |
| 9 | 29 |
| 10 | 56 |
| … | … |
| 20 | 39648 |
| … | … |
| 100 | 2505471397838180985096739296 |
リュカ数 Lucas number
リュカ数（りゅかすう、Lucas number）とは、フランスの数学者エドゥアール・リュカにちなんで名付けられた数であり、n 番目のリュカ数を L_n で表わすと
リュカ数 - Wikipedia
L_0 = 2, L_1 = 1
L_n+2 = L_n + L_n+1
で定義される数列にある項のことである。
つまり、初項（最初のリュカ数）を 2、次の項を 1 と定義し、それ以降の項は前の2つの項の和になっている数列のことである。
フィボナッチ数の親戚その3。
フィボナッチ数が 1, 1 から始まるところを 2, 1 から始まるように、後のルールはフィボナッチ数と同じく、ある項が前の2つの項の和になっている数列です。
さらに、最初の2項を一般化したものをwikipedia:リュカ数列と言います。
| order | number |
| 0 | 2 |
| 1 | 1 |
| 2 | 3 |
| 3 | 4 |
| 4 | 7 |
| 5 | 11 |
| 6 | 18 |
| 7 | 29 |
| 8 | 47 |
| 9 | 76 |
| 10 | 123 |
| … | … |
| 20 | 15127 |
| … | … |
| 100 | 792070839848372253127 |
回文平方数 Palindromic square number
回文数（かいぶんすう）とは、14641のように逆から数字を読んでも同じ数になる数である。
回文数 - Wikipedia
逆から読んでも同じになる回文から名付けられた。
上は回文数の説明です。
回文平方数は、回文数で、かつ何かの数の2乗になっている数のことです。
4桁の回文平方数は存在しないため、676の次は10201と大きく離れます。
| order | number |
| 1 | 0 |
| 2 | 1 |
| 3 | 4 |
| 4 | 9 |
| 5 | 121 |
| 6 | 484 |
| 7 | 676 |
| 8 | 10201 |
| 9 | 12321 |
| 10 | 14641 |
| … | … |
| 20 | 6948496 |
カタラン数 Catalan number
カタラン数は、自然数のうち、ベルギーの数学者Eugène Charles Catalanによって名付けられた数である。
カタラン数 - Wikipedia
n番目のカタラン数C_nは以下の式で定義される。
定義式だけ見ても「何これ」という感じですが、組み合わせを扱うような問題では頻繁に現れます。
以下のリンクで様々な例を見ることができます。
wikipedia:カタラン数
http://www3.ocn.ne.jp/~fukiyo/math-obe/cataran2.htm
ƒJƒ^ƒ‰ƒ“”‚̈Ӗ¡
| order | number |
| 0 | 1 |
| 1 | 1 |
| 2 | 2 |
| 3 | 5 |
| 4 | 14 |
| 5 | 42 |
| … | … |
| 10 | 16796 |
| … | … |
| 20 | 6564120420 |
| … | … |
| 100 | 896519947090131496687170070074100632420837521538745909320 |
完全トーティエント数 Perfect totient number
この数を説明するためには、まず「オイラーのトーティエント関数」を説明しなければいけません。
オイラーのトーティエント関数は各正の整数 n に対して、1 から n までの自然数のうち n と互いに素なものの個数を φ(n) として与えることによって定まる数論的関数 φ である。
オイラーのφ関数 - Wikipedia
例えば、1, 2, 3, 4, 5, 6 のうち 6 と互いに素なのは 1, 5 の 2 個であるから、定義に拠れば φ(6) = 2 である。
また例えば 1, 2, 3, 4, 5, 6, 7 のうち 7 以外は全て 7 と互いに素だから、φ(7) = 6 と定まる。
このφ(n)の定義を踏まえた上で、完全トーティエント数の定義が以下です。
完全トーティエント数は、自然数のうち、以下の等式を満たす数nである。
完全トーティエント数 - Wikipedia
ここでφはオイラーのトーティエント関数である。
例えば327は φ(327) = 216, φ(216) = 72, φ(72) = 24, φ(24) = 8, φ(8) = 4, φ(4) = 2, φ(2) = 1 というように次々とφ関数の値を計算し、
それらの総和が 216 + 72 + 24 + 8 + 4 + 2 + 1 = 327 と元の数に等しくなるので完全トーティエント数である。
「総和が元の数に等しくなる」というのは完全数の定義と同じものです。
「そもそもオイラーのトーティエント関数なんて聞いたことないし、いったい何に使うんだ？」というのが大半の人の感想だと思います。
自分もそう思っていましたが、大学の「有限体と組み合わせ論」という授業で登場し驚きました。素数と約数には密接な関係があるため、扱いやすくするために考え出されたのでしょう。
| order | number |
| 1 | 3 |
| 2 | 9 |
| 3 | 15 |
| 4 | 27 |
| 5 | 39 |
| 6 | 81 |
| 7 | 111 |
| 8 | 183 |
| 9 | 243 |
| 10 | 255 |
| … | … |
| 20 | 5571 |
| … | … |
| 30 | 177147 |
カーマイケル数 Carmichael number
ある自然数 n が素数かどうかを判定するアルゴリズムは、古くから多くの手法が存在します。
一番なじみ深いものはwikipedia:エラトステネスの篩でしょうか。しかし、nが巨大な数だった場合この手法は時間がかかりすぎてしまうため、他の手法を考える必要があります。
素数を判定するアルゴリズムの中に、「確率的素数判定法」と呼ばれる種類のものがあります。
ある自然数 n が「合成数(素数でない数)」または「よくわからない」とするものです。
これを何回も繰り返し、一度も「合成数」と判定されなかった数は素数ではないか？というものを「確率的素数」といいます。
「確率的素数判定法」としていちばん有名なものに、「フェルマーの小定理」を利用したフェルマーテストというものがあります。
フェルマーテストは、 フェルマーの小定理の対偶を用いて確率的素数判定を行うアルゴリズムである。
次のように自然数 n の素数判定を行う。
フェルマーの小定理 - Wikipedia
1. パラメータとして、2 以上 n 未満の自然数 a を1つ定める。
2. a と n が互いに素でなければ「n は合成数」と出力して終了。
3.ならば「n は合成数」と出力して終了する。
そうでないとき「n は確率的素数」と出力して終了する。
n に対して、2 以上 n 未満の自然数 a を決めるのですが、a を全通り試して「合成数」と1回も判定されなかったら、nは「確率的素数」と言える、というわけです。
しかし、このフェルマーテストをいくらやっても、「確率的素数」と判定されてしまう「合成数」があります。
それを数列としたものがカーマイケル数です。
カーマイケル数とは、自身と互いに素である任意の底でフェルマーテストを通過する合成数である。
カーマイケル数 - Wikipedia
アメリカの数学者ロバート・ダニエル・カーマイケル（Robert Daniel Carmichael）に因んでこう呼ばれる。
また、絶対擬素数 (absolute pseudoprimes) とも呼ばれる。
つまり、とても厄介な奴らということです。
| order | number |
| 1 | 561 |
| 2 | 1105 |
| 3 | 1729 |
| 4 | 2465 |
| 5 | 2821 |
| 6 | 6601 |
| 7 | 8911 |
| 8 | 10585 |
| 9 | 15841 |
| 10 | 29341 |
| … | … |
| 20 | 162401 |
| … | … |
| 100 | 9439201 |
| … | … |
| 1000 | 3086434561 |
| … | … |
| 10000 | 1713045574801 |
