の呟きは 36
対面がラス回避したかったのか３確しやがった・・・
https://tenhou.net/0/?log=2023121823gm-0009-0000-5375f803&tw=0
https://projecteuler.net/problem=853
フィボナッチ数列の各値のnで割った余りの数列は周期的に循環する？
その循環の周期をピサノ周期（？）でπ(n)で表すと？
π(n)=18となる、つまり周期が１８個になるnは、19と38と76？、これらのうち50未満のnを和すると19+38=57になると？
お題は、π(n)=120、つまり周期が120個になるnのうち10^9未満のnの和を求めろ・・・と？- (UPD ) #
フィボナッチは漸化式（？）が
F(0) = 1
F(1) = 1
F(x | x>=2) = F(x-1) + F(x-2)
だよな？おそらく（F(0)=0,F(1)=1としても変わらんか？わからん・・・？- (UPD ) #
問題文の雰囲気を定式化（？）すると
sum n
| n < 10^9
| F(x) ≡ F(x + π(n)) (mod n) ∀x∈N
| F(x) mod n = F(x + π(n)) mod n ∀x∈N
| π(n) = 120
という感じ？（なんか違ってそう、合同式で表すのも違ってそう- (UPD ) #
ピサノ周期とやら
どこを区切りとして周期とみなすんだろう？
1 2 3 1 2 3 1 2 3と 出てきたら 1 2 3 を周期としてみなしていいのかというと
1 2 3 1 2 3 1 2 3 4 5 1 2 3 1 2 3 1 2 3 4 5 という罠サイクルかもしれんし
（実際に具体数字の1 2 3 という並びは発生せんだろうけど
周期的になっていると断定できる何かがあるはずなんだよな- (UPD ) #
あー、フィボナッチは漸化式で前後の要素の和で構成されているわけだから
F(x) mod n = *1 mod n なわけで
1 2 3 1 2 と出た時点で 1 2 3 の周期、と断定しちゃってもいいのかな？
わからん- (UPD ) #
ただ、飛んでる値だけを拾っての周期判定はできなさそうな
π(n) = 9を探せ！だからといって
* * * *
1 2 3 1 2 3 1 2 3 1 2 3
の9個飛んだ部分だけ拾って周期は9と判断しちゃったらヤバい、約数の周期の場合を見逃す・・・つか、そもそも
ここまでの考察はnを10^9まで全部列挙する前提になるし
それだと、実行時間、間に合わん・・・アプローチが何か間違っている
- (UPD ) #
要するに
F(x) = a * n + (F(x) mod n) ∃a∈N
で表せる、と思うから、
F(x + 1) = b * n + (F(x + 1) mod n) ∃b∈N
なわけで
F(x + 2) = c * n + (F(x + 2) mod n) ∃c∈N
= F(x + 1) + F(x)
= b * n + (F(x + 1) mod n) + a * n + (F(x) mod n)
= (a + b) * n + (F(x + 1) mod n) + (F(x) mod n)
となるが・・・
c >= a + b は成り立つ ※(F(x + 1) mod n) + (F(x) mod n)がn以上になった場合は、a+bよりcが大きいのは自明・・・
- (UPD ) #
愚直にやるなら
まぁ
10^9までのすべてのnにおいて周期調べて120になってるのだけピックアップする
という感じだが
10^9*120の計算量（？）だから、所要時間ヤバそう、数日？数か月？やべえな（パソコンのスペック次第でもあるか・・・？difficulty5%だからそういう気合で解けるやつだね・・・
- (UPD ) #
(omitted)
これ、お宝スポットとかイベントスポットの位置が変わる可能性・・・？
- (UPD ) #
もう、マネーない・・・
おにこんぼうやナウマンボーグと戦いたいのに
タイミング合わないな・・・宝珠ミッション
なかなか厳しいね・・・
導きのかけらが溜まって
１４章６話を解放できた
バッテリー都合で開始はしてないので
ストーリーは不明だが
フィールドモンスターにシルエットはなかったまた、wifi切れた・・・
また最近不安定だな・・・なぜ・・・
*1:F(x-1) mod n) + (F(x-2) mod n
