次の等式について考える：$a^2 + b^2 = N$（$0 ≤ a ≤ b, \, a,b,N$は整数）

等式$a^2 + b^2 = N$について考える。ここで$0 ≤ a ≤ b$とし、$a,b,N$は整数である。

たとえば N=65 では 2 つ解がある： a=1, b=8 と a=4, b=7 である。

$S(N)$を$a^2 + b^2 = N$（$0 ≤ a ≤ b, \, a,b,N$は整数） の全ての解の$a$の値の和とする。

つまり S(65)=1+4=5 である。

平方因子を持たず、150 未満の 4k+1 で表せる素数でのみ割りきれるような全ての N に関して$\sum S(N)$を求めよ。

正の整数$n$に対し、$S(n)$を$1<x<n$で$x^3 ≡1 \mod n$を満たすような整数$x$の和と定義する。

$n=91$のとき、$x$は 8 つの値を取りうる、すなわち 9, 16, 22, 29, 53, 74, 79, 81 である。 つまり、$S(91)=9+16+22+29+53+74+79+81=363$である。

S(13082761331670030) を求めよ。

正の整数$n$に対し、$S(n)$を$1<x<n$で$x^3 ≡1 \mod n$を満たすような整数$x$の和と定義する。

$n=91$のとき、$x$は 8 つの値を取りうる、すなわち 9, 16, 22, 29, 53, 74, 79, 81 である。 つまり、$S(91)=9+16+22+29+53+74+79+81=363$である。

$C(n)=242$を満たす正整数$n≤10^{11}$の合計を求めよ。

10 と互いに素な整数 p > 1 に対し、次のような性質がある正の整除乗数 (divisibility multiplier) m < p が存在する：任意の正の整数 n に対しp で割り切れるかどうかを次の関数が保存する：

f(n) = (n の最後の桁以外) + (n の最後の桁) * m

つまり、もし m が p の整除乗数であるなら、f(n) が p で割り切れる必要十分条件は n が p で割り切れることである。

（n が p より十分大きければ、f(n) は n より小さくなり、f を繰り返し適用することで p の整除乗数のテストに使用できる）(*multiplicative divisibility test 訳正しい？)

例えば、113 の整除乗数は 34 である。

f(76275) = 7627 + 5 * 34 = 7797 : 76275 と 7797 は共に 113 で割り切れる。 f(12345) = 1234 + 5 * 34 = 1404 : 12345 と 1404 は共に 113 で割り切れない。

1000 未満で 10 と互いに素な素数の整除乗数の合計は 39517 である。 $10^7$未満で10 と互いに素な素数の整除乗数の合計は？

辺の長さ a, b, c が整数で a ≤ b ≤ c となるような三角形について考える。 整数である辺の長さ (a,b,c) の三角形が gcd(a,b,c)=1 を満たすとき、原始的であるという。 周長が 10 000 000 を超えない、辺の長さが整数で原始的な三角形はいくつあるか。

位数 n の均整の取れた彫像を次のように定義する：

• ブロック（n 枚のタイル）と台座（残りのタイル）と呼ばれる n+1 枚のタイルからなるポリオミノ(*)である

• 台座は中心が (x = 0, y = 0) にある

• ブロックの y 座標は 0 より大きい（つまり台座のみが一番下のタイルである）

• 全ブロックをあわせた重心は x 座標が 0 に等しい

彫像を数えるとき、y 軸に対称なだけの図形は別のものと考えない。例えば、位数 6 の 18 個の均整の取れた彫像は以下の通りである。（y 軸に対し）鏡像のペアは 1 つの彫像として数えていることに注意せよ：

位数 10 の均整の取れた彫像は 964 あり、位数 15 では 360505 ある。 位数 18 の均整の取れた彫像はいくつあるか？

(*) ポリオミノ(polyomino)：同じ形の正方形を共有する辺でつなげた図形。穴は許される。

全ての辺の長さが整数で、少なくとも1つの角が度で計測して整数である三角形のうち、周長が $10^8$を超えないものはいくつあるか。

いくつかの整数$1 < a_1 < a_2 < \dots < a_n$に対し、次の線形の組み合わせについて考える。 $q_1 a_1 + q_2 a_2 + \dots + q_n a_n = b$、ただし$q_k ≥ 0$は整数のみとする。

与えられた整数列$a_k$に対して、$b$は全ての値を網羅しないかもしれないことに注意せよ。 例えば、$a_1 = 5, a_2 = 7$のとき、$b$が 1, 2, 3, 4, 6, 8, 9, 11, 13, 16, 18 または 23 となるような $q_1 ≥ 0, q_2 ≥ 0$は存在しない。 実際、23 は$a_1 = 5, a_2 = 7$に対して$b$の値とならない最大の数である。 これを$f(5, 7) = 23$とする。 同様に、$f(6, 10, 15) = 29, f(14, 22, 77) = 195$であることを示せる。

$p, q, r$が素数で$p < q < r < 5000$であるとしたとき、$\sum f(pq,pr,qr)$を求めよ。

整数の修正コラッツ列は値$a_1$から始めて次のようにして得られる：

$a_n$が3で割り切れるならば、$\displaystyle a_{n+1} = \frac{n}{3}$ これを大きな下降ステップ "D" と表す。

$a_n$を3で割った余りが1ならば、$\displaystyle a_{n+1} = \frac{4a_n + 2}{3}$ これを大きな上昇ステップ "U" と表す。

$a_n$を3で割った余りが2ならば、$\displaystyle a_{n+1} = \frac{2a_n - 1}{3}$ これを小さな下降ステップ "d" と表す。

数列は$a_n = 1$となれば終了する。

任意の整数が与えられたとき、ステップの列を書き出すことができる。 例えば$a_1=231$なら、数列${a_{n}}={231,77,51,17,11,7,10,14,9,3,1}$はステップ "DdDddUUdDD" に対応する。

もちろん、同じ列 "DdDddUUdDD...." から始まる列は他にもある。 例えば$a_{1}=1004064$なら、ステップの列は DdDddUUdDDDdUDUUUdDdUUDDDUdDD である。 実際、1004064 は列 DdDddUUdDD から始まる最小の可能な$a_1 > 10^6$である。

列 "UDDDUdddDDUDDddDdDddDDUDDdUUDd" から始まる最小の$a_1 > 10^{15}$は何か？

勤勉なアリが 5x5 の格子をランダムに歩く。中央のマスから歩き始める。各ステップにおいて、アリは格子からはみ出すことなく、隣接するマスにランダムに移動する。ゆえに各ステップではアリの位置に応じて 2, 3, 4 通りの移動の仕方がある。

出発前に、種が最下列の各マスに置かれる。アリが種を運んでおらず、かつ種のある最下列のマスに到達した場合、アリは種を運び始める。アリは、最上列の種のないマスに最初に到着したとき、そこに種を落とす。

すべての種が最上列に落とされるまでのステップ数の期待値はいくつか。 答を小数第 6 位に丸めて求めよ。