[ 新着記事
| 新着メモ
| 数学・プログラミング
| 天文・暦
| シリア語・Unicode・詩
| ジョーク
| 漫画・アニメ
| 字幕
| 哲学・ファンタジー
| 全記事 ]
チラ裏
「チラ裏」はメモ。誤字・誤記・脱線が多いです!
2023-01-23 LLT: Lehmer’s Lemma 1 ギネスに載る素数…?
#数論 #フィボナッチ #Lucas-Lehmer
新しいメルセンヌ素数が発見されると、場合によっては「世界最大の既知の素数」として、一般メディアでも話題になる。2023年1月現在の最大 [3] は、2018年に発見された 282589933 − 1 で、2500万桁に近い。
計算以前に「数字自体を書く」だけでも大変な巨大さで、1ページに1万桁ずつ書くとしても約2500ページ。毎秒1桁ずつ飲まず食わずで数字を書き続けたとして、書き終わるのは10カ月後だ!
そんなでかい数が素数か素数でないか、どうやって判定されるのか? 一般には困難な問題だが、メルセンヌ数に限っては「LLT」という方法がある。やり方自体はシンプルで、普通の人でも容易に理解可能。比較的小さいメルセンヌ数なら、ブラウザ上の JavaScript でも判定は可能。「なぜその方法で判定できるの?」という理論についても、基本アルゴリズムを完成させた D. H. Lehmer 自身による初等的な証明 [2] があり、フィボナッチ数列のいとこ「バイナッチ数列」と関係している。一連のメモでは、この証明を最終目的地として各ステップをのんびり検討し、興味を引くような話題があれば寄り道もして、いろんな景色を楽しみたい。
(続き)
2023-01-20 その数列は強いか? 「星のらせん階段」
#数論 #フィボナッチ #Lucas-Lehmer
ちょうど10段ごとに一周するらせん階段では、10段目・20段目・30段目…が、階段の基点(0段目)の真上になる。そのように、フィボナッチ数列では、第10項・第20項・第30項…が同じ倍数列の上で、きれいにハモっている。
F20 = 6765, F30 = 832040, F40 = …
が、全部 F10 = 55 でキッカリ割り切れる*9のだ!
この性質は、10に限らず任意の周期で成り立つ: F6, F12, F18, … も倍数列、F7, F14, F21, … も倍数列。その結果、例えば F20 は「F4 から始まる倍数列」、「F10 から始まる倍数列」など、複数の周期の「波」に乗っていて、自分自身も F20, F40, F60, … という新たな「波」の出発点となる。
フィボナッチ数で遊んでて、この性質に気付いたときは、ちょ~美しい!と感じ「星のらせん階段」と名付けた。フィボナッチ数の黄金比は、正五角形・星型と縁が深いので「星」。フィボナッチ数には、巻き貝のような「らせん」のイメージもある――この渦巻きは「ジョジョの奇妙な冒険」第7部でも、重要な小道具となってるようだ*10。スイスのチューリッヒ中央駅にも、らせんとフィボナッチ数を題材にした巨大オブジェがある(画像)。
「星のらせん」構造を持つ数列は、正式には divisibility sequence と呼ばれるらしい。フィボナッチのいとこ「バイナッチ」も同じ構造を持つが、フィボナッチは「強い」、バイナッチは「弱い」という違いがある。後学のため「強い・弱い」の意味を具体例で観察しておきたい。
(続き)
2023-01-17 バイナッチ数列の加法定理
#数論 #フィボナッチ #Lucas-Lehmer
フィボナッチ数列の場合、Binet の公式や加法定理が、いろいろな研究の土台となった。フィボナッチ数列のいとこ「バイナッチ数列」についても、加法定理を考えてみたい。導出法はフィボナッチ版とほとんど同じで、その復習ともいえる。加法定理の一つでは、フィボナッチ版にはなかった係数が付く(この係数は「逆数」の形の違いに由来し、さかのぼると、背後にある2次方程式の定数項の、符号を変えたものに当たる)。
(続き)
2023-01-16 「マイナス番目」のフィボナッチ数? 因数の出現位置
#数論 #フィボナッチ #Lucas-Lehmer
フィボナッチ数列 1, 1, 2, 3, 5, 8, 13, …。その第1項 F1 = 1 の直前の理論上の「第0項」は F0 = 0 だが、そのさらに直前の「第マイナス1項」は何だろうか? このような「マイナス番目の項」を考えることで、通常の範囲のフィボナッチ数列について、素敵な性質が証明される。
(続き)
2023-01-13 いかすぜ!バイナッチ 依存症者の末路…w
#数論 #フィボナッチ #Lucas-Lehmer
フィボナッチ数列というのは 1, 1, 2, 3, 5, 8, 13, 21, … のように、各項が直前の2項の和になっている数列の一種。「第0項」の 0 から始めると:
0, 1, 1, 2, 3, 5, 8, 13, 21, …
それと似ているが、ひとひねり加え、各項を直前の2項の和の2倍としてみよう:
0, 1, 2, 6, 16, 44, 120, 328, …
例えば第3項(左端の 0 を第0項とする)の 6 は、直前の2項の和 1+2 の2倍。第4項の 16 は、直前の2項の和 2+6 の2倍。以下同様。フィボナッチ数列の「直前の2項の和」という部分に「~の2倍」という処理を追加した数列なんで、これをバイナッチ数列と呼ぶことにする(正式名称ではない)。「一般化 Lucas 数列」の一例だが、あまり取り上げられることのない存在だろう。どんな景色が待ち受けているのだろうか…
(続き)
2023-01-12 アンラッキー・セブン④ あなたの勘では…?
フェルマー風の数列――
A: 3, 5, 9, 17, 33, 65, 129, …
それは 2 が倍々となる次の数列の各項に 1 を足したもの。
B: 2, 4, 8, 16, 32, 64, 128, …
A の偶数番目の項 5, 17, 65 = 5 × 13, 257, 1025 = 5 × 5 × 41, … を調べると、どの数も、そしてどの約数も、「4 の倍数より 1 大きい」という性質を持っているようだ。そういう目で、今度は A の奇数番目の項を眺めると:
3, 9 = 3 × 3, 33 = 3 × 11, 129 = 3 × 43, 513 = 3 × 3 × 3 × 19, …
因数にやけに 3 が多いことはさておき、どの素因数も「4 の倍数より 1 小さい」ようだ(3, 11, 43, 19)。――偶数番目・奇数番目の項に関するこの観察。たまたま数列の最初の方がそうなってるだけなのだろうか。それとも、どこまで行っても、無限にこの性質が維持されるのか?
あなたの勘では…?
(続き)
2023-01-08 オイラーの定理 もしも週が8日だったら
#数論
「小学生のフェルマーの小定理」の別バージョン。簡単な算数だけで「オイラーの定理」。アホくさい(けど分かりやすい?)アプローチをお楽しみください。
【1】 「1週間が8種類の曜日から成る異世界」を考える。8種類の曜日を順に「1曜日」「2曜日」…「8曜日」と呼ぶことにして、話を簡単にするため、毎月の「1日」は「1曜日」に固定されているとする(そして月の日数は無限にあるとしよう)。「8曜日」である8日の翌日の9日は、「1曜日」に戻る。そのまた翌日の10日は「2曜日」。そして例えば(その5日後の)15日は「7曜日」…。一般に「D日」は、D が8の倍数なら「8曜日」で、そうでなければ D を8で割った余りを R として「R曜日」となる。
(続き)
2023-01-04 アンラッキー・セブン③ 2は1の4乗根!?
#数論
ある数の4乗根とは、4乗するとその数になる値。例えば 3 を 4 乗すると…
34 = 3 × 3 × 3 × 3 = (3 × 3) × (3 × 3) = 9 × 9 = 81
…なので 3 は 81 の4乗根。同様に 24 = 16 なので、2 は 16 の4乗根。
パラレルワールドの一つ mod 5 の世界では、「5 で割った余りが同じなら同じ値」と見なされるので、16 と 11 と 6 と 1 などは「同じ」(合同):
16 ≡ 11 ≡ 6 ≡ 1 (mod 5)
だから 24 ≡ 1 (mod 5) であり、2 は 1 の4乗根となる!
驚くべきことに 3 以上のどんな奇数 a を考えても、パラレルワールド mod a では、2 は 1 の何乗根かになっている。例えば…
(続き)
2023-01-02 アンラッキー・セブン② 幸運と不運の分かれ目
#数論
2, 4 = 2 × 2, 8 = 2 × 2 × 2, 16 = 2 × 2 × 2 × 2, …は「2 だけ」を掛け合わせた数なので、3 では割り切れない。より詳しく言うと、2 は 3 の倍数より 1 小さい(この場合の「3 の倍数」とは「3 の 1 倍」つまり 3 自身)。このことを次のような記号で表す:
2 ≡ −1 (mod 3)
一方、4 は 3 の倍数より 1 大きい。8 は 3 の倍数より 1 小さく、16 は 3 の倍数より 1 大きい。記号的には、それぞれこうなる:
4 ≡ 1 (mod 3), 8 ≡ −1 (mod 3), 16 ≡ 1 (mod 3)
これについては、最初の…
2 ≡ −1 (mod 3)
…の両辺を2乗・3乗・4乗したと考えると、見通しがいい。例えば:
4 ≡ 1 (mod 3) は 22 ≡ (−1)2 (mod 3) と同じこと(☆)
8 ≡ −1 (mod 3) は 23 ≡ (−1)3 (mod 3) と同じこと
ところで本題とは全然関係ないが、(☆)は「マイナスかけるマイナスがプラスになることの証明」といえなくもない…。22 ≡ (−1)2 が 4 ≡ 1 と同じ意味であるからには、(−1)2 = (−1) × (−1) が +1 と同じ意味にならねばならず、事実 4 は 3 の倍数プラス 1 である!
(続き)
2022-12-31 アンラッキー・セブン 2, 4, 8, 16, 32…の不思議
#数論 #ジグモンディの定理
2 を次々と倍々にした数 2, 4, 8, 16, 32, … に、それぞれ 1 を足してみます。
3, 5, 9, 17, 33, …
この一つ一つの数は、どんな数で割り切れるでしょうか?
3, 5, 17 は素数(1 と自分自身でしか割り切れない数)。9 は 3 で(2回)割り切れます。33 は 3 と 11 で割り切れます。
64, 128, … など、もうちょっと先まで同様のことを考えてみると――
(続き)
「チラ裏」は、きちんとまとまった記事ではなく、断片的なメモです…
Map
の長所、splice
より速い要素挿入法も紹介。 〔最終更新: 2016年4月10日〕bdi
要素と Unicode 6.3 の新しい双方向アルゴリズム (2012-12-04)dir
属性は落とし穴が多い。HTML5 の <bdi>
は役立つ。近い将来、「ユーザー入力欄などの語句は、このタグで隔離」が常識になるかも。 〔最終更新: 2014年4月27日〕fad()
は濁りやすい。各種の代替手段を紹介。forum.doom9.org
/ videolan.org