math, programming, and little something to laugh

number_bot解説

Twitter, 数学

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

完全数とは、その数自身を除く約数の和が、その数自身と等しい自然数のことである。

例えば 6 (=1+2+3)、28 (=1+2+4+7+14) が完全数である。

新ピュタゴラス学派は、最初の完全数が 6 なのは「神が6日間で世界を創造した」こと（天地創造）、次の完全数が 28 なのは「月の公転周期が28日である」ことと関連があると考えていたとされる。

完全数 - Wikipedia

「その数自身を除く約数の和が、その数自身と等しい」という条件はかなり厳しく、数の増え方が尋常ではありません。

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,...である。

repeated unitを省略したものが名前の由来である。

レピュニット - Wikipedia

キリ番的で非常にわかりやすいです。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

フィボナッチ数とは、イタリアの数学者レオナルド・フィボナッチ（ピサのレオナルド）にちなんで名付けられた数である。

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つの項の和となっている。

フィボナッチ数 - Wikipedia

ある項が前の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項の和」である。

最初のいくつかの項は、次のようになる。

0, 0, 1, 1, 2, 4, 7, 13, 24, 44, 81, 149, 274, 504, 927, 1705, 3136, 5768, 10609, 19513, 35890, 66012, …

フィボナッチ数 - Wikipedia

フィボナッチ数の親戚その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

テトラナッチ数は、トリボナッチ数列と同様に次のように定義される、テトラナッチ数列に現れる数のことである。

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項の和」である。

フィボナッチ数 - Wikipedia

フィボナッチ数の親戚その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 で表わすと

L_0 = 2, L_1 = 1

L_n+2 = L_n + L_n+1

で定義される数列にある項のことである。

つまり、初項（最初のリュカ数）を 2、次の項を 1 と定義し、それ以降の項は前の2つの項の和になっている数列のことである。

リュカ数 - Wikipedia

フィボナッチ数の親戚その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によって名付けられた数である。

n番目のカタラン数C_nは以下の式で定義される。

カタラン数 - Wikipedia

定義式だけ見ても「何これ」という感じですが、組み合わせを扱うような問題では頻繁に現れます。

以下のリンクで様々な例を見ることができます。

wikipedia:カタラン数

カタラン数（２）　〜さんすう・数学のお勉強〜

カタラン数の意味

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) として与えることによって定まる数論的関数 φ である。

例えば、1, 2, 3, 4, 5, 6 のうち 6 と互いに素なのは 1, 5 の 2 個であるから、定義に拠れば φ(6) = 2 である。

また例えば 1, 2, 3, 4, 5, 6, 7 のうち 7 以外は全て 7 と互いに素だから、φ(7) = 6 と定まる。

オイラーのφ関数 - Wikipedia

このφ(n)の定義を踏まえた上で、完全トーティエント数の定義が以下です。

完全トーティエント数は、自然数のうち、以下の等式を満たす数nである。

ここでφはオイラーのトーティエント関数である。

例えば327は φ(327) = 216, φ(216) = 72, φ(72) = 24, φ(24) = 8, φ(8) = 4, φ(4) = 2, φ(2) = 1 というように次々とφ関数の値を計算し、

それらの総和が 216 + 72 + 24 + 8 + 4 + 2 + 1 = 327 と元の数に等しくなるので完全トーティエント数である。

完全トーティエント数 - Wikipedia

「総和が元の数に等しくなる」というのは完全数の定義と同じものです。

「そもそもオイラーのトーティエント関数なんて聞いたことないし、いったい何に使うんだ？」というのが大半の人の感想だと思います。

自分もそう思っていましたが、大学の「有限体と組み合わせ論」という授業で登場し驚きました。素数と約数には密接な関係があるため、扱いやすくするために考え出されたのでしょう。

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 の素数判定を行う。

1. パラメータとして、2 以上 n 未満の自然数 a を1つ定める。

2. a と n が互いに素でなければ「n は合成数」と出力して終了。

3. ならば「n は合成数」と出力して終了する。

そうでないとき「n は確率的素数」と出力して終了する。

フェルマーの小定理 - Wikipedia

n に対して、2 以上 n 未満の自然数 a を決めるのですが、a を全通り試して「合成数」と1回も判定されなかったら、nは「確率的素数」と言える、というわけです。

しかし、このフェルマーテストをいくらやっても、「確率的素数」と判定されてしまう「合成数」があります。

それを数列としたものがカーマイケル数です。

カーマイケル数とは、自身と互いに素である任意の底でフェルマーテストを通過する合成数である。

アメリカの数学者ロバート・ダニエル・カーマイケル（Robert Daniel Carmichael）に因んでこう呼ばれる。

また、絶対擬素数 (absolute pseudoprimes) とも呼ばれる。

カーマイケル数 - Wikipedia

つまり、とても厄介な奴らということです。

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

ツイートする

Permalink | コメント(2) | トラックバック(1) | 20:24