数学とプログラミングの世界を楽しもう〜プロジェクトオイラー〜

プログラマのための数学勉強会@福岡で話したスライドです。

Transcript

1. 数学とプログラミングの 世界を楽しもう プログラマのための数学勉強会@福岡 2015.09.04 @tkengo
2. 立石 賢吾 Twitter : @tkengo github : @tkengo RubyとJavaScriptが好きです。でも、トトロの方が もっと好きです。
3. Project Euler
4. Project Euler 計算問題をプログラミングを使って 解いて答えを入力するサイト。
5. Project Euler •全ての問題は一般的なスペックのPCで1分以内で解ける。 •でも、別に1分以上かかっても答えが出ればOK。 •正解後にフォーラム上で他人の解答を閲覧可能。 •問題を解く度にレベルが上ったりアワードをもらえたり。
6. 問題紹介
7. 3と5の倍数
8. 10未満の3または5の倍数である自然数には3, 5, 6, 9が あり、それらの合計は23である。 では、1000未満の3または5の倍数の全ての自然数の合 計を求めよ。 問1: 3と5の倍数
9. 1000未満の3または5の倍数の全ての自然数の合計とは つまり... 3 + 5 + 6 + 9 + 10 + 12 + 15 + ... 問1: 3と5の倍数
10. 1000未満の3または5の倍数の全ての自然数の合計とは つまり... 3 + 5 + 6 + 9 + 10 + 12 + 15 + ... ( 3 + 6 + 9 + 12 + 15 + ...) = (①3の倍数の合計) 問1: 3と5の倍数
11. 1000未満の3または5の倍数の全ての自然数の合計とは つまり... 3 + 5 + 6 + 9 + 10 + 12 + 15 + ... ( 3 + 6 + 9 + 12 + 15 + ...) = + ( 5 + 10 + 15 + 20 + 25 + ...) (①3の倍数の合計) (②5の倍数の合計) 問1: 3と5の倍数
12. 問1: 3と5の倍数 1000未満の3または5の倍数の全ての自然数の合計とは つまり... 3 + 5 + 6 + 9 + 10 + 12 + 15 + ... ( 3 + 6 + 9 + 12 + 15 + ...) = + ( 5 + 10 + 15 + 20 + 25 + ...) - (15 + 30 + 45 + ...) (①3の倍数の合計) (②5の倍数の合計) (③15の倍数の合計) ※①と②で2回足し上げてる のを相殺するために引く
13. 問1: 3と5の倍数 1000未満の3または5の倍数の全ての自然数の合計とは つまり... 3 + 5 + 6 + 9 + 10 + 12 + 15 + ... ( 3 + 6 + 9 + 12 + 15 + ...) = + ( 5 + 10 + 15 + 20 + 25 + ...) - (15 + 30 + 45 + ...) = (①3の倍数の合計) (②5の倍数の合計) (③15の倍数の合計) ※①と②で2回足し上げてる のを相殺するために引く N(3) X k=1 3k + N(5) X k=1 5k N(15) X k=1 15k ✓ N(d) =  1000 1 d ◆
14. 問1: 3と5の倍数 各項が一定数ずつ増えていく数列のことを等比数列と言 いますね。等比数列の和というと... 例: 3 ずつ増えていく数列(公差 d = 3)
15. 問1: 3と5の倍数 各項が一定数ずつ増えていく数列のことを等比数列と言 いますね。等比数列の和というと... = 3 + 6 + 9 + ... + 996 + 999 例: 3 ずつ増えていく数列(公差 d = 3) S3
16. 問1: 3と5の倍数 各項が一定数ずつ増えていく数列のことを等比数列と言 いますね。等比数列の和というと... = 3 + 6 + 9 + ... + 996 + 999 = 999 + 996 + 993 + ... + 6 + 3 例: 3 ずつ増えていく数列(公差 d = 3) S3 S3
17. 問1: 3と5の倍数 各項が一定数ずつ増えていく数列のことを等比数列と言 いますね。等比数列の和というと... = 3 + 6 + 9 + ... + 996 + 999 = 999 + 996 + 993 + ... + 6 + 3 例: 3 ずつ増えていく数列(公差 d = 3) + S3 S3
18. 問1: 3と5の倍数 各項が一定数ずつ増えていく数列のことを等比数列と言 いますね。等比数列の和というと... = 3 + 6 + 9 + ... + 996 + 999 = 999 + 996 + 993 + ... + 6 + 3 = 1002 + 1002 + 1002 + ... + 1002 + 1002 例: 3 ずつ増えていく数列(公差 d = 3) + S3 S3 2S3
19. 問1: 3と5の倍数 各項が一定数ずつ増えていく数列のことを等比数列と言 いますね。等比数列の和というと... = 3 + 6 + 9 + ... + 996 + 999 = 999 + 996 + 993 + ... + 6 + 3 = 1002 + 1002 + 1002 + ... + 1002 + 1002 (= 333) 個 例: 3 ずつ増えていく数列(公差 d = 3) +  1000 1 3 S3 S3 2S3
20. 問1: 3と5の倍数 各項が一定数ずつ増えていく数列のことを等比数列と言 いますね。等比数列の和というと... = 3 + 6 + 9 + ... + 996 + 999 = 999 + 996 + 993 + ... + 6 + 3 = 1002 + 1002 + 1002 + ... + 1002 + 1002 例: 3 ずつ増えていく数列(公差 d = 3) + (= 333) 個  1000 1 3 S3 S3 2S3 S3 = 1 2 · 1002 · 333 = 501 · 333 = 166833
21. 問1: 3と5の倍数 一般的に公差 d の数列が n 個ある場合の総和は、以下の ようにして計算できますね。 例: d ずつ増えていく数列(公差 d) = d + 2d + ... + (n-1)d + nd Sn
22. 問1: 3と5の倍数 一般的に公差 d の数列が n 個ある場合の総和は、以下の ようにして計算できますね。 例: d ずつ増えていく数列(公差 d) = d + 2d + ... + (n-1)d + nd Sn = nd + (n-1)d + ... + 2d + d Sn
23. 問1: 3と5の倍数 一般的に公差 d の数列が n 個ある場合の総和は、以下の ようにして計算できますね。 例: d ずつ増えていく数列(公差 d) = d + 2d + ... + (n-1)d + nd Sn = nd + (n-1)d + ... + 2d + d Sn +
24. 問1: 3と5の倍数 一般的に公差 d の数列が n 個ある場合の総和は、以下の ようにして計算できますね。 例: d ずつ増えていく数列(公差 d) = d + 2d + ... + (n-1)d + nd Sn = nd + (n-1)d + ... + 2d + d Sn = (n+1)d + (n+1)d + ... + (n+1)d + (n+1)d 2Sn +
25. 問1: 3と5の倍数 一般的に公差 d の数列が n 個ある場合の総和は、以下の ようにして計算できますね。 例: d ずつ増えていく数列(公差 d) = d + 2d + ... + (n-1)d + nd Sn = nd + (n-1)d + ... + 2d + d Sn = (n+1)d + (n+1)d + ... + (n+1)d + (n+1)d 2Sn n 個 +
26. 問1: 3と5の倍数 一般的に公差 d の数列が n 個ある場合の総和は、以下の ようにして計算できますね。 例: d ずつ増えていく数列(公差 d) = d + 2d + ... + (n-1)d + nd Sn = nd + (n-1)d + ... + 2d + d Sn = (n+1)d + (n+1)d + ... + (n+1)d + (n+1)d 2Sn n 個 + Sn = 1 2 · (n + 1)d · n = n(n + 1)d 2
27. 問1: 3と5の倍数 等差数列の和の公式を使うと... N(3) X k=1 3k + N(5) X k=1 5k N(15) X k=1 15k ✓ N(d) =  1000 1 d ◆
28. 問1: 3と5の倍数 等差数列の和の公式を使うと... N(3) X k=1 3k + N(5) X k=1 5k N(15) X k=1 15k ✓ N(d) =  1000 1 d ◆ = N(3)((N(3) + 1)3 2 + N(5)(N(5) + 1)5 2 N(15)(N(15) + 1)15 2
29. 自乗の合計の差
30. 問6: 自乗の合計の差 最初の10個の自然数の”自乗の総和”は 最初の10個の自然数の”総和の自乗”は これらの差は　　　　　　　　である。 では、最初の100個の自然数の”自乗の総和”と”総和の自 乗”の差を求めよ。 12 + 22 + · · · + 102 = 385 (1 + 2 + · · · + 10)2 = 552 = 3025 3025 385 = 2640
31. 問6: 自乗の合計の差 総和の自乗は、問1で求めた等差数列の和の公式が適用 できますね。 (1 + 2 + · · · + 99 + 100)2 = ✓ 100(100 + 1) 2 ◆2
32. 問6: 自乗の合計の差 自乗の総和は別途公式があるので求めてみます。n = 4 までを計算してみると... 12 + 22 + 32 + 42
33. 問6: 自乗の合計の差 = 1 + (2 + 2) + (3 + 3 + 3) + (4 + 4 + 4 + 4) = 4 + (4 + 3) + (4 + 3 + 2) + (4 + 3 + 2 + 1) = 4 + (3 + 4) + (2 + 3 + 4) + (1 + 2 + 3 + 4) 12 + 22 + 32 + 42 9 + (9 + 9) + (9 + 9 + 9) + (9 + 9 + 9 + 9) 自乗の総和は別途公式があるので求めてみます。n = 4 までを計算してみると...
34. 問6: 自乗の合計の差 = 1 + (2 + 2) + (3 + 3 + 3) + (4 + 4 + 4 + 4) = 4 + (4 + 3) + (4 + 3 + 2) + (4 + 3 + 2 + 1) = 4 + (3 + 4) + (2 + 3 + 4) + (1 + 2 + 3 + 4) 12 + 22 + 32 + 42 9 + (9 + 9) + (9 + 9 + 9) + (9 + 9 + 9 + 9) 自乗の総和は別途公式があるので求めてみます。n = 4 までを計算してみると...
35. 問6: 自乗の合計の差 = 1 + (2 + 2) + (3 + 3 + 3) + (4 + 4 + 4 + 4) = 4 + (4 + 3) + (4 + 3 + 2) + (4 + 3 + 2 + 1) = 4 + (3 + 4) + (2 + 3 + 4) + (1 + 2 + 3 + 4) 12 + 22 + 32 + 42 9 + (9 + 9) + (9 + 9 + 9) + (9 + 9 + 9 + 9) 自乗の総和は別途公式があるので求めてみます。n = 4 までを計算してみると...
36. 問6: 自乗の合計の差 = 1 + (2 + 2) + (3 + 3 + 3) + (4 + 4 + 4 + 4) = 4 + (4 + 3) + (4 + 3 + 2) + (4 + 3 + 2 + 1) = 4 + (3 + 4) + (2 + 3 + 4) + (1 + 2 + 3 + 4) 12 + 22 + 32 + 42 9 + (9 + 9) + (9 + 9 + 9) + (9 + 9 + 9 + 9) 自乗の総和は別途公式があるので求めてみます。n = 4 までを計算してみると...
37. 問6: 自乗の合計の差 = 1 + (2 + 2) + (3 + 3 + 3) + (4 + 4 + 4 + 4) = 4 + (4 + 3) + (4 + 3 + 2) + (4 + 3 + 2 + 1) = 4 + (3 + 4) + (2 + 3 + 4) + (1 + 2 + 3 + 4) 12 + 22 + 32 + 42 9 + (9 + 9) + (9 + 9 + 9) + (9 + 9 + 9 + 9) 自乗の総和は別途公式があるので求めてみます。n = 4 までを計算してみると...
38. 問6: 自乗の合計の差 = 1 + (2 + 2) + (3 + 3 + 3) + (4 + 4 + 4 + 4) = 4 + (4 + 3) + (4 + 3 + 2) + (4 + 3 + 2 + 1) = 4 + (3 + 4) + (2 + 3 + 4) + (1 + 2 + 3 + 4) 12 + 22 + 32 + 42 9 + (9 + 9) + (9 + 9 + 9) + (9 + 9 + 9 + 9) 自乗の総和は別途公式があるので求めてみます。n = 4 までを計算してみると...
39. 問6: 自乗の合計の差 = 1 + (2 + 2) + (3 + 3 + 3) + (4 + 4 + 4 + 4) = 4 + (4 + 3) + (4 + 3 + 2) + (4 + 3 + 2 + 1) = 4 + (3 + 4) + (2 + 3 + 4) + (1 + 2 + 3 + 4) 12 + 22 + 32 + 42 9 + (9 + 9) + (9 + 9 + 9) + (9 + 9 + 9 + 9) 自乗の総和は別途公式があるので求めてみます。n = 4 までを計算してみると...
40. 問6: 自乗の合計の差 = 1 + (2 + 2) + (3 + 3 + 3) + (4 + 4 + 4 + 4) = 4 + (4 + 3) + (4 + 3 + 2) + (4 + 3 + 2 + 1) = 4 + (3 + 4) + (2 + 3 + 4) + (1 + 2 + 3 + 4) 12 + 22 + 32 + 42 9 + (9 + 9) + (9 + 9 + 9) + (9 + 9 + 9 + 9) 自乗の総和は別途公式があるので求めてみます。n = 4 までを計算してみると...
41. 問6: 自乗の合計の差 = 1 + (2 + 2) + (3 + 3 + 3) + (4 + 4 + 4 + 4) = 4 + (4 + 3) + (4 + 3 + 2) + (4 + 3 + 2 + 1) = 4 + (3 + 4) + (2 + 3 + 4) + (1 + 2 + 3 + 4) 12 + 22 + 32 + 42 9 + (9 + 9) + (9 + 9 + 9) + (9 + 9 + 9 + 9) 2 · 4 + 1 = 9 自乗の総和は別途公式があるので求めてみます。n = 4 までを計算してみると...
42. 問6: 自乗の合計の差 = 1 + (2 + 2) + (3 + 3 + 3) + (4 + 4 + 4 + 4) = 4 + (4 + 3) + (4 + 3 + 2) + (4 + 3 + 2 + 1) = 4 + (3 + 4) + (2 + 3 + 4) + (1 + 2 + 3 + 4) 12 + 22 + 32 + 42 9 + (9 + 9) + (9 + 9 + 9) + (9 + 9 + 9 + 9) 1+2+3+4個(つまりn=4までの等差数列の和) 個 = 4(4 + 1) 2 = 10 自乗の総和は別途公式があるので求めてみます。n = 4 までを計算してみると...
43. 問6: 自乗の合計の差 とおくと、前頁の結果から S4 = 12 + 22 + 32 + 42 3S4 = (2 · 4 + 1) · 4(4 + 1) 2 となるのがわかります。
44. 問6: 自乗の合計の差 とおくと、前頁の結果から S4 = 12 + 22 + 32 + 42 3S4 = (2 · 4 + 1) · 4(4 + 1) 2 となるのがわかります。 この 4 を n に一般化してみると 3Sn = (2n + 1) · n(n + 1) 2 となります。
45. 問6: 自乗の合計の差 とおくと、前頁の結果から S4 = 12 + 22 + 32 + 42 3S4 = (2 · 4 + 1) · 4(4 + 1) 2 となるのがわかります。 この 4 を n に一般化してみると 3Sn = (2n + 1) · n(n + 1) 2 となります。整理すると Sn = n(n + 1)(2n + 1) 6
46. 問6: 自乗の合計の差 まとめると n X k=1 k2 = 12 + 22 + · · · + n2 = n(n + 1)(2n + 1) 6 n X k=1 k = 1 + 2 + · · · + n = n(n + 1) 2
47. 問6: 自乗の合計の差 まとめると n X k=1 k2 = 12 + 22 + · · · + n2 = n(n + 1)(2n + 1) 6 n X k=1 k = 1 + 2 + · · · + n = n(n + 1) 2 (1 + 2 + · · · + 100)2 = ✓ 100(100 + 1) 2 ◆2 12 + 22 + · · · + 1002 = 100(100 + 1)(2 · 100 + 1) 6
48. 自身のべき乗
49. 問48: 自身のべき乗 11 + 22 + 33 + · · · + 1010 = 10405071317 である。では以下の級数の下10桁を求めよ。 11 + 22 + 33 + · · · + 10001000
50. 問48: 自身のべき乗 いつものように n = 1000 における以下の数列の和を求 めてみる。 11 + 22 + 33 + · · · + nn
51. 問48: 自身のべき乗 いつものように n = 1000 における以下の数列の和を求 めてみる。 11 + 22 + 33 + · · · + nn
52. 問48: 自身のべき乗 •n = 1000 とかなると桁がものすごいことになる。 •C言語とかだと完全に桁あふれする。 •実際に n = 1000 の時を計算してみると...
53. 問48: 自身のべき乗 100036819914469517709537501122764679556779368062293465458376098810023491074771619438142865909952784594586994264319129089472034 297990640767964725986043423846803832604080969103761537037623771364851006311573295146177424670558426686575960181584366644283228 455688031311454815153919097539848549664557651346585858271233640116622195618817344953167410268890832176466302030669977040862534 076609159502279137936809836930637560281385664635877375155877521346022579657984658333400734935862434233933298133457123788880928 310334876026136017595081560917946402687100524365210998086355214201424290343406856093657323107934219403186441391810123815105650 926739351576039284247250139159407346300152184381107376702171102630750469573346789782186690664846982834660741296739580179779168 360983472243224195284535256468186824036956956619282555532355807806199752768998384886337478678933158156525205917261433942460098 614325923316758337107036262555453185205416611714885822950858158961433759446327755438051838092130121883632710223140733220110974 010258021646929833176692061964608379073280762736061442808517156500628972850868896422679964719258292405858953075067457838536556 187855958968575622569234891474692281091391561983475411764835803581412867029415856566994208773628639094224154722601500447133063 011307204270428890504214262819377191859457430220214720118848634591319083375230747696601054742392887106311878302603638131903905 200825207205793366671291894623331279369709407422418787204597097644430924278218773832025749008082433007499169869823956112581112 760786390035522173784669056770734407449414526666210383981284021630344847691395707235573271662709837224522304679291974725911315 742582406485833141540094327821304295463505357404520998451222126424190355017841682455141254863759000777908253928824775165356689 988274959440589510258798553952770949351004954644542726561747839910718823868177121590423411939224748975107908594805594509880561 796372292846955426378221762516042800822884555254034449486019526711518709222776619575390721112664615014061474423397476527347561 996431185285861416781966834012473048771016200679352998575882065367727437956331349545452663271872348233949482575982107640169431 604345651211793793545646352146302119772669498355892913235757618859497751663073421286386945616420552553676731129813718251149464 946366307375921921305682356166777609373942574288393071260996216346408803882656913203216069263720618308594298797368458427649178 484311547207790040169259569411927355351102599126544603936628892174358133320008371710524117150460688354341886202404755217705526 342446950129890590193815824593863369410502481516667981368915666834119771347509438990488712679446890189385047505001120522574245 555562575056021323038791033798395033324502065323898911550701388295627776388079568721085719649389314265671310596627542214460598 805893960060360422692140140209651929425048867029798339635327946045314237554226788198919748178978067895509376319365860369089847 4826976906544473978017455720367929981796023041785852626797271283465789498383642350667978127819110846700 •n = 1000 とかなると桁がものすごいことになる。 •C言語とかだと完全に桁あふれする。 •実際に n = 1000 の時を計算してみると...
54. 問48: 自身のべき乗 mod
55. 問48: 自身のべき乗 5 1 ⌘ 5(mod9)
56. 問48: 自身のべき乗 5 1 ⌘ 5(mod9) 5 2 ⌘ 5 1 · 5 = 5 · 5 = 25 ⌘ 7(mod9)
57. 問48: 自身のべき乗 5 1 ⌘ 5(mod9) 5 2 ⌘ 5 1 · 5 = 5 · 5 = 25 ⌘ 7(mod9) 5 3 ⌘ 5 2 · 5 = 7 · 5 = 35 ⌘ 8(mod9)
58. 問48: 自身のべき乗 5 1 ⌘ 5(mod9) 5 2 ⌘ 5 1 · 5 = 5 · 5 = 25 ⌘ 7(mod9) 5 3 ⌘ 5 2 · 5 = 7 · 5 = 35 ⌘ 8(mod9) 5 4 ⌘ 5 3 · 5 = 8 · 5 = 40 ⌘ 4(mod9)
59. 問48: 自身のべき乗 5 1 ⌘ 5(mod9) 5 2 ⌘ 5 1 · 5 = 5 · 5 = 25 ⌘ 7(mod9) 5 3 ⌘ 5 2 · 5 = 7 · 5 = 35 ⌘ 8(mod9) 5 4 ⌘ 5 3 · 5 = 8 · 5 = 40 ⌘ 4(mod9) 5 5 ⌘ 5 4 · 5 = 4 · 5 = 20 ⌘ 2(mod9)
60. 問48: 自身のべき乗 下10桁を求めればよいので の世界で計算して いけばOK。最大でも 未満の数にし かならない。 mod10 10 1010 = 10000000000
61. 偶数の フィボナッチ数
62. 問2: 偶数のフィボナッチ数 フィボナッチ数列の各項は前の2つの項から生成され る。最初の項が1, 2から始まるとすると、最初の10項は 以下のようになる。 1,2,3,5,8,13,21,34,55,89 400万を超えないフィボナッチ数列を考える時、偶数値 の合計を求めよ。
63. 問2: 偶数のフィボナッチ数 フィボナッチ数列の一般項を求めてみます。 一般に、前の項によって次の項の値が決まるものを漸化 式、特にフィボナッチ数列のように前の2つの項によっ て次の項の値が決まるものを三項間漸化式といいます ね。
64. 問2: 偶数のフィボナッチ数 漸化式の解き方は •特性方程式を解く •行列を使って解く の2種類がありますが、行列を使った解き方の方が面白 いのでそちらの方法で求めてみます。
65. 問2: 偶数のフィボナッチ数 まず、フィボナッチ数列は以下のように表せますね。 F0 = 0, F1 = 1 ※問題文では初項が 1, 2 になっていますが 0, 1 の方が計算しやすいのでこうします。 Fn = Fn 2 + Fn 1(n > 1)
66. ✓ F1 F2 ◆ = ✓ 0 1 1 1 ◆ ✓ F0 F1 ◆ = ✓ F1 F0 + F1 ◆ 問2: 偶数のフィボナッチ数 行列を使っても表せます。 F0 = 0, F1 = 1
67. ✓ F1 F2 ◆ = ✓ 0 1 1 1 ◆ ✓ F0 F1 ◆ = ✓ F1 F0 + F1 ◆ F0 = 0, F1 = 1 問2: 偶数のフィボナッチ数 行列を使っても表せます。
68. ✓ F1 F2 ◆ = ✓ 0 1 1 1 ◆ ✓ F0 F1 ◆ = ✓ F1 F0 + F1 ◆ F0 = 0, F1 = 1 問2: 偶数のフィボナッチ数 行列を使っても表せます。 ✓ F2 F3 ◆ = ✓ 0 1 1 1 ◆ ✓ F1 F2 ◆ = ✓ 0 1 1 1 ◆ ✓ 0 1 1 1 ◆ ✓ F0 F1 ◆
69. ✓ F1 F2 ◆ = ✓ 0 1 1 1 ◆ ✓ F0 F1 ◆ = ✓ F1 F0 + F1 ◆ F0 = 0, F1 = 1 問2: 偶数のフィボナッチ数 行列を使っても表せます。 ✓ F2 F3 ◆ = ✓ 0 1 1 1 ◆ ✓ F1 F2 ◆ = ✓ 0 1 1 1 ◆ ✓ 0 1 1 1 ◆ ✓ F0 F1 ◆
70. ✓ F1 F2 ◆ = ✓ 0 1 1 1 ◆ ✓ F0 F1 ◆ = ✓ F1 F0 + F1 ◆ F0 = 0, F1 = 1 問2: 偶数のフィボナッチ数 行列を使っても表せます。 ✓ F2 F3 ◆ = ✓ 0 1 1 1 ◆ ✓ F1 F2 ◆ = ✓ 0 1 1 1 ◆ ✓ 0 1 1 1 ◆ ✓ F0 F1 ◆
71. ✓ F1 F2 ◆ = ✓ 0 1 1 1 ◆ ✓ F0 F1 ◆ = ✓ F1 F0 + F1 ◆ F0 = 0, F1 = 1 問2: 偶数のフィボナッチ数 行列を使っても表せます。 ✓ F2 F3 ◆ = ✓ 0 1 1 1 ◆ ✓ F1 F2 ◆ = ✓ 0 1 1 1 ◆ ✓ 0 1 1 1 ◆ ✓ F0 F1 ◆ = ✓ 0 1 1 1 ◆2 ✓ F0 F1 ◆
72. 問2: 偶数のフィボナッチ数 一般化してみると という風に表すことができます。 F0 = 0, F1 = 1 ✓ Fn Fn+1 ◆ = ✓ 0 1 1 1 ◆n ✓ F0 F1 ◆
73. 問2: 偶数のフィボナッチ数 一般化してみると という風に表すことができます。 F0 = 0, F1 = 1 ✓ Fn Fn+1 ◆ = ✓ 0 1 1 1 ◆n ✓ F0 F1 ◆ A = ✓ 0 1 1 1 ◆ と置くと を求めることができれば Fn を計算できそう。 An
74. 問2: 偶数のフィボナッチ数 単純に を求めると n が大きくなった時にかなり大変 なので、ちょっと工夫します。 An
75. 問2: 偶数のフィボナッチ数 対角行列のべき乗は簡単に求めることができますね。 ⇤ = 0 B B B @ 1 0 . . . 0 0 2 . . . 0 . . . . . . ... . . . 0 0 . . . m 1 C C C A こういう対角行列Λが あるとすると...
76. 問2: 偶数のフィボナッチ数 対角行列のべき乗は簡単に求めることができますね。 ⇤ = 0 B B B @ 1 0 . . . 0 0 2 . . . 0 . . . . . . ... . . . 0 0 . . . m 1 C C C A ⇤n = 0 B B B @ n 1 0 . . . 0 0 n 2 . . . 0 . . . . . . ... . . . 0 0 . . . n m 1 C C C A こういう対角行列Λが あるとすると... Λのn乗はこうなる
77. 問2: 偶数のフィボナッチ数 ここで を行列の掛け算で表してみます。 A = P⇤P 1 A = ✓ 0 1 1 1 ◆ ⇤ ( は対角行列)
78. 問2: 偶数のフィボナッチ数 この行列 A の n 乗を計算してみると An = (P⇤P 1)n = P⇤P 1P⇤P 1 · · · P⇤P 1 = P⇤nP 1 ここで を行列の掛け算で表してみます。 A = P⇤P 1 A = ✓ 0 1 1 1 ◆ ⇤ ( は対角行列)
79. 問2: 偶数のフィボナッチ数 この行列 A の n 乗を計算してみると An = (P⇤P 1)n = P⇤P 1P⇤P 1 · · · P⇤P 1 = P⇤nP 1 ここで を行列の掛け算で表してみます。 A = P⇤P 1 A = ✓ 0 1 1 1 ◆ ⇤ ( は対角行列)
80. 問2: 偶数のフィボナッチ数 この行列 A の n 乗を計算してみると An = (P⇤P 1)n = P⇤P 1P⇤P 1 · · · P⇤P 1 = P⇤nP 1 ここで を行列の掛け算で表してみます。 A = P⇤P 1 A = ✓ 0 1 1 1 ◆ ⇤ ( は対角行列)
81. 問2: 偶数のフィボナッチ数 この行列 A の n 乗を計算してみると An = (P⇤P 1)n = P⇤P 1P⇤P 1 · · · P⇤P 1 = P⇤nP 1 ここで を行列の掛け算で表してみます。 A = P⇤P 1 A = ✓ 0 1 1 1 ◆ ⇤ ( は対角行列) となるのでべき乗の計算が簡単になります。問題はどう やってこの都合の良い行列を見つけるか？
82. 問2: 偶数のフィボナッチ数 P = ✓ p11 p21 p12 p22 ◆ = (p1, p2) とりあえず行列 を列ベクトルの集まりとしてみます。 P
83. 問2: 偶数のフィボナッチ数 A = P⇤P 1 の両辺の右側に をかけてみると P AP = P⇤ P = ✓ p11 p21 p12 p22 ◆ = (p1, p2) とりあえず行列 を列ベクトルの集まりとしてみます。 P となる。
84. 問2: 偶数のフィボナッチ数 A = P⇤P 1 の両辺の右側に をかけてみると P AP = P⇤ P = ✓ p11 p21 p12 p22 ◆ = (p1, p2) とりあえず行列 を列ベクトルの集まりとしてみます。 P A(p1, p2) = (p1, p2)⇤ となる。 を代入すると P となります。
85. 問2: 偶数のフィボナッチ数 A(p1, p2) = (p1, p2)⇤ なので は ⇤ = ✓ 1 0 0 2 ◆ (Ap1, Ap2) = (p1, p2) ✓ 1 0 0 2 ◆ = ( 1p1, 2p2) と表せます。
86. 問2: 偶数のフィボナッチ数 A(p1, p2) = (p1, p2)⇤ なので は ⇤ = ✓ 1 0 0 2 ◆ (Ap1, Ap2) = (p1, p2) ✓ 1 0 0 2 ◆ = ( 1p1, 2p2) と表せます。よって Ap1 = 1p1 Ap2 = 2p2 ということですね。
87. 問2: 偶数のフィボナッチ数 Ap1 = 1p1 Ap2 = 2p2 これは要するに と が の固有ベクトルということ。 A p1 p2 A = P⇤P 1 の は の固有ベクトルを並べた行列だと いうことがわかりました！ A P そして対角行列 の対角要素は の固有値です！ ⇤ A
88. 問2: 偶数のフィボナッチ数 では の固有値と固有ベクトルを求めてみます。固有値は 以下の特性多項式を解くことで求められましたね。 A det( I A) = 0
89. 問2: 偶数のフィボナッチ数 A det( I A) = 0 det( I A) = det ✓✓ 0 0 ◆ ✓ 0 1 1 1 ◆◆ では の固有値と固有ベクトルを求めてみます。固有値は 以下の特性多項式を解くことで求められましたね。
90. 問2: 偶数のフィボナッチ数 A det( I A) = 0 det( I A) = det ✓✓ 0 0 ◆ ✓ 0 1 1 1 ◆◆ = det ✓ 1 1 1 ◆ では の固有値と固有ベクトルを求めてみます。固有値は 以下の特性多項式を解くことで求められましたね。
91. 問2: 偶数のフィボナッチ数 A det( I A) = 0 det( I A) = det ✓✓ 0 0 ◆ ✓ 0 1 1 1 ◆◆ = det ✓ 1 1 1 ◆ = · ( 1) ( 1) · ( 1) では の固有値と固有ベクトルを求めてみます。固有値は 以下の特性多項式を解くことで求められましたね。
92. 問2: 偶数のフィボナッチ数 A det( I A) = 0 det( I A) = det ✓✓ 0 0 ◆ ✓ 0 1 1 1 ◆◆ = det ✓ 1 1 1 ◆ = · ( 1) ( 1) · ( 1) では の固有値と固有ベクトルを求めてみます。固有値は 以下の特性多項式を解くことで求められましたね。
93. 問2: 偶数のフィボナッチ数 A det( I A) = 0 det( I A) = det ✓✓ 0 0 ◆ ✓ 0 1 1 1 ◆◆ = det ✓ 1 1 1 ◆ = · ( 1) ( 1) · ( 1) = 2 1 = 0 では の固有値と固有ベクトルを求めてみます。固有値は 以下の特性多項式を解くことで求められましたね。
94. 問2: 偶数のフィボナッチ数 あとは を解きましょう。二次方程式の解 2 1 = 0 の公式に当てはめるだけです。
95. 問2: 偶数のフィボナッチ数 あとは を解きましょう。二次方程式の解 2 1 = 0 の公式に当てはめるだけです。 ax 2 + bx + c = 0 x = b ± p b 2 4 ac 2 a の時 なので
96. 問2: 偶数のフィボナッチ数 あとは を解きましょう。二次方程式の解 2 1 = 0 の公式に当てはめるだけです。 ax 2 + bx + c = 0 x = b ± p b 2 4 ac 2 a の時 なので = ( 1) ± p ( 1)2 4 · 1 · ( 1) 2 · 1 = 1 ± p 5 2 固有値が求まりました！
97. 問2: 偶数のフィボナッチ数 1 = 1 + p 5 2 , 2 = 1 p 5 2 とおいて を解きましょう。 次は固有ベクトルを求めます。 Ap1 = 1p1 Ap2 = 2p2
98. 問2: 偶数のフィボナッチ数 ✓ 0 1 1 1 ◆ ✓ p11 p12 ◆ = ✓ p12 p11 + p12 ◆ = ✓ 1p11 1p12 ◆ なので という連立方程式を解きます。 p12 = 1p11 p11 + p12 = 1p12
99. 問2: 偶数のフィボナッチ数 ✓ 0 1 1 1 ◆ ✓ p11 p12 ◆ = ✓ p12 p11 + p12 ◆ = ✓ 1p11 1p12 ◆ なので という連立方程式を解きます。 とはいうものの既に で答えは出ています。 p12 = 1p11 p12 = 1p11 p11 + p12 = 1p12
100. 問2: 偶数のフィボナッチ数 ✓ 0 1 1 1 ◆ ✓ p11 p12 ◆ = ✓ p12 p11 + p12 ◆ = ✓ 1p11 1p12 ◆ なので という連立方程式を解きます。 とはいうものの既に で答えは出ています。 これは が決まれば自動的に も決まるということ。 p12 = 1p11 p11 p12 p12 = 1p11 p11 + p12 = 1p12
101. 問2: 偶数のフィボナッチ数 ✓ 0 1 1 1 ◆ ✓ p11 p12 ◆ = ✓ p12 p11 + p12 ◆ = ✓ 1p11 1p12 ◆ なので という連立方程式を解きます。 とはいうものの既に で答えは出ています。 これは が決まれば自動的に も決まるということ。 なので、これ全部固有ベクトルです。 p12 = 1p11 p11 p12 p12 = 1p11 p11 + p12 = 1p12 p1 = ✓ 1 1 ◆ , p1 = ✓ 3 3 1 ◆ , p1 = ✓ 999 999 1 ◆
102. 問2: 偶数のフィボナッチ数 2 の方の固有ベクトルも同じ理屈です。とはいえ、計算 は簡単な方がいいので、一番単純なものを固有ベクトル として選びます！ p1 = ✓ 1 1 ◆ , p2 = ✓ 1 2 ◆
103. 問2: 偶数のフィボナッチ数 最初に戻ります。フィボナッチ数列は以下のように表さ れるのでした。 ✓ Fn Fn+1 ◆ = ✓ 0 1 1 1 ◆n ✓ F0 F1 ◆
104. 問2: 偶数のフィボナッチ数 最初に戻ります。フィボナッチ数列は以下のように表さ れるのでした。 ✓ Fn Fn+1 ◆ = ✓ 0 1 1 1 ◆n ✓ F0 F1 ◆ An = (P⇤P 1)n = P⇤nP 1 = ✓ 1 1 1 2 ◆ ✓ n 1 0 0 n 2 ◆ 1 p 5 ✓ 2 1 1 1 ◆
105. 問2: 偶数のフィボナッチ数 最初に戻ります。フィボナッチ数列は以下のように表さ れるのでした。 ✓ Fn Fn+1 ◆ = ✓ 0 1 1 1 ◆n ✓ F0 F1 ◆ An = (P⇤P 1)n = P⇤nP 1 = ✓ 1 1 1 2 ◆ ✓ n 1 0 0 n 2 ◆ 1 p 5 ✓ 2 1 1 1 ◆ さっき求めた固有ベクトル
106. 問2: 偶数のフィボナッチ数 最初に戻ります。フィボナッチ数列は以下のように表さ れるのでした。 ✓ Fn Fn+1 ◆ = ✓ 0 1 1 1 ◆n ✓ F0 F1 ◆ An = (P⇤P 1)n = P⇤nP 1 = ✓ 1 1 1 2 ◆ ✓ n 1 0 0 n 2 ◆ 1 p 5 ✓ 2 1 1 1 ◆ さっき求めた固有ベクトル 逆行列。計算過程は省略...
107. 問2: 偶数のフィボナッチ数 最初に戻ります。フィボナッチ数列は以下のように表さ れるのでした。 ✓ Fn Fn+1 ◆ = ✓ 0 1 1 1 ◆n ✓ F0 F1 ◆ An = (P⇤P 1)n = P⇤nP 1 = ✓ 1 1 1 2 ◆ ✓ n 1 0 0 n 2 ◆ 1 p 5 ✓ 2 1 1 1 ◆ = 1 p 5 ✓ 1 n 2 n 1 2 n 1 n 2 1 n+1 2 n+1 1 2 n+1 1 n+1 2 ◆
108. 問2: 偶数のフィボナッチ数 ✓ Fn Fn+1 ◆ = 1 p 5 ✓ 1 n 2 n 1 2 n 1 n 2 1 n+1 2 n+1 1 2 n+1 1 n+1 2 ◆ ✓ F0 F1 ◆ = 1 p 5 ✓ 1 n 2 n 1 2 n 1 n 2 1 n+1 2 n+1 1 2 n+1 1 n+1 2 ◆ ✓ 0 1 ◆ となります。
109. 問2: 偶数のフィボナッチ数 ✓ Fn Fn+1 ◆ = 1 p 5 ✓ 1 n 2 n 1 2 n 1 n 2 1 n+1 2 n+1 1 2 n+1 1 n+1 2 ◆ ✓ F0 F1 ◆ = 1 p 5 ✓ 1 n 2 n 1 2 n 1 n 2 1 n+1 2 n+1 1 2 n+1 1 n+1 2 ◆ ✓ 0 1 ◆ となります。今は が欲しいので1行目だけ計算します。 Fn Fn = 1 p 5 (( 1 n 2 n 1 2) · 0 + ( n 1 n 2 ) · 1)
110. 問2: 偶数のフィボナッチ数 ✓ Fn Fn+1 ◆ = 1 p 5 ✓ 1 n 2 n 1 2 n 1 n 2 1 n+1 2 n+1 1 2 n+1 1 n+1 2 ◆ ✓ F0 F1 ◆ = 1 p 5 ✓ 1 n 2 n 1 2 n 1 n 2 1 n+1 2 n+1 1 2 n+1 1 n+1 2 ◆ ✓ 0 1 ◆ となります。今は が欲しいので1行目だけ計算します。 Fn = 1 p 5 ( n 1 n 2 ) = 1 p 5 ( 1 + p 5 2 !n 1 p 5 2 !n ) Fn = 1 p 5 (( 1 n 2 n 1 2) · 0 + ( n 1 n 2 ) · 1)
111. 問2: 偶数のフィボナッチ数 ✓ Fn Fn+1 ◆ = 1 p 5 ✓ 1 n 2 n 1 2 n 1 n 2 1 n+1 2 n+1 1 2 n+1 1 n+1 2 ◆ ✓ F0 F1 ◆ = 1 p 5 ✓ 1 n 2 n 1 2 n 1 n 2 1 n+1 2 n+1 1 2 n+1 1 n+1 2 ◆ ✓ 0 1 ◆ となります。今は が欲しいので1行目だけ計算します。 Fn = 1 p 5 ( n 1 n 2 ) = 1 p 5 ( 1 + p 5 2 !n 1 p 5 2 !n ) Fn = 1 p 5 (( 1 n 2 n 1 2) · 0 + ( n 1 n 2 ) · 1)
112. 問2: 偶数のフィボナッチ数 ということでフィボナッチ数列の一般項は Fn = 1 p 5 ( 1 + p 5 2 !n 1 p 5 2 !n ) という式だとわかりました！ F0 = 0, F1 = 1 初項を とした場合
113. 問2: 偶数のフィボナッチ数 ということでフィボナッチ数列の一般項は Fn = 1 p 5 ( 1 + p 5 2 !n 1 p 5 2 !n ) という式だとわかりました！ もう少し頑張ります！ F0 = 0, F1 = 1 初項を とした場合
114. 問2: 偶数のフィボナッチ数 問題文で400万を超えないフィボナッチ数とありましたが n がいくつで400万を超えるか計算してみます。 Fn = 1 p 5 ( 1 + p 5 2 !n 1 p 5 2 !n ) > 4000000
115. 問2: 偶数のフィボナッチ数 問題文で400万を超えないフィボナッチ数とありましたが n がいくつで400万を超えるか計算してみます。 Fn = 1 p 5 ( 1 + p 5 2 !n 1 p 5 2 !n ) > 4000000 ( 1 + p 5 2 !n 1 p 5 2 !n ) > 4000000 p 5
116. 問2: 偶数のフィボナッチ数 問題文で400万を超えないフィボナッチ数とありましたが n がいくつで400万を超えるか計算してみます。 Fn = 1 p 5 ( 1 + p 5 2 !n 1 p 5 2 !n ) > 4000000 ( 1 + p 5 2 !n 1 p 5 2 !n ) > 4000000 p 5 この両辺の対数をとってみます。
117. 問2: 偶数のフィボナッチ数 log ( 1 + p 5 2 !n 1 p 5 2 !n ) > log 4000000 p 5
118. 問2: 偶数のフィボナッチ数 この式の左辺の第二項は n が大きくなると 0 に近づくので 簡単のため無視します。 log ( 1 + p 5 2 !n 1 p 5 2 !n ) > log 4000000 p 5
119. 問2: 偶数のフィボナッチ数 この式の左辺の第二項は n が大きくなると 0 に近づくので 簡単のため無視します。 log ( 1 + p 5 2 !n 1 p 5 2 !n ) > log 4000000 p 5 log 1 + p 5 2 !n > log 4000000 p 5
120. 問2: 偶数のフィボナッチ数 この式の左辺の第二項は n が大きくなると 0 に近づくので 簡単のため無視します。 log ( 1 + p 5 2 !n 1 p 5 2 !n ) > log 4000000 p 5 log 1 + p 5 2 !n > log 4000000 p 5 n log 1 + p 5 2 ! > log 4000000 p 5
121. 問2: 偶数のフィボナッチ数 では両辺の対数を実際に計算してみます。 = 0.6020 + 6 + 0.3495 = 6.9515 log 4000000 p 5 = log 2 2 · 10 6 · 5 1 2 = 2 log 2 + 6 log 10 + 0 . 5 log 5 = 2 · 0.301 + 6 · 1 + 0.5 · 0.699 log 1 + p 5 2 ! = log ✓ 1 + 2 . 236 2 ◆ = log ✓ 3 . 236 2 ◆ = log 1 . 618 = 0.2068
122. 問2: 偶数のフィボナッチ数 では両辺の対数を実際に計算してみます。 = 0.6020 + 6 + 0.3495 = 6.9515 log 4000000 p 5 = log 2 2 · 10 6 · 5 1 2 = 2 log 2 + 6 log 10 + 0 . 5 log 5 = 2 · 0.301 + 6 · 1 + 0.5 · 0.699 log 1 + p 5 2 ! = log ✓ 1 + 2 . 236 2 ◆ = log ✓ 3 . 236 2 ◆ = log 1 . 618 = 0.2068
123. 問2: 偶数のフィボナッチ数 では両辺の対数を実際に計算してみます。 = 0.6020 + 6 + 0.3495 = 6.9515 log 4000000 p 5 = log 2 2 · 10 6 · 5 1 2 = 2 log 2 + 6 log 10 + 0 . 5 log 5 = 2 · 0.301 + 6 · 1 + 0.5 · 0.699 log 1 + p 5 2 ! = log ✓ 1 + 2 . 236 2 ◆ = log ✓ 3 . 236 2 ◆ = log 1 . 618 = 0.2068
124. 問2: 偶数のフィボナッチ数 では両辺の対数を実際に計算してみます。 = 0.6020 + 6 + 0.3495 = 6.9515 log 4000000 p 5 = log 2 2 · 10 6 · 5 1 2 = 2 log 2 + 6 log 10 + 0 . 5 log 5 = 2 · 0.301 + 6 · 1 + 0.5 · 0.699 log 1 + p 5 2 ! = log ✓ 1 + 2 . 236 2 ◆ = log ✓ 3 . 236 2 ◆ = log 1 . 618 = 0.2068
125. 問2: 偶数のフィボナッチ数 では両辺の対数を実際に計算してみます。 = 0.6020 + 6 + 0.3495 = 6.9515 log 4000000 p 5 = log 2 2 · 10 6 · 5 1 2 = 2 log 2 + 6 log 10 + 0 . 5 log 5 = 2 · 0.301 + 6 · 1 + 0.5 · 0.699 log 1 + p 5 2 ! = log ✓ 1 + 2 . 236 2 ◆ = log ✓ 3 . 236 2 ◆ = log 1 . 618 = 0.2068
126. 問2: 偶数のフィボナッチ数 では両辺の対数を実際に計算してみます。 = 0.6020 + 6 + 0.3495 = 6.9515 log 4000000 p 5 = log 2 2 · 10 6 · 5 1 2 = 2 log 2 + 6 log 10 + 0 . 5 log 5 = 2 · 0.301 + 6 · 1 + 0.5 · 0.699 log 1 + p 5 2 ! = log ✓ 1 + 2 . 236 2 ◆ = log ✓ 3 . 236 2 ◆ = log 1 . 618 = 0.2068
127. 問2: 偶数のフィボナッチ数 では両辺の対数を実際に計算してみます。 = 0.6020 + 6 + 0.3495 = 6.9515 log 4000000 p 5 = log 2 2 · 10 6 · 5 1 2 = 2 log 2 + 6 log 10 + 0 . 5 log 5 = 2 · 0.301 + 6 · 1 + 0.5 · 0.699 log 1 + p 5 2 ! = log ✓ 1 + 2 . 236 2 ◆ = log ✓ 3 . 236 2 ◆ = log 1 . 618 = 0.2068
128. 問2: 偶数のフィボナッチ数 では両辺の対数を実際に計算してみます。 = 0.6020 + 6 + 0.3495 = 6.9515 log 4000000 p 5 = log 2 2 · 10 6 · 5 1 2 = 2 log 2 + 6 log 10 + 0 . 5 log 5 = 2 · 0.301 + 6 · 1 + 0.5 · 0.699 log 1 + p 5 2 ! = log ✓ 1 + 2 . 236 2 ◆ = log ✓ 3 . 236 2 ◆ = log 1 . 618 = 0.2068
129. 問2: 偶数のフィボナッチ数 よって 4000000 より大きい n は n log 1 + p 5 2 ! > log 4000000 p 5 0.2068n > 6.9515 n > 33.2607 · · ·
130. 問2: 偶数のフィボナッチ数 よって 4000000 より大きい n は n log 1 + p 5 2 ! > log 4000000 p 5 0.2068n > 6.9515 n > 33.2607 · · · n は整数なので が 4000000 を超えない最大のフィボ ナッチ数。(n が 0 から始まる場合) F33
131. 問2: 偶数のフィボナッチ数 までの偶数の和を考えてみます。数列を眺めてると F33 F0 = 0 F1 = 1 F2 = 1 F3 = 2 F4 = 3 F5 = 5 F6 = 8 F7 = 13 F8 = 21 F9 = 34
132. 問2: 偶数のフィボナッチ数 までの偶数の和を考えてみます。数列を眺めてると F33 F0 = 0 F1 = 1 F2 = 1 F3 = 2 F4 = 3 F5 = 5 F6 = 8 F7 = 13 F8 = 21 F9 = 34 偶数 偶数 偶数
133. 問2: 偶数のフィボナッチ数 までの偶数の和を考えてみます。数列を眺めてると どうも n が 3 の倍数の時が偶数っぽい。 F33 F0 = 0 F1 = 1 F2 = 1 F3 = 2 F4 = 3 F5 = 5 F6 = 8 F7 = 13 F8 = 21 F9 = 34 偶数 偶数 偶数
134. 問2: 偶数のフィボナッチ数 Fn = 1 p 5 ( 1 + p 5 2 !n 1 p 5 2 !n ) 今 ですが、 長ったらしいので、以下のように置き換えます。 = 1 + p 5 2 , ˆ = 1 p 5 2 ※ちなみに っていうの 　は黄金比としてよく知ら 　れてますね。
135. 問2: 偶数のフィボナッチ数 Fn = 1 p 5 ( 1 + p 5 2 !n 1 p 5 2 !n ) 今 ですが、 長ったらしいので、以下のように置き換えます。 すると以下のように表せます。 = 1 + p 5 2 , ˆ = 1 p 5 2 ※ちなみに っていうの 　は黄金比としてよく知ら 　れてますね。 Fn = n ˆn p 5
136. 問2: 偶数のフィボナッチ数 n が 3 の倍数のフィボナッチ数列の和を考えてみると F3 + F6 + · · · + F30 + F33 = 11 X k=1 F3k
137. 問2: 偶数のフィボナッチ数 n が 3 の倍数のフィボナッチ数列の和を考えてみると これに一般項を代入してみると F3 + F6 + · · · + F30 + F33 = 11 X k=1 F3k 11 X k=1 F3k = 11 X k=1 3k ˆ3k p 5 = 1 p 5 11 X k=1 3k 11 X k=1 ˆ3k !
138. 問2: 偶数のフィボナッチ数 n が 3 の倍数のフィボナッチ数列の和を考えてみると なんかこれ、等比級数っぽくないですか？ これに一般項を代入してみると F3 + F6 + · · · + F30 + F33 = 11 X k=1 F3k 11 X k=1 F3k = 11 X k=1 3k ˆ3k p 5 = 1 p 5 11 X k=1 3k 11 X k=1 ˆ3k !
139. 問2: 偶数のフィボナッチ数 等比級数にはこういう公式がありますよね。 これを代入してみましょう。 n X k=1 ark 1 = a(rn 1) r 1
140. 問2: 偶数のフィボナッチ数 ※ とするとこうなります。 の場合も同じ。 等比級数にはこういう公式がありますよね。 これを代入してみましょう。 n X k=1 ark 1 = a(rn 1) r 1 a = 3, r = 3 ˆ 11 X k=1 F3k = 1 p 5 3(( 3)11 1) 3 1 ˆ3((ˆ3)11 1) ˆ3 1 !
141. 問2: 偶数のフィボナッチ数 ※ とするとこうなります。 の場合も同じ。 ここで、カッコの中の分数の式をまとめたい衝動に駆られ ます。でも分母の値が違うのでまとめれない・・・ 等比級数にはこういう公式がありますよね。 これを代入してみましょう。 n X k=1 ark 1 = a(rn 1) r 1 a = 3, r = 3 ˆ 11 X k=1 F3k = 1 p 5 3(( 3)11 1) 3 1 ˆ3((ˆ3)11 1) ˆ3 1 !
142. 問2: 偶数のフィボナッチ数 さて、ここで は の解でしたよねー？ 固有値を求めるとこでやりました。と、いうことは , ˆ x 2 x 1 = 0 2 1 = 0
143. 問2: 偶数のフィボナッチ数 , ˆ x 2 x 1 = 0 2 1 = 0 2 = + 1 この式から以下の式が導かれます。 さて、ここで は の解でしたよねー？ 固有値を求めるとこでやりました。と、いうことは
144. 問2: 偶数のフィボナッチ数 , ˆ x 2 x 1 = 0 2 1 = 0 2 = + 1 3 = 2 + = + 1 + = 2 + 1 この式から以下の式が導かれます。 さて、ここで は の解でしたよねー？ 固有値を求めるとこでやりました。と、いうことは
145. 問2: 偶数のフィボナッチ数 , ˆ x 2 x 1 = 0 2 1 = 0 2 = + 1 3 = 2 + = + 1 + = 2 + 1 この式から以下の式が導かれます。 さて、ここで は の解でしたよねー？ 固有値を求めるとこでやりました。と、いうことは
146. 問2: 偶数のフィボナッチ数 , ˆ x 2 x 1 = 0 2 1 = 0 2 = + 1 3 = 2 + = + 1 + = 2 + 1 この式から以下の式が導かれます。 つまりこういうことです。 3 1 = 2 ※ も同じ理屈です。 ˆ さて、ここで は の解でしたよねー？ 固有値を求めるとこでやりました。と、いうことは
147. 問2: 偶数のフィボナッチ数 11 X k=1 F3k = 1 p 5 3( 33 1) 2 ˆ3(ˆ33 1) 2ˆ ! = 1 2 · 1 p 5 ⇣ 2( 33 1) ˆ2(ˆ33 1) ⌘ = 1 2 · 2( 33 1) ˆ2(ˆ33 1) p 5 = 1 2 · 35 2 ˆ35 + ˆ2 p 5 = 1 2 35 ˆ35 p 5 2 ˆ2 p 5 !
148. 問2: 偶数のフィボナッチ数 11 X k=1 F3k = 1 p 5 3( 33 1) 2 ˆ3(ˆ33 1) 2ˆ ! = 1 2 · 1 p 5 ⇣ 2( 33 1) ˆ2(ˆ33 1) ⌘ = 1 2 · 2( 33 1) ˆ2(ˆ33 1) p 5 = 1 2 · 35 2 ˆ35 + ˆ2 p 5 = 1 2 35 ˆ35 p 5 2 ˆ2 p 5 !
149. 問2: 偶数のフィボナッチ数 11 X k=1 F3k = 1 p 5 3( 33 1) 2 ˆ3(ˆ33 1) 2ˆ ! = 1 2 · 1 p 5 ⇣ 2( 33 1) ˆ2(ˆ33 1) ⌘ = 1 2 · 2( 33 1) ˆ2(ˆ33 1) p 5 = 1 2 · 35 2 ˆ35 + ˆ2 p 5 = 1 2 35 ˆ35 p 5 2 ˆ2 p 5 !
150. 問2: 偶数のフィボナッチ数 11 X k=1 F3k = 1 p 5 3( 33 1) 2 ˆ3(ˆ33 1) 2ˆ ! = 1 2 · 1 p 5 ⇣ 2( 33 1) ˆ2(ˆ33 1) ⌘ = 1 2 · 2( 33 1) ˆ2(ˆ33 1) p 5 = 1 2 · 35 2 ˆ35 + ˆ2 p 5 = 1 2 35 ˆ35 p 5 2 ˆ2 p 5 !
151. 問2: 偶数のフィボナッチ数 11 X k=1 F3k = 1 p 5 3( 33 1) 2 ˆ3(ˆ33 1) 2ˆ ! = 1 2 · 1 p 5 ⇣ 2( 33 1) ˆ2(ˆ33 1) ⌘ = 1 2 · 2( 33 1) ˆ2(ˆ33 1) p 5 = 1 2 · 35 2 ˆ35 + ˆ2 p 5 = 1 2 35 ˆ35 p 5 2 ˆ2 p 5 !
152. 問2: 偶数のフィボナッチ数 答えが見えてきました。この式、わかりますか？ 1 2 35 ˆ35 p 5 2 ˆ2 p 5 !
153. 問2: 偶数のフィボナッチ数 答えが見えてきました。この式、わかりますか？ ↓ ↓ 1 2 35 ˆ35 p 5 2 ˆ2 p 5 ! F35 F2
154. 問2: 偶数のフィボナッチ数 答えが見えてきました。この式、わかりますか？ ↓ ↓ 1 2 35 ˆ35 p 5 2 ˆ2 p 5 ! F35 F2 11 X k=1 F3k = 1 2 (F35 F2) つまり 4000000 を超えないフィボナッチ数の偶数項の和 はこうなります。
155. 問2: 偶数のフィボナッチ数 お疲れ様でした
156. 問2: 偶数のフィボナッチ数 おまけ F35 = 35 ˆ 35 p 5 = 1 p 5 8 < : 1 + p 5 2 !35 1 p 5 2 !35 9 = ;
157. 問2: 偶数のフィボナッチ数 おまけ F35 = 35 ˆ 35 p 5 = 1 p 5 8 < : 1 + p 5 2 !35 1 p 5 2 !35 9 = ; (1 + p 5)35 = 35C0135 p 5 0 + 35C1134 p 5 1 + · · · + 35C3411 p 5 34 + 35C3510 p 5 35
158. 問2: 偶数のフィボナッチ数 おまけ F35 = 35 ˆ 35 p 5 = 1 p 5 8 < : 1 + p 5 2 !35 1 p 5 2 !35 9 = ; (1 + p 5)35 = 35C0135 p 5 0 + 35C1134 p 5 1 + · · · + 35C3411 p 5 34 + 35C3510 p 5 35 = 35C0 + · · · + 35C34517 +35C35517 p 5 +35C150 p 5
159. 問2: 偶数のフィボナッチ数 おまけ F35 = 35 ˆ 35 p 5 = 1 p 5 8 < : 1 + p 5 2 !35 1 p 5 2 !35 9 = ; (1 + p 5)35 = 35C0135 p 5 0 + 35C1134 p 5 1 + · · · + 35C3411 p 5 34 + 35C3510 p 5 35 = 35C0 + · · · + 35C34517 +35C35517 p 5 +35C150 p 5 = (35C050 + 35C251 + · · · + 35C32516 + 35C34517) + p 5(· · · ) 整数部 無理数部
160. 問2: 偶数のフィボナッチ数 おまけ F35 = 35 ˆ 35 p 5 = 1 p 5 8 < : 1 + p 5 2 !35 1 p 5 2 !35 9 = ; (1 + p 5)35 = 35C0135 p 5 0 + 35C1134 p 5 1 + · · · + 35C3411 p 5 34 + 35C3510 p 5 35 = 35C0 + · · · + 35C34517 +35C35517 p 5 +35C150 p 5 = (35C050 + 35C251 + · · · + 35C32516 + 35C34517) + p 5(· · · ) (1 p 5)35 = (35C050 + 35C251 + · · · + 35C32516 + 35C34517) p 5(· · · ) 整数部 無理数部 整数部 無理数部
161. 問2: 偶数のフィボナッチ数 おまけ F35 = 35 ˆ 35 p 5 = 1 p 5 8 < : 1 + p 5 2 !35 1 p 5 2 !35 9 = ; (1 + p 5)35 = 35C0135 p 5 0 + 35C1134 p 5 1 + · · · + 35C3411 p 5 34 + 35C3510 p 5 35 = 35C0 + · · · + 35C34517 +35C35517 p 5 +35C150 p 5 = (35C050 + 35C251 + · · · + 35C32516 + 35C34517) + p 5(· · · ) (1 p 5)35 = (35C050 + 35C251 + · · · + 35C32516 + 35C34517) p 5(· · · ) 整数部 無理数部 整数部 無理数部
162. 問2: 偶数のフィボナッチ数 おまけ F35 = 35 ˆ 35 p 5 = 1 p 5 8 < : 1 + p 5 2 !35 1 p 5 2 !35 9 = ; (1 + p 5)35 = 35C0135 p 5 0 + 35C1134 p 5 1 + · · · + 35C3411 p 5 34 + 35C3510 p 5 35 = 35C0 + · · · + 35C34517 +35C35517 p 5 +35C150 p 5 = (35C050 + 35C251 + · · · + 35C32516 + 35C34517) + p 5(· · · ) (1 p 5)35 = (35C050 + 35C251 + · · · + 35C32516 + 35C34517) p 5(· · · ) 整数部 無理数部 整数部 無理数部 (1 + p 5)35 (1 p 5)35 = 2 p 5(· · · )
163. 問2: 偶数のフィボナッチ数 おまけ F35 = 35 ˆ 35 p 5 = 1 p 5 8 < : 1 + p 5 2 !35 1 p 5 2 !35 9 = ; (1 + p 5)35 = 35C0135 p 5 0 + 35C1134 p 5 1 + · · · + 35C3411 p 5 34 + 35C3510 p 5 35 = 35C0 + · · · + 35C34517 +35C35517 p 5 +35C150 p 5 = (35C050 + 35C251 + · · · + 35C32516 + 35C34517) + p 5(· · · ) (1 p 5)35 = (35C050 + 35C251 + · · · + 35C32516 + 35C34517) p 5(· · · ) 整数部 無理数部 整数部 無理数部 (1 + p 5)35 (1 p 5)35 = 2 p 5(· · · )
164. 問2: 偶数のフィボナッチ数 おまけ F35 = 35 ˆ 35 p 5 = 1 p 5 8 < : 1 + p 5 2 !35 1 p 5 2 !35 9 = ; (1 + p 5)35 = 35C0135 p 5 0 + 35C1134 p 5 1 + · · · + 35C3411 p 5 34 + 35C3510 p 5 35 = 35C0 + · · · + 35C34517 +35C35517 p 5 +35C150 p 5 = (35C050 + 35C251 + · · · + 35C32516 + 35C34517) + p 5(· · · ) (1 p 5)35 = (35C050 + 35C251 + · · · + 35C32516 + 35C34517) p 5(· · · ) 整数部 無理数部 整数部 無理数部 (1 + p 5)35 (1 p 5)35 = 2 p 5(· · · )
165. 数学とプログラミングの 世界を楽しもう おわり