50 という数を考える. $50^2 = 2500 = 2^2×5^4$のため, $φ(2500) = 2×4×5^3 = 8×5^3 = 2^3×5^3$である. よって 2500 は平方数, かつ φ(2500) は立方数である.

$φ(n^2)$が立方数となる$1＜n＜10^{10}$の範囲の$n$の和を求めよ.

$φ$はオイラーのトーティエント関数を表す.

N.G. de Bruijn の銀貨ゲームの一変種

は次のように説明される :

四角いマスが帯状に並んだ盤面があり, そこにある個数の硬貨が最大一マスに一個で置かれている. 銀貨と呼ばれる硬貨がひとつだけ任意の位置にあり, 二人のプレイヤーは交互に硬貨の移動を繰り返す. プレイヤーはそれぞれの局面で基本移動か特殊移動のどちらかを行わなければならない.

基本移動はひとつの硬貨を選択しマスひとつ以上左に移動させる. 硬貨は盤面を出たり, 他の硬貨の上に乗せたり飛び越えたりしてはならない.

その一方, プレイヤーは基本移動ではなく, 一番左にある硬貨を手に入れるという特殊移動を選択することができる. もし基本移動が不可能な場合, プレイヤーは強制的に一番左の硬貨を手に入れなければならない.

銀貨を手に入れたプレイヤーが勝者となる.

後手がどのようにプレイしても, 先手が勝利できる硬貨の配列を「勝利配置」と呼ぶ.

仮に n 個のマスの盤面, c 個の普通の硬貨, 1個の銀貨の場合の勝利配置の数を W(n,c) とする.

すでに W(10,2) = 324, W(100,10) = 1514704946113500 が求められている.

半素数 1 000 036 000 099 (= 1 000 003 · 1 000 033 ) を法とする W(1 000 000, 100) の値を求めよ.

行と列それぞれで1つのみの要素を選択した場合の要素の合計が最も大きくなるものを, その行列の「行列計( Matrix Sum )」と定義する. 例えば, 下記の行列での行列計は3315になる. ( = 863 + 383 + 343 + 959 + 767) :

下記行列の行列計を求めよ.

素数 2 と 3 の両方のみで割り切れる100以下の最大の整数は 96 である. である. ２つの異なる素数とに対し,との両方のみで割り切れる以下の最大の正の整数を とする. そのような正の整数が存在しなければである.

例えばである. であって90ではない.90は2,3,5で割り切れるためである. またである.2と73の両方で割り切れる100以下の正の整数は存在しないためである.

を全てのの和とする.である.

を求めよ.

多くの数は平方数と立方数の和として表せる。複数のやり方で表せるものもある。

回文数であり、平方数と立方数の和として、ちょうど4通りのやり方で表せるものを考える。ただし、平方数と立方数はいずれも1より大きいものでなくてはならない。 例えば、5229225 は回文数であり、以下のようにちょうど４通りの異なるやり方で表せる：

• $2285^2 + 20^3$

• $2223^2 + 66^3$

• $1810^2 + 125^3$

• $1197^2 + 156^3$

このような回文数を小さいものから順に5つ求め、その和を答えよ。

黒白いずれかで色づけされた正方形の規則的な格子上をアリが動く. アリは四方（上下左右）のいずれかを向いており, 次のルールに則って正方形から隣接する正方形へ動く：

• 黒い正方形上にいる場合, その正方形の色を白に変えて反時計回りに向きを変え, １マス前進する.

• 白い正方形上にいる場合, その正方形の色を黒に変えて時計回りに向きを変え, １マス前進する.

格子全体が白の状態から始めるとき, アリが $10^{18}$回動いた後の黒い正方形の数は何個あるか.

「サイズ$n$のリスト」とは,$n$個の自然数からなる数列のことである. 例えば (2,4,6), (2,6,4), (10,6,15,6), (11).

リストの最大公約数, gcdとは, リストのすべての数を割り切る最大の自然数を言う. 例 : gcd(2,6,4) = 2, gcd(10,6,15,6) = 1, gcd(11) = 11.

リストの最小公倍数, lcmとは, リストそれぞれの数で割り切ることができる最小の自然数を言う. 例 : lcm(2,6,4) = 12, lcm(10,6,15,6) = 30, lcm(11) = 11.

gcd ≥ G, lcm ≤ L となるサイズ N のリストの個数を$f(G, L, N)$としよう. 以下に例を示す:

$f(10, 100, 1) = 91$ $f(10, 100, 2) = 327$ $f(10, 100, 3) = 1135$ $f(10, 100, 1000) \mod 101^4 = 3286053$

$f(10^6, 10^{12}, 10^{18}) \mod 101^4$を求めよ.

任意の正の整数$k$に対して、分数$x_i/y_i$の有限数列$a_i$は次のように定義される：

$a_1 = 1 / k$ $a_i = (x_{i-1}+1)/(y_{i-1}-1)$($i>1$のとき。約分可能な場合は約分する）

$a_i$がある整数$n$になったとき（つまり$y_i=1$になったとき）数列はそこで終了とする。 ここで関数$f(k) = n$と定義する。 例えば$k = 20$のとき

$1/20 → 2/19 → 3/18 = 1/6 → 2/5 → 3/4 → 4/3 → 5/2 → 6/1 = 6$

したがって$f(20) = 6$となる。

同様に$f(1) = 1, f(2) = 2, f(3) = 1$、$1 ≤ k ≤ 100$について$\sum f(k^3) = 118937$となる。

$1 ≤ k ≤ 2×10^6$について$\sum f(k^3)$を求めよ。

Golomb の自己記述的数列 $\{G(n)\}$は,$n$が数列にちょうど$G(n)$回現れるような, 自然数の非減少の数列である. 最初のいくつかの$n$に対する$G(n)$の値は次の通りである.

$G(10^3) = 86, G(10^6) = 6137$である. また,$1 ≤ n < 10^3$に対し,$\sum G(n^3) = 153506976$である.

$1 ≤ n < 10^6$に対し,$\sum G(n^3)$を求めよ.

7という数字は特別な数字である, なぜなら7は2進数では111と表せ, また6進数では11と表せる. (すなわち$7_{10} = 11_6 = 111_2$). 別の言い方をすると, 7は少なくとも二種類の1より大きい底の記数法でレプユニット(全ての桁が1である自然数)である.

ここで上記の特徴を有する正の整数を「強いレプユニット」と呼ぶことにする. 50未満には8つの強いレプユニットが存在する. :{1,7,13,15,21,31,40,43}. さらに, 1000未満の強いレプユニットの和は15864になる.

$10_{12}$未満の強いレプユニットの和を求めよ.