*[[Problem 337:http://projecteuler.net/index.php?section=problems&id=337]] [#z12d06bf]
*[[Problem 337:http://projecteuler.net/problem=337]] 「トーティエント階段数列」 [#z12d06bf]

{ a&sub{1};, a&sub{2};,..., a&sub{n};} を次のような長さ n の 整数列とする。
{a&sub{1};, a&sub{2};,..., a&tex{_{n}};} を次のような長さ &tex{n}; の 整数列とする.

- a&sub{1}; = 6
- 1≦i<n に対し:φ(a&sub{i};)<φ(a&sub{i+1};)<a&sub{i};<a&sub{i+1}; &sup{1};
- 1 ≤ &tex{i}; < &tex{n}; に対し : φ(a&tex{_{i}};) < φ(a&tex{_{i+1}};) < a&tex{_{i}}; < a&tex{_{i+1}}; &sup{1};

a&sub{n};≦N となる数列の数を S(N) とする。~
例えば、S(10) = 4 である:{6}, {6, 8}, {6, 8, 9}, {6, 10}.~
S(100) = 482073668 と S(10 000) mod 10&sup{8}; = 73808307 であることが確かめられる。
a&tex{_{n}}; ≤ N となる数列の数を S(&tex{N};) とする. ~
例えば, S(10) = 4 である:{6}, {6, 8}, {6, 8, 9}, {6, 10}.~
S(100) = 482073668 と S(10 000) mod 10&sup{8}; = 73808307 であることが確かめられる.

S(20 000 000) mod 10&sup{8}; を求めよ。
S(20 000 000) mod 10&sup{8}; を求めよ.

&sup{1}; φは''オイラーのトーティエント関数''を表す。
&sup{1}; φは''オイラーのトーティエント関数''を表す.


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