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

$n$ の一意表現の項数を $w(n)$ とする。したがって $w(3)=4, w(10)=3$ である。

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

$\displaystyle n = \sum_{k=-\infty}^\infty b_k r^k$

• 全ての $k$ について $b_k$ は0か1

• 全ての $k$ について $k$$b_k+b_{k+1}+b_{k+2} \leq 1$

• $\displaystyle w(n)=\sum_{k=-\infty}^{\infty} b_k$ は有限である

いま、$\displaystyle S(m)= \sum_{j=1}^{\infty} w(j^2)$ とする。 $S(10)=61$ と $S(1000)=19403$ が与えられている。

$S(5\,000\,000)$ を求めよ。

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

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

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

$L(10,5)=9964, L(10,10)=472400303, L(103, 103) \bmod (10^9+7) = 954021836$ である。

$L(10^7, 10^7) \bmod (10^9+7)$ を求めよ。

行列の全ての行で $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)$ を求めよ。