*[[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

これらの数 s&sub{0};s&sub{1};s&sub{2};... を連結して無限長の数列 w を作る. ~
すなわち w = &color(blue){14025256741014958470038053646...}; となる.

正の整数 k に対し, もし数字の合計が k となる w の部分列が存在しないなら, p(k) を 0 と定義する.
もし数字の合計が k となる w の部分列が少なくとも一つ存在するなら, z をそのような部分列の中で最も前に出てくる部分列の先頭の位置とすると, 
正の整数 k に対し, もし数字の合計が k となる w の部分文字列が存在しないなら, p(k) を 0 と定義する.
もし数字の合計が k となる w の部分文字列が少なくとも一つ存在するなら, z をそのような部分文字列の中で最も前に出てくる部分文字列の先頭の位置とすると, 
p(k)=z と定義する.

例えば:

部分列 &color(blue){1};, &color(blue){14};, &color(blue){1402};, ...~
部分文字列 &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};, ...~
部分文字列 &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};, ...~
部分文字列 &color(blue){02};, &color(blue){0252};, ...~
はそれぞれ数字の合計が 2, 9, ... であり, ~
''3'' 番目で始まるので p(2)=p(9)=...=''3'' となる.

部分列 &color(blue){025}; は ''3'' 番目で始まり, 数字の合計は 7 だが, より前にある(''1'' 番目から始まる)部分列が数字の合計が 7 である為, 
部分文字列 &color(blue){025}; は ''3'' 番目で始まり, 数字の合計は 7 だが, より前にある(''1'' 番目から始まる)部分文字列が数字の合計が 7 である為, 
p(7) = 1 であって 3 ではないことに注意せよ.

0 < k ≤ 10&sup{3}; では Σp(k) = 4742 であることがわかる.

0 < k ≤ 2⋅10&sup{15}; において Σp(k) を求めよ.



トップ   新規 一覧 単語検索 最終更新   ヘルプ   最終更新のRSS