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

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

$N$未満の一人っ子数の個数を$F(N)$としよう。 $F(10) = 9$, $F(10^3) = 389$, $F(10^7) = 277674$であることが確かめられている。

$F(10^{19})$を求めよ。

格子点の集合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$を求めよ。

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

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

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

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

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

しかしながら、5桁で基数が$b = 6t+3≠9$の場合、カプレカ定数は存在する。 例えば、基数が15 のとき：$(10,4,14,9,5)_{15}$ 基数が 21 のとき：$(14,6,20,13,7)_{21}$

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

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

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

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

$0 < i < b^5$における$sb(i)$の和を$S(b)$と定義しよう。 例えば、$S(15) = 5274369$ $S(111) = 400668930299$

$2 ≤ k ≤ 300$における$S(6k+3)$の和を求めよ。 回答として末尾18桁を答えよ。

ある正の整数を$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)$を求めよ。

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

一番左のマスにカエルがいる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桁を求めよ。

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となる。

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

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

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

単位分数とは分子が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 であるとしよう。

$1/n$の循環節の長さを$L(n)$で表すとしよう。$3 ≤ n ≤ 1 000 000$における$\sum L(n)$は 55535191115 である。

$3 ≤ n ≤ 100 000 000$における$\sum L(n)$を求めよ。