整数$a$と$b$に対し、放物線$y = x^2$と直線$y = ax + b$で囲まれた領域$D(a, b)$を定義しよう。すなわち： $D(a, b) = \{ (x, y) \,|\, x^2 \leq y \leq ax + b \}$

$D(a, b)$に含まれる格子点の個数を$L(a, b)$と定義しよう。 例として、$L(1, 2) = 8, L(2, -1) = 1$である。

さらに$D(a, b)$の面積が有理数であり、かつ$|a|, |b| \leq N$であるすべてのペア$(a, b)$に対する$L(a, b)$の和を$S(N)$と定義する。 $S(5) = 344, S(100) = 26709528$であることが確認できる。

$S(10^{12})$を求めよ。回答は$10^8$を法として答えよ。

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$を求めよ。

長さが幅の二倍の長方形のタイルを敷き詰めたい。 一個の長方形タイルからなる敷き詰めを$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$を法として答えよ。

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

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

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

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

$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)$を求めよ。

ある正の整数を$n$とする。$0\leq i \leq 2n$において座標$(x, y) = (2^i \mod n, 3^i \mod n)$の位置に駅があるとしよう。同じ座標を持つ駅が複数できる場合、それらは同じ駅であると見なす。

$(0, 0)$から$(n, n)$まで、$x, y$座標がいずれも減少することのない軌道を作ってみよう。そのような軌道で通ることのできる駅の最大数を$S(n)$とする。

例えば$n=22$の場合、11個の駅があり、条件を満たす軌道は最大5駅を通ることができる。したがって $S(22) = 5$となる。最適な軌道の例と共に、下にこの例を図示する。

$S(123) = 14, S(10000) = 48$であることが確かめられる。

$1 ≤ k ≤ 30$における$\sum S(k^5)$を求めよ。

質問することで整数の集合${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桁になるよう四捨五入して答えよ。

格子点の集合Sについて、そのうちの2点のみを通る直線が存在するとき、そのSをタイタニック集合と呼ぼう。

例えば以下の集合はタイタニック集合である。 S = {(0, 0), (0, 1), (0, 2), (1, 1), (2, 0), (1, 0)} ここで (0, 1) と (2, 0) を通る直線は S の他の点を通ることがない。

一方、集合 {(0, 0), (1, 1), (2, 2), (4, 4)} はタイタニック集合ではない。 なぜなら集合内のいかなる2つの点を通る直線も他の2つの点を通るからである。

ある正の整数$N$に対して、$0 \leq x, y \leq N$を満たすすべての点$(x,y)$におけるタイタニック集合Sの数を$T(N)$としよう。

$T(1) = 11$, $T(2) = 494$, $T(4) = 33554178$, $T(111) \bmod 10^8 = 15300401$, $T(10^5) \bmod 10^8 = 63259062$であることが確かめられている。

$T(10^{11}) \bmod 10^8$を求めよ。

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個のマスの列がある。 連続してジャンプすることにより、カエルは一番右のマスに移動し、再び一番左のマスに戻ってくる。 下り（最初のマスから離れる方へ向かう）のときはカエルは右へ1マス、2マス、あるいは3マスジャンプする。そして上り（最初のマスへ近づく方へ向かう）の時は同様にして左にジャンプする。 カエルはマスの外には移動できない。カエルはこの往復をm回繰り返す。

カエルが旅行をする方法のうち、訪れることなく残されるマスがたかだかひとつになるようなやり方の数を $F(m,n)$としよう。

例えば、$F(1, 3) = 4$, $F(1, 4) = 15$, $F(1, 5) = 46$, $F(2, 3) = 16$, $F(2, 100) \bmod 10^9 = 429619151$ となる。

$F(10, 10^{12})$の末尾9桁を求めよ。

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

$n^4 + an^3 + bn^2 + cn$がすべての整数$n$で$m$の倍数となるような最大の$m$を$M(a, b, c)$と定義しよう。例えば$M(4, 2, 5) = 6$となる。

同様に、$0 < a, b, c \leq N$のときの$M(a, b, c)$の和を$S(N)$と定義しよう。

$S(10) = 1972$、そして$S(10000) = 2024258331114$であることがわかる。

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

$F_0 = 0, F_1 = 1$ そして$k \geq 2$のとき$F_k = F_{k-1} + F_{k-2}$

$2 \leq k \leq 1234567890123$に対する$\sum S(F_k)$の末尾9桁を求めよ。

単位分数とは分子が1の分数である。分母が2から10の単位分数を10進数で表記すると次のようになる。

1/2 = 0.5 1/3 = 0.(3) 1/4 = 0.25 1/5 = 0.2 1/6 = 0.1(6) 1/7 = 0.(142857) 1/8 = 0.125 1/9 = 0.(1) 1/10 = 0.1

0.1(6)は 0.166666... を意味し、1桁の循環節を持つ。1/7 の循環節は6桁ある。

分母が 2 および 5 の素因数だけからなるとき、その単位分数は循環節を持たないと考えられる。 そのような単位分数の循環節の長さは 0 であるとしよう。

の循環節の長さをで表すとしよう。におけるは 55535191115 である。

におけるを求めよ。

の方程式からなる楕円をとする。 原点を中心にの範囲でを度時計回りに回転させた図形をとする。

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

の場合の異なる正準楕円三つ組の個数をとしよう。 であることが確認できる。

$n$を正の整数とする。 整数の三組$(a,b,c)$が以下のようになるとき、それを$n$の因数分解三組と呼ぶ。

• $1 ≤ a ≤ b ≤ c$

• $a·b·c = n$

$c / a$が最小となる場合の$n$の因数分解三組に対する$a+b+c$を$f(n)$で表すとしよう。

例として、$f(165)=19,$ $f(100100) = 142,$ $f(20!) = 4034872$である。

$f(43!)$を求めよ。

整数$m, n \; (0 \leq n < m)$において、$m \times m$格子の右上から$n \times n$格子を取り除いたものを$L(m,n)$としよう。（訳注：このような図形のことをグノモン (gnomon) と呼ぶ。）

例えば$L(5, 3)$は以下のようになる：

$L(m, n)$のそれぞれのマスに連続する整数 1, 2, 3, ... を番号付けしたい。このとき全てのマスの数が下のマスと左のマスにある数より小さくなるようにしたい。

$L(5, 3)$に対する有効な番号付けを2例示す：

$L(m, n)$に対する有効な番号付けの個数を$LC(m, n)$としよう。 $LC(3, 0) = 42$, $LC(5, 3) = 250250$, $LC(6, 3) = 406029023400$, $LC(10, 5) \bmod 76543217 = 61251715$であることが確かめられている。

$LC(10000, 5000) \bmod 76543217$を求めよ。

2つの正整数AとBが次の条件のいずれかを満たすとき、それらは親類であるという。 （これを "A ↔ B" で表す。）

1. AとBが同じ桁数を持ち、ちょうど1つの桁だけ異なる。例： 123 ↔ 173

2. A（もしくはB）の左側に新たに1桁追加してしてB（もしくはA）が作れる。例：23 ↔ 223, 123 ↔ 23

2と素数Pの間に素数からなる親類関係によるつながりがあり、そのつながりの中にPを超える素数がないとき、そのPを2の親戚と呼ぼう。

例えば、127は2の親戚である。可能なつながりの1つを示す： 2 ↔ 3 ↔ 13 ↔ 113 ↔ 103 ↔ 107 ↔ 127 しかし、11や103はどうやっても2の親戚にはなり得ない。

$N$以下の2の親戚ではない素数の和を$F(N)$としよう。 $F(10^3) = 431, F(10^4) = 78728$であることが確かめられている。

$F(10^7)$を求めよ。

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 を求めよ。

整数の数列 $S = \{s_i\}$ が $n$ 個の要素を持ち、それぞれの要素 $s_i$ が $1 \leq s_i \leq n$ を満たすとき、これを nの数列 と呼ぼう。したがって全体で $n^n$ 個のnの数列が存在することになる。例えば、数列 $S = \{1, 5, 5, 10, 7, 7, 7, 2, 3, 7\}$ は10の数列のひとつである。

ある数列 $S$ に対し、同じ値からなる最長の連続部分列の長さを $L(S)$ としよう。例えば、上記で与えられた数列 $S$ の場合、 $L(S) = 3$ となる、なぜなら3回連続して 7 が現れるからである。

全てのnの数列 $S$ に対し関数 $f(n) = \sum L(S)$ と定義しよう。

例として、$f(3) = 45, f(7) = 1403689, f(11) = 481496895121$ である。

$f(7\ 500\ 000) \bmod 1\ 000\ 000\ 009$ を求めよ。

正整数行列とは要素が全て正の整数の行列のことである。 正整数行列の中には、正整数行列の自乗として二つの方法で表せるものがある。例えば、

$\left ( \begin{array}{rr}40 & 12\\48 & 40\end{array} \right ) = \left ( \begin{array}{rr}2 & 3\\2 & 12\end{array} \right )^2 = \left ( \begin{array}{rr}6 & 1\\4 & 6\end{array} \right )^2$

二つの方法で正整数行列の自乗として表すことができる、対角和（跡, trace）がN未満の2x2の正整数行列の個数を$F(N)$としよう。 $F(50) = 7,$ $F(1000) = 1019$であることが確かめられている。

$F(10^7)$を求めよ。

桁の正の数（先行ゼロを持たない）がで割り切れる部分文字列を一つだけ持つとき、その数を一人っ子数と呼ぼう。

例えば、5671は4桁の一人っ子数である。すべての部分文字列 5, 6, 7, 1, 56, 67, 71, 567, 671, 5671 のうち、56のみが4で割り切れる。 同様に、104 は 3 桁の一人っ子数、0 は 3 で割り切れるからである。 1132451 は 7 桁の一人っ子数、245 は 7 で割り切れるからである。

未満の一人っ子数の個数をとしよう。 , , であることが確かめられている。

を求めよ。

無限に連なる箱の並びを考えよう。いくつかの箱には玉が入っている。例えば、玉の入った箱が2個連続し、それに続いて2個の空箱、玉の入った箱2個、1個の空箱、玉の入った箱2個、が並んだ初期配置について、これを交互に現れる玉の入った箱と空箱の数により数列 (2, 2, 2, 1, 2) と表すことができる。

一回の操作は、以下のルールに従って玉それぞれについてちょうど一回ずつ移動させることにより構成される：まだ移動していない最も左の玉を右側の一番近い空箱に入れる。

一回の操作で下記に示すように箱列の数列 (2, 2, 2, 1, 2) は (2, 2, 1, 2, 3) に変化する。新しくできた数列は玉の入っている最初の箱から始まっていることに注意。

このような系を箱玉系 (Box-Ball System) 、または略して BBS と呼ぶ。

十分にこの操作を繰り返したあと, この系は玉の入った箱の連続数が変わらない状態へと発展することがわかる。以下に示した例では、玉の入った箱の連続数は [1, 2, 3] に発展する。これを最終状態と呼ぼう。

数列 $\{t_i\}$ を以下のように定義する：

• $s_0 = 290797$

• $s_{k+1} = {s_k}^2 \bmod 50515093$

• $t_k = (s_k \bmod 64) + 1$

初期配置 $(t_0, t_1, \dots, t_{10})$ から開始すると、最終状態は [1, 3, 10, 24, 51, 75] となる。 初期配置 $(t_0, t_1, \dots, t_{10\, 000\, 000})$ から開始した時の最終状態を求めよ。 回答は最終状態の要素の自乗の和で答えよ。例えば、最終状態が [1, 2, 3] のとき、14 $( = 1^2 + 2^2 + 3^2)$ が答えるべき回答となる。

先頭から $n$ 個の正整数の $k$ 乗の和を $f_k(n)$ としよう。 例えば $f_2(10) = 1^2 + 2^2 + 3^2 + 4^2 + 5^2 + 6^2 + 7^2 + 8^2 + 9^2 + 10^2 = 385$ である。

$1 \leq i \leq n$ における $f_k(i)$ の和を $S_k(n)$ としよう。 例えば $S_4(100) = 35375333830$ である。

$2 \cdot 10^9$ から $2 \cdot 10^9 + 2000$ の間にある全ての素数の集合を $P$ とする。 $\displaystyle\sum_{p \in P} \big (S_{10000}(10^{12}) \bmod p \big )$ はいくつか？

数列 $a_1, a_2, a_3, \dots$ を以下のように定義する：

• $a_1 = 1$

• $n \geq 1$ について、$a_{n+1} = 6{a_n}^2 + 10a_n + 3$

例えば： $a_3 = 2359$ $a_6 = 269221280981320216750489044576319$ $a_6 \bmod 1\,000\,000\,007 = 203064689$ $a_{100} \bmod 1\,000\,000\,007 = 456482974$

$B(x,y,n)$ を、$x \leq p \leq x + y$ である全ての素数 $p$ に対する $\sum (a_n \bmod p)$ と定義する。

例えば： $B(10^9, 10^3, 10^3) = 23674718882$ $B(10^9, 10^3, 10^{15}) = 20731563854$

$B(10^9, 10^7, 10^{15})$ を求めよ。

虹の７色について、それぞれの色の付けられたボールが10個ずつ、計70個が壺に入っている。 （壺の中に色の付いたボールが70個入っている。色の内訳は虹の７色の各色がそれぞれ10個ずつである。） ランダムに20個のボールを取り出したとき、色数の期待値はいくつか？ 小数点以下9桁にして（a.bcdefghij の形式で）答えよ。

式$12^2 + 7xy - 12y^2 = 625$で定義される双曲線を H とする。

次に、点$(7, 1)$を X と定義する。X は H 上にあるのがわかるだろう。

そして、H 上の点列 (sequence of points) $\{P_i : i ≥ 1\}$を以下のように定義する：

• $P_1 = (13, 61/4)$

• $P_2 = (-43/6, -4)$

• $i > 2$の$i$に対して、点$P_i$は線分$P_i P_{i-1}$が線分$P_{i-2}X$と平行になるように引かれた時の$P_{i-1}$とは異なる方の H 上の唯一の点である。$P_i$は明確に定義することができ(well-defined)、さらにそれらの座標は常に有理数となる。

$P_3 = (-19/2, -229/24),$ $P_4 = (1267/144, -37/12),$ $P_7 = (17194218091/143327232, 274748766781/1719926784)$がすでに与えられている。

$n = 11^{14}$のときの$P_n$を求め、以下の形式で答えよ： $P_n$を既約分数、また分母を正の数として表したとき$(a/b, c/d)$となるならば、答えは$(a + b + c + d) \bmod 1 \,000\, 000\, 007$ とする。

例えば$n = 7$のとき、答えるべき解答は 806236837 となる。

$n^{15}+1$ の形の数は$n>1$のすべての整数$n$において合成数である。 正の整数$n$と$m$に対し、$m$を超えない$n^{15}+1$の異なる素因数の和を$s(n,m)$としよう。

例えば、$2^{15}+1 = 3 \times 3 \times 11 \times 331$である。 したがって$s(2,10) = 3$である。また$s(2,1000) = 3+11+331 = 345$である。

同様に、$10^{15}+1 = 7×11×13×211×241×2161×9091$である。 したがって$s(10,100) = 31, s(10,1000) = 483$である。

$1 \leq n \leq 10^{11}$における $\sum s(n,10^8)$を求めよ。

$n$ を正の整数とする。 一個の六面サイコロを$n$回投げる。サイコロの出目が連続して同じ値となるペアの数を $c$ とする。

例えば、$n=7$ でサイコロの目が (1,1,5,6,6,6,3) のとき、連続して同じ値となるサイコロの出目のペアは： (1,1,5,6,6,6,3) (1,1,5,6,6,6,3) (1,1,5,6,6,6,3) したがって、(1,1,5,6,6,6,3) のとき $c=3$ となる。

一個の六面サイコロを $n$ 回投げたとき、$c$ が $\pi(n)$ を超えない結果の数を $C(n)$ と定義する。 例として、$C(3) = 216, C(4) = 1290, C(11) = 361912500, C(24) = 4727547363281250000$ である。

$\displaystyle S(L) = \sum_{n=1}^L C(n)$ と定義する。 例として、$S(50) \bmod 1\,000\,000\,007 = 832833871$ である。

$S(50\,000\,000) \bmod 1\,000\,000\,007$ を求めよ。

注：$π$ は素数計数関数 (prime-counting function) を意味する。すなわち、$\pi(n)$ は $n$ 以下の素数の個数である。

「結果の数」とは「場合の数」か？

Ramvok というゲーム一回分について考えよう：

ゲーム終了までの最大のターン数を $t$ で表す。 $t= 0$ ならば、ゲームは即座に終了する。 それ以外のとき、それぞれの $i$ 回目のターンに、プレイヤーはサイコロを一つ投げる。 投げたあと、$i < t$ ならば、プレイヤーは出たサイコロの目と同額の賞金を受け取ってゲームを終えるか、出た目を捨てて次のターンに挑戦することができる。 $i=t$ のときは、出た目を捨てることはできず賞金を受け取らなければならない。 ゲーム開始前に、プレイヤーは $t$ を決めて、ある定数 $c$ に対して前金 $ct$ を支払う必要がある。 $c = 0$ ならば、（前金は0となるので）$t$ として無限大を選ぶことができる。 偏りのない $d$ 面のサイコロとコスト定数 $c$ が与えられ、Ramvok を最適に行った時に一回のゲームでプレイヤーが受け取ることになる期待利益 (すなわち純利益) を $R(d,c)$ としよう。 例えば $R(4,0.2) = 2.65$ となる。 プレイヤーはどんな前金でも支払えるだけの十分な資金を持っていると仮定する。

ここで Super Ramvok というゲームを考えよう：

Super Ramvok では, Ramvok を繰り返し行うが, 若干の変更点がある。 それぞれのゲームのあと、サイコロを変更する。 変更の手順は次の通り： サイコロを一度だけ投げる。普通の面が出たとき、その面を白く塗りつぶす。 前に塗りつぶされた面が出たときは、元の目に戻す。 この変更が行われた後、次の Ramvok ゲームを開始できる。（そしてゲームの最中、それぞれのターンで、サイコロは塗りつぶされていない面が出るまで投げ直す。） プレイヤーは常にどの目が空白でどの目がそうでないかを把握している。 サイコロのすべての目が空白になった時点で Super Ramvok のゲームは終了となる。

偏りのない $d$ 面のサイコロ（開始時はすべての目が見えている）とコスト定数 $c$ が与えられ、Super Ramvok を最適に行った時に一回のゲームでプレイヤーが受け取ることになる期待利益を $S(d,c)$ としよう。 例えば $S(6,1) = 208.3$ となる。

$\displaystyle F(n) = \sum_{d = 4}^n \sum_{c = 0}^n S(d,c)$ とする。

$F(20)$ を計算し、最も近い整数に四捨五入せよ。

（cは整数で考えればよい？）

$k$ 個の異なる正の整数の積として $n$ を書き表す方法の数を $W(n,k)$ としよう。

例えば、$W(144,4)=7$ となる。4つの異なる正の整数の積として144を書き表す方法は7つある：

• 144 = 1×2×4×18

• 144 = 1×2×8×9

• 144 = 1×2×3×24

• 144 = 1×2×6×12

• 144 = 1×3×4×12

• 144 = 1×3×6×8

• 144 = 2×3×4×6

整数の順序を並び替えたものは異なるものとは考えないことに注意せよ。

さらに、$W(100!,10) \bmod 1\,000\,000\,007 = 287549200$ である。

$W(10000!,30) \bmod 1\,000\,000\,007$ を求めよ。

コラッツ数列は次のように定義される： $a_{i+1} = \left \{ \begin{array}{cl}a_i / 2 & a_i が偶数のとき \\ 3a_i+1 & a_i が奇数のとき \end{array} \right .$

コラッツ予想では、いかなる正の整数から始めても、この数列は最終的に 1,4,2,1... という周期に入るとされている。 $a_1 = n$ から始まるコラッツ数列のうち、2のべき乗でない数からなる部分数列を、その数列の先頭の数を用いて $p(n)$ と表し、これを「数列プレフィックス」と定義する。 （この問題では $2^0 = 1$ は2のべき乗と見なす。）

例えば： $p(13) = \{13, 40, 20, 10, 5\}$ $p(8) = \{\}$ コラッツ予想に反する数が存在するならば、この部分数列は無限の長さを持つことになる。

長さ $m$ の全ての数列プレフィックスの集合を $S_m$ とする。$S_m$ 内の2つの数列 $\{a_1, a_2, \dots, a_m\}$ と $\{b_1, b_2, \dots, b_m\}$ が、$1 \leq i,j \leq m$ において $b_i < b_j$ かつそのときに限り $a_i < a_j$ であるならば、この数列は同じプレフィックスファミリーに属すると言うことにする。

例えば、集合 $S_4$ 内では、{6, 3, 10, 5} は {454, 227, 682, 341} と同じファミリーに属するが、{113, 340, 170, 85} はそうではない。 $S_m$ 内の異なるプレフィックスファミリーの個数を $f(m)$ と定義しよう。 f(5) = 5, f(10) = 55, f(20) = 6771 が与えられている。

f(90) を求めよ。

6174 は驚くべき数である。その数の桁を大きい順にソートしてできる数から小さい順にソートしてできる数を引くと 7641-1467=6174 となる。

更に驚くべきことに、いかなる4桁の数からスタートしてソートと引き算を繰り返しても、最終的に6174に落ち着くか、すべての桁が同じ場合には 0 となる。

これは4桁より少ない桁の数でも、4桁となるまで先行ゼロを付与することで同様に再現できる。 例えば、数 0837 から始めてみると： 8730-0378=8352 8532-2358=6174

6174 はカプレカ定数 (Kaprekar constant) と呼ばれる。またこのソートと引き算のプロセス、そして 0 かカプレカ定数になるまでこのプロセスを繰り返すことをカプレカルーチン (Kaprekar routine) と呼ぶ。

別の基数、別の桁数の数に対してカプレカルーチンを考えてみよう。 残念なことに、どんな場合でも必ずカプレカ定数があるわけではない。入力される数によっては循環に陥る場合、あるいは異なる入力に対して異なる定数に落ち着く場合がある。

しかしながら、5桁で基数がの場合、カプレカ定数は存在する。 例えば、基数が15 のとき： 基数が 21 のとき：

5桁の数で基数がの場合のカプレカ定数をと定義しよう。 また関数を以下のように定義する：

• またはを基数で表記すると同じ数字の5桁の数となるとき値は 0

• それ以外のときは、基数でカプレカルーチンを行ってに到達するまでの繰り返しの回数

のすべての整数に対してが定義できることに注意。が基数で5桁に満たない場合、その数にはカプレカルーチン適用前に5桁になるまで先行ゼロが付与される。

におけるの和をと定義しよう。 例えば、

におけるの和を求めよ。 回答として末尾18桁を答えよ。

ある数 $n$ の単約数 (unitary divisor) $d$ とは、$\gcd(d, n/d) = 1$ となる $n$ の約数のことである。 $4! = 24$ の単約数は 1, 3, 8, 24 である。 これらの自乗和は $1^2 + 3^2 + 8^2 + 24^2 = 650$ となる。

$n$ の単約数の自乗和を $S(n)$ で表すとしよう。したがって $S(4!) = 650$ となる。

$S(100\ 000\ 000!) \bmod 1\ 000\ 000\ 009$ を求めよ。

整数の辺を持つ三角形 ABC が次のように与えられる： 三角形 ABC の内心を I としよう。 三角形 ABC の外接円と線分 AI との交点を D としよう(A ≠ D).

AC = DI, かつ BC ≤ L を満たす三角形 ABC の BC の長さの総和を F(L) と定義する。

例えば F(15) = 45、なぜなら辺の長さがそれぞれ (BC,AC,AB) = (6,4,5), (12,8,10), (12,9,7), (15,9,16) となる三角形 ABC がこの条件を満たす。

$F(10^9)$ を求めよ。

辺の長さが整数の三角形 ABC があり、その内心を $I$、周長を $p$ とする。 その上、線分 IA, IB, IC も整数の長さを持つ。

L = p + |IA| + |IB| + |IC| としよう。

$p \leq P$ となるような全ての三角形に対して $S(P) = \sum L$ としよう。 例えば $S(10^3) = 3619$ である。

$S(10^7)$ を求めよ。

0から9の数字をちょうど2回使った（先行ゼロのない）正整数をダブルパンデジタル数と呼ぼう。 例えば、40561817703823564929 はそのような数の一つである。

11で割り切れるダブルパンデジタル数はいくつあるか？

look and say 数列は 1, 11, 21, 1211, 111221, 312211, 13112221, 1113213211, ... と続いていく数列である。 この数列は1から始まり、他の項は前項の数について連続する桁をひとまとめにして言い表すことで得られる。 声に出してみるとやりやすい： 1 は 「1個の 1」 ('one one') → 11 11 は 「2個の 1」 ('two ones') → 21 21 は 「1個の 2 と1個の 1」 ('one two and one one') → 1211 1211 は 「1個の 1 と1個の 2 と2個の 1」 ('one one, one two and two ones') → 111221 111221 は 「3個の 1 と2個の 2 と1個の 1」 ('three ones, two twos and one one') → 312211 ...

この数列の n 番目の項の 1, 2, 3 の数をそれぞれ A(n), B(n), C(n) としよう。 A(40) = 31254, B(40) = 20259, C(40) = 11625 であることが確かめられている。

n が$10^{12}$のときの A(n), B(n), C(n) を求めよ。 回答はそれぞれを$2^{30}$を法として、 A,B,C とコンマで分かち書きして答えよ。 例えば、n が 40 のときの解答は31254,20259,11625となる。