6 の約数は1,2,3,6である。 これらの数の平方和は1+4+9+36=50となる。

$n$の約数の平方和を$\textrm{sigma2}(n)$で表すとしよう。

$\textrm{sigma2}$の総和関数を$\textrm{SIGMA2}$としよう。 すなわち $\textrm{SIGMA2}(n)=\sum_{i=1}^n \textrm{sigma2}(i)$である。 $\textrm{SIGMA2}$の最初の6項は1,6,16,37,63,113となる。

$\textrm{SIGMA2}(10^{15}) \mod 10^9$を求めよ。

質問することで整数の集合${1, 2, \dots, n}$から選ばれた秘密の数を見つけ出したい。 数による質問それぞれに対し、以下の3つの回答から一つを得る。

• 「あなたの推測は秘密の数より小さい」（aのコストがかかる）

• 「あなたの推測は秘密の数より大きい」（bのコストがかかる）

• 「正解」（ゲーム終了）

与えられた値 n, a, b に対して、最適戦略とは最悪の場合の総コストを最小化する。

例として、n = 5, a = 2, b = 3 の場合、最初の質問として（秘密の数が）"2" であるかどうかを聞いてみる。

もし 2 が秘密の数より大きければ（コストは b=3 ）秘密の数字は "1" であることがわかる。（総コストは 3 ） もし 2 が秘密の数より小さければ（コストは a=2 ）次の質問は "4" となる。 もし 4 が秘密の数より大きければ（コストは b=3）秘密の数は "3" であることがわかる。（総コストは 2+3=5 ） もし 4 が秘密の数より小さければ（コストは a=2 ）秘密の数は "5" であることがわかる。（総コストは 2+2=4 ） このようにして、この戦略における最悪の場合のコストは 5 となる。またこれが最も低い最悪の場合のコストであることを示すことができる。つまり、これが与えられた値 n, a, b における最適戦略である。

与えられた値 n, a, b に関する最適戦略における最悪の場合のコストを$C(n, a, b)$としよう。

以下に例を示す: $C(5, 2, 3) = 5$ $C(500, \sqrt{2}, \sqrt{3}) = 13.22073197\dots$ $C(20000, 5, 7) = 82$ $C(2000000, \sqrt{5}, \sqrt{7}) = 49.63755955\dots$

$F_k$をフィボナッチ数と定義しよう：$Fk = F_{k-1} + F_{k-2}$, 初期条件は$F_1 = F_2 = 1$

$\displaystyle \sum_{k=1}^{30} C(10^{12}, \sqrt{k}, \sqrt{F_k})$を求め、回答を小数点以下8桁になるよう四捨五入して答えよ。

$0 ≤ a ≤ 5$の$a$に対し$a^2 \mod 6$を計算すると、0,1,4,3,4,1 となる。

$a^2 = a \mod 6$を満たす最大の$a$の値は4である。 $a^2 = a \mod n$を満たす$a<n$の最大値を$M(n)$としよう。 つまり$M(6)=4$である。

$1 \leq n \leq 10^7$のときの$\sum M(n)$を求めよ。

$x^2 + 4y^2 = 4a^2$の方程式からなる楕円を$E_a$とする。 原点$O(0,0)$を中心に$0° < θ < 90°$の範囲で$E_a$を$θ$度時計回りに回転させた図形を$E_a'$とする。

原点から近い方の2つの交点の原点からの距離を$b$、それ以外の2つの交点の原点からの距離を$c$とする。 $a, b, c$が正の整数となるとき、次のように順序付けされた三つ組(triplet)$(a, b, c)$を正準楕円三つ組と呼ぼう。 例えば、(209, 247, 286) は正準楕円三つ組である。

$a ≤ N$の場合の異なる正準楕円三つ組$(a, b, c)$の個数を$C(N)$としよう。 $C(10^3) = 7, C(10^4) = 106, C(10^6) = 11845$であることが確認できる。

$C(10^{17})$を求めよ。

長さが幅の二倍の長方形のタイルを敷き詰めたい。 一個の長方形タイルからなる敷き詰めを$T(0)$としよう。 $n > 0$に対し、下記の方法で$T(n-1)$のすべてのタイルを置き換えたものを$T(n)$としよう。

n が0から5のときの敷き詰め方 T(n) を以下のアニメーションに示そう。

$T(n)$において4つのタイルが集まっている点の数を$f(n)$としよう。 例えば$f(1) = 0, f(4) = 82, f(10^9) \mod 17^7 = 126897180$である。

$k = 10^{18}$のときの$f(10^k)$を求め、回答を$17^7$を法として答えよ。

多項式はすべての整数において6の倍数となることが示せる。 また、このような性質を満たす最大の整数は6であることも示せる。

がすべての整数での倍数となるような最大のをと定義しよう。例えばとなる。

同様に、のときのの和をと定義しよう。

、そしてであることがわかる。

フィボナッチ数列を次のように定義しよう：

そしてのとき

に対するの末尾9桁を求めよ。

$x, y, x+y$がすべて正の完全平方数であるとき、その格子点$(x,y)$を非許容点と呼ぼう。 例えば (9, 16) は非許容点であり、(0, 4), (3, 1), (9, 4) はそうではない。

点$(x_1, y_1)$から$(x_2,y_2)$へ、北か東への単位ステップのみを使って移動する経路を考えよう。 その経路の途中の点で非許容点を通らないとき、そのような経路を許容経路と呼ぼう。

$(0, 0)$から$(n,n)$までの許容経路の数を$P(n)$としよう。 P(5) = 252, P(16) = 596994440, P(1000) mod 1 000 000 007 = 341920854 であることが確かめられる。

P(10 000 000) mod 1 000 000 007 を求めよ。

Cを半径$r$の円$x^2 + y^2 = r^2$とする。2つの点P$(a, b)$, Q$(-a, c)$を、その2点を通る直線がCの接線となるように選ぶ。

例えば、4つ組$(r, a, b, c) = (2, 6, 2, -7)$はこの性質を満たす。

$0 < r ≤ R , 0 < a ≤ X$において、上記の性質を満たす整数の4つ組$(r, a, b, c)$の個数を$F(R, X)$としよう。

$F(1, 5) = 10, F(2, 10) = 52, F(10, 100) = 3384$となることが確かめられる。 $F(10^8, 10^9) + F(10^9, 10^8)$を求めよ。

n を正の整数とする。以下のような nim (訳注:いくつかの山に分かれた石を交互にとっていくゲーム, Problem 301を参照のこと) の配置について考えよう :

• n 個の空でない山がある.

• それぞれの山の大きさは 2&sup{n}; 未満である.

• 同じサイズの山は存在しない.

上記の条件を満たす必勝nim配置(最初のプレイヤーが必勝法を持つ配置)の数を W(n) としよう. 例として, W(1) = 1, W(2) = 6, W(3) = 168, W(5) = 19764360, W(100) mod 1 000 000 007 = 384777056 となる.

W(10 000 000) mod 1 000 000 007 を求めよ。

整数とに対し、放物線と直線で囲まれた領域を定義しよう。すなわち：

に含まれる格子点の個数をと定義しよう。 例として、である。

さらにの面積が有理数であり、かつであるすべてのペアに対するの和をと定義する。 であることが確認できる。

を求めよ。回答はを法として答えよ。