オイラーのトーシェント関数を $φ(n)$ としよう。

$\displaystyle f(n)=(\sum_{i=1}^n φ(n^i)) \bmod (n+1)$ としよう。

$\displaystyle g(n)=\sum_{i=1}^n f(i)$ としよう。

$g(100) = 2007$ となる。

$g(5 × 10^8)$ を求めよ。

素数 $p$ を法としたときの $n$ の逆数を $d(p,n,0)$ としよう。つまり $n \times d(p,n,0) = 1 \bmod p$ と定義される。 $k \geq 1$ となるような k に対し、$\displaystyle d(p,n,k) = \sum_{i=1}^n d(p,i,k-1)$ としよう。 $a \leq p < a + b$ となるような全ての素数 $p$ に対し $D(a,b,k) = \sum (d(p,p-1,k) \bmod p)$ としよう。

次のように与えられている：

• $D(101,1,10) = 45$

• $D(10^3,10^2,10^2) = 8334$

• $D(10^6,10^3, 10^3) = 38162302$

$D(10^9,10^5,10^5)$ を求めよ。

$a \leq b \leq c$ となる整数辺を持つ三角形 ABC がある。 線分 AB の中点と点 C を結ぶ中線を $m_c$ とする。 $c \leq n$ であり、さらに $m_c$ が整数の長さを持つような三角形の数を $F(n)$ としよう。 $F(10)=3, F(50)=165$ である。

$F(100000)$ を求めよ。

（$N$次の）ジオボードとは、表面からピンが等間隔に突き出ていて、それらが座標 $0 \leq x,y \leq N$ における整数の格子点を表す正方形のボードである。

ジョンがピンのないジオボードに取り掛かっている。ボードのそれぞれの位置にはピンを入れることのできる穴が開いている。ジョンはジオボードのそれぞれの穴に対し 1 から $N+1$ の間（端を含む）のランダムな数を生成することに決める。もしある穴に対しそのランダムな数が 1 に等しければ、その穴にピンが差し込まれる。

こうしてジョンは全ての $(N+1)^2$ 個の穴に対し数を生成し、それに対応するピンを配置し終えると、そのボードから突き出ているピン全体を囲むようにピンと張られたゴムバンドを掛けていく。こうして形成される形状を $S$ と表すことにしよう. また $S$ は全てのピンを含む最小の凸形状と定義することができる。

上記の画像は $N = 4$ の場合の見本となる配置を表現したものである。緑の目印はピンが配置されている位置を示しており、青い線全体がゴムバンドを表している。この見本の場合の配置では、$S$ の面積は 6 になる。もしボード上のピンが3本未満（あるいはすべてのピンが同一線分上にある）ならば、$S$ の面積は0と見なすことができる。

1個の$N$次のジオボードによって与えられる$S$の面積の期待値を $E(N)$ としよう。小数点以下5桁となるよう四捨五入すると、$E(1) = 0.18750, E(2) = 0.94335, E(10) = 55.03013$ となる。

小数点以下5桁となるよう四捨五入した $E(100)$ を計算せよ。

以下のような3つ組 $(a,b,c)$ 全てに対して $S(n) = \sum (a + b + c)$ としよう：

• $a, b, c$ は素数

• $a < b < c < n$

• $a+1, b+1, c+1$ が等比数列となる

例えば, 以下のような3つ組により S(100) = 1035 となる：

(2, 5, 11), (2, 11, 47), (5, 11, 23), (5, 17, 53), (7, 11, 17), (7, 23, 71), (11, 23, 47), (17, 23, 31), (17, 41, 97), (31, 47, 71), (71, 83, 97)

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

$a > 1$ である全ての実数 $a$ に対し, 関数 $g_a$ が以下のように与えられている： （訳注：原文では sequence $g_a$ とある） $g_a(x)=1$ （$x < a$ のとき） $g_a(x)=g_a(x−1) + g_a(x−a)$　（$x \geq a$ のとき）

$G(n) = g_{\sqrt{n}}(n)$ とする。 $G(90)=7564511$ である。

$10\,000\,000 < p < 10\,010\,000$ の間の素数 $p$ に対する $\sum G(p)$ を求めよ。 答えは $1\,000\,000\,007$ を法として答えよ。

数 $n$ の最小の素因数を $s(n)$ と定義しよう。 $s(91)=7$ となる、なぜなら $91=7 \times 13$, そして $s(45)=3$, なぜなら $45=3 \times 3\times 5$. $2 \leq i \leq n$ の範囲における $s(i)$ の和を $S(n)$ としよう。 例えば $S(100)=1257$ である。

$S(10^{12}) \bmod 10^9$ を求めよ。

5-スムーズ数とは最大の素因数が5を超えないような数のことである。 5-スムーズ数はハミング数とも呼ばれる。 オイラーのトーシェント関数 $φ(n)$ がハミング数となるような、$L$を超えない数 $n$ の値の和を $S(L)$ としよう。 $S(100)=3728$ である。

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

Coprime Nim はニムゲームであり、「山から取り除く石の個数は、その山の石の個数と互いに素でなければならない」という条件がついている。2人のプレイヤーが交互に石を取り除き、最後の石を取り除いた方が勝ちである。

1 個以上 個以下の石の山が 個ある初期状態のうち、互いに最善手を尽くしたときに先手が負けるものの個数を とする。

例えば である。各山の石の個数が (1,1),(2,2),(2,4),(3,3),(4,2),(4,4) であったときに先手の負けとなる。

である。

を求めよ。

行列の全ての行で $j$ 列目の要素が $j+1$ 列目の要素より小さいとき、 $j$ 列目は上昇しているという。

次の条件を満たす $r×n$ 行列の個数を $P(k,r,n)$ とする。

• どの行も $\{1,2,3,\dots,n\}$ の並び替えである

• 最初の列を 1 列目として、列 $j < n$ は $j$ が $k$ の倍数でないときかつそのときに限り上昇している

例えば $P(1,2,3)=19, P(2,4,6)=65508751, P(7,5,30) \bmod (10^9+123) = 161858102$ である。

$\displaystyle Q(n)=\sum_{k=1}^n P(k,n,n)$ とする。

例えば $Q(5)=21879393751, Q(50) \bmod (10^9+123) = 819573537$ である。

$Q(50000) \bmod (10^9+123)$ を求めよ。

の実数解を とする。 全ての正の整数は の異なるべき乗の和として書くことができる。 項の数を有限、2つの指数の差を3以上とすると、一意に表現される。 例えば、, である。 興味深いことに、この関係はの複素数解にも成り立つ。

の一意表現の項数を とする。したがって である。

より形式的には、全ての正の整数 について、いくつかの条件のもとで一意に表せる。

• 全ての について は0か1

• 全ての について

• は有限である

いま、 とする。 と が与えられている。

を求めよ。

ある正整数の10進表記が、どの奇数数字についても、それが出現しているならば奇数回であり、どの偶数数字（訳注：0を含む）についても、それが出現しているならば偶数回であるとき、その数を simber であると定義しよう。

例えば 141221242 は9桁のsimberである、なぜなら3個の1、4個の2、2個の4を持っているからである。

たかだか $n$ 桁のsimberの個数を $Q(n)$ としよう。

$Q(7) = 287975, Q(100) \bmod 1\,000\,000\,123 = 123864868$ が与えられている。

$\displaystyle \left ( \sum_{1 \leq u \leq 39} Q(2^u) \right ) \bmod 1\,000\,000\,123$ を求めよ。

ある会社は、単位正方形の金属板から始めて大きな長方形の金属板の製造を専門としている。溶接はロボットによって実行される。残念なことに、これらのロボットにプログラムできることはかなり限られている。それぞれが最大 25 枚までの同一の長方形の金属板しか処理できず、どちらかの端に沿って溶接してより大きな長方形を作成することだけができる。設定できるパラメータは、処理する長方形の数（25 以下）と、長辺を溶接するか短辺を溶接するかだけである。

例えば、最初のロボットには、11 枚の未加工の単位正方形プレートを溶接して $11\times 1$ の長方形を作成するようにプログラムできる。次のロボットには、これらの $11 \times 1$ の長方形 $10$ 枚を溶接して、より長い $110\times 1$ の長方形、または $11\times 10$ の長方形を作成するようにプログラムできる。多くの長方形はこの方法で作成できるが、全てではない。

ある常連客が次のような珍しい注文を出した。完成品の面積は注文どおりで、長辺は短辺の 1.1 倍以下でなければならない。これらの条件を複数の方法で満たすことができる場合、客は全てのサイズを要求する。例えば、面積 889200 の金属板が注文された場合、900×988、912×975、936×950 の 3 つのサイズを生産することになる。面積 889200 は、ロボット溶接機の制限内で 3 つの異なるサイズで製造できる最小面積である。

長辺が短辺の 1.1 倍以下であるようなちょうど n 種のサイズを作ることができる最小の面積を $M(n)$ とする。つまり $M(3)=889200$ である。

$\displaystyle \sum_{n=2}^{100} M(n)$ を求めよ。

$\sigma(n)$を$n$の約数の総和とする。 例えば、4の約数は1,2,4なので、$\sigma(4)= 1 + 2 + 4 = 7$ である。

20以下の自然数$n$で、$\sigma(n)$が 7 で割り切れるようなものは4, 12, 13, 20 の 4 つで、その和は49である。

$S(n,d)$を、$n$以下の自然数$i$で、$\sigma(i)$が$d$で割り切れるようなものの和とする。 すると$S(20,7) = 49$である。

$S(10^6, 2017) = 150850429,$ $S(10^9, 2017) = 249652238344557$ である。

$S(10^{11}, 2017)$を求めよ。

整数 $a, b, c$ を、ある角が120度、$a \leq b \leq c$、$b-a \leq 100$の三角形の辺の長さとする。

$T(n)$ を $c \leq n$ を満たすこのような三角形の個数とする。 $T(1000) = 235$, $T(10^8) = 1245$である。

$T(10^{100})$ を求めよ。

正の整数を基数$b$で表記すると$0$から$b-1$の全ての数字を少なくともひとつ含むとき、基数$b$に関してパンデジタルであるという。

n超パンデジタル数とは、$2$から$n$までの全ての基数に関してパンデジタルな数である。

例えば $978 = 1111010010_2 = 1100020_3 = 33102_4 = 12403_5$ は最小の5超パンデジタル数である。 同様に、1093265784は最小の10超パンデジタル数である。 10超パンデジタル数の小さいものから10個の和は20319792309である。

12超パンデジタル数の小さいものから10個の和はいくつか？

下図左のように、円の周囲に正方形を描くことができる。 青く塗りつぶした領域をL切片と呼ぼう。

下図右のように、正方形の左下から右上に線を引くことができる。 橙色に塗りつぶした領域を凹んだ三角形と呼ぼう。

明らかに、凹んだ三角形はL切片のちょうど半分を占める。

下図のように、二つの円を水平に隣接させ、この二円の周りに長方形を描き、左下から右上に線を引くことができる。

今回、凹んだ三角形はL切片のおよそ36.46%を占める。

$n$個の円を水平に隣接させ、その $n$​ 個の円の周りに長方形を描き、左下から右上に線を引くとき、凹んだ三角形がL切片の10%未満を占めるような $n$ の最小値 $n = 15$​ である。

凹んだ三角形がL切片の0.1%未満を占めるような $n$ の最小値はいくつか？

隙間なく積まれた1段以上のコインの段があり、その上の段にあるコイン全てが下の段のちょうど2個のコインと接しているようなコインの配置をコインの噴水(fountain) と呼ぶ。$n$個のコインによる配置可能な噴水の数を $f(n)$ としよう。4個のコインの場合3個の可能な配置がある：

よって$f(4) = 3$ である。そしてさらに $f(10) = 78$ となる。

$n$ 個のコインによる $f(n)$ 個の噴水全てを、2個の接するコインが同じ色にならないという条件のもとに三色に塗り分ける配色の数を $T(n)$ としよう。4個のコインからなる3個の妥当な噴水のうちの1つに対する可能な塗り分け方は以下のようになる：

$T(4) = 48$ そして $T(10) = 17760$ が与えられている。

$T(20000)$ の末尾9桁を求めよ。

以下のような長さ $n$ の正整数の数列 $\{a_i\}_{1 \leq i \leq n}$ の個数を $Seq(n,k)$ としよう：

• $1 \leq i \leq n$ に対し $n$ が $a_i$ で割り切れる

• $n + a_1 + a_2 + \dots + a_n$ が $k$ で割り切れる

例えば:

Seq(3,4) = 4, そしてその4つの数列は: {1, 1, 3} {1, 3, 1} {3, 1, 1} {3, 3, 3}

Seq(4,11) = 8, そしてその8つの数列は: {1, 1, 1, 4} {1, 1, 4, 1} {1, 4, 1, 1} {4, 1, 1, 1} {2, 2, 2, 1} {2, 2, 1, 2} {2, 1, 2, 2} {1, 2, 2, 2}

Seq(1111,24) の末尾9桁は 840643584 となる。

Seq(1234567898765,4321) の末尾9桁を求めよ。