![[PukiWiki]](image/pukiwiki.png "[PukiWiki]")
#author("2022-11-03T04:51:16+00:00","","") *[[Problem 238:http://projecteuler.net/problem=238]] 「無限長列ツアー」 [#af955315] '''この問題の文章は前のエラーを直すため修正された. ''' "Blum Blum Shub" 擬似乱数生成器を用いて数列を作る: >>s&sub{0}; = 14025256 >>s&sub{n+1}; = s&sub{n};&sup{2}; mod 20300713 >>&tex{s_{0}}; = 14025256 >>&tex{s_{n+1}}; = &tex{s_{n}^{2}}; mod 20300713 これらの数 s&sub{0};s&sub{1};s&sub{2};... を連結して無限長の数列 w を作る. ~ これらの数 &tex{s_{0}s_{1}s_{2}};... を連結して無限長の数列 w を作る. ~ すなわち w = &color(blue){14025256741014958470038053646...}; となる. 正の整数 k に対し, もし数字の合計が k となる w の部分文字列が存在しないなら, p(k) を 0 と定義する. もし数字の合計が k となる w の部分文字列が少なくとも一つ存在するなら, z をそのような部分文字列の中で最も前に出てくる部分文字列の先頭の位置とすると, p(k)=z と定義する. 例えば: 部分文字列 &color(blue){1};, &color(blue){14};, &color(blue){1402};, ...~ はそれぞれ数字の合計が 1, 5, 7, ... であり, ~ ''1'' 番目で始まるので p(1)=p(5)=p(7)=...=''1'' となる. 部分文字列 &color(blue){4};, &color(blue){402};, &color(blue){4025};, ...~ はそれぞれ数字の合計が 4, 6, 11, ... であり, ~ ''2'' 番目で始まるので p(4)=p(6)=p(11)=...=''2'' となる. 部分文字列 &color(blue){02};, &color(blue){0252};, ...~ はそれぞれ数字の合計が 2, 9, ... であり, ~ ''3'' 番目で始まるので p(2)=p(9)=...=''3'' となる. 部分文字列 &color(blue){025}; は ''3'' 番目で始まり, 数字の合計は 7 だが, より前にある(''1'' 番目から始まる)部分文字列が数字の合計が 7 である為, p(7) = 1 であって 3 ではないことに注意せよ. 0 < k ≤ 10&sup{3}; では Σp(k) = 4742 であることがわかる. 0 < k ≤ &tex{10^{3}}; では Σp(k) = 4742 であることがわかる. 0 < k ≤ 2⋅10&sup{15}; において Σp(k) を求めよ. 0 < k ≤ 2×&tex{10^{15}}; において Σp(k) を求めよ. IP:112.68.65.182 TIME:"2022-11-03 (木) 13:51:16" REFERER:"http://odz.sakura.ne.jp/projecteuler/" USER_AGENT:"Mozilla/5.0 (Macintosh; Intel Mac OS X 10_15_7) AppleWebKit/537.36 (KHTML, like Gecko) Chrome/107.0.0.0 Safari/537.36"
