OMC225(F) - n の偶奇で分けた場合

　公式解説は $n$ の偶奇によって分けていないものの，漸化式の形から $n$ の偶奇で分けて考えるのも自然な発想である．ここでは，そのような方針で作成した解答を記しておく．
　なお，公式解説と本質的に大きく変わるわけではない．以下，公式解説の補題 1,2,3 とそれぞれ対応させながら記述している．

　まず数列 $\lbrace a_n \rbrace$ を奇数部分と偶数部分に分ける．$a_{2n-1}=s_n, a_{2n}=t_n$ としよう．

　補題 1.　$2$ 以上の整数 $n$ に対し，$s_{n+1}=s_n+t_n, t_{n+1}=s_n+3t_n$ が成立する．（証明略）

　補題 2.　$\gcd (s_n,s_{n+2})=\gcd(s_n, 4t_n)$，$\gcd (t_n,t_{n+2})=\gcd(t_n, 4s_n)$

　証明.　補題 1 の漸化式を用いて，$s_{n+2}=2s_n+4t_n, t_{n+2}=4s_n+10t_n$ を得る．あとは Euclid の互除法を用いればよい．

　補題 3.　任意の正整数 $n$ に対して，$s_n$ と $t_n$ をともに割り切る奇素数は存在しない．

　証明.　 $$\gcd (s_{n+1},t_{n+1})=\gcd(s_n+t_n, s_n+3t_n)=\gcd(s_n+t_n,2t_n) \leq \gcd(2s_n+2t_n,2t_n) =\gcd(2s_n,2t_n)$$ （途中の不等号は，単に大小関係だけではなく，一方が他方の約数であることも含意している．）
　この計算から，ある奇素数 $p$ について $p \mid \gcd (s_{n+1},t_{n+1})$ が成り立てば $p \mid \gcd (s_{n},t_{n})$ が成り立つ．$\gcd (s_2,t_2)=1$ より，そのような奇素数 $p$ は存在しない．

　補題 2 と補題 3 から $\gcd (s_n,s_{n+2}), \gcd (t_n,t_{n+2})$ はともに $2$ 冪である．よって，以下 $s_n,t_n$ が $2$ で割り切れる最大の回数を考える．
　そこで $n=2 \sim 6$ について，補題 1 の漸化式を用いながら，$s_n,t_n$ を $32$ で割った余りを書き並べてみよう． $$\begin{matrix} \ & n=2 & n=3 & n=4 & n=5 & n=6 \cr s_n & 1 & 4 & 14 & 16 & 4 \cr t_n & 3 & 10 & 2 & 20 & 12 \cr \end{matrix}$$ 　$(s_6, t_6)$ が $(s_2,t_2)$ のちょうど $4$ 倍になっていることがわかる．このことから着想を得て，$n=4k+2 \sim 4k+6$ について，$s_n,t_n$ を $2^{2k+5}$ で割った余りが次のように得られる．

$$\begin{matrix} \ & n=4k+2 & n=4k+3 & n=4k+4 & n=4k+5 & n=4k+6 \cr s_n & (8x+1)2^{2k} & \lbrace 8(x+y)+4 \rbrace 2^{2k} & (16x+14)2^{2k} & \lbrace 16(x+y)+16 \rbrace2^{2k} & 4×2^{2k} \cr t_n & (8y+3)2^{2k} & \lbrace 8(x+3y)+10 \rbrace 2^{2k} & (16y+2)2^{2k} & \lbrace 16(x+y)+20 \rbrace 2^{2k} & 12×2^{2k} \cr \end{matrix}$$

　この表を見れば，$4k+2 \leq n \leq 4k+6$ の範囲で $\gcd(s_n, 4t_n)$ または $\gcd(t_n, 4s_n)$ の最大値が $\gcd(s_{4k+5}, 4t_{4k+5})=2^{2k+4}$ であるとわかる．
　$2^{49} \lt 10^{15} \lt 2^{50}$ より，$2k+4=50$ から $k=23$ ．$s_{97}=a_{193}$ より求めるべき値は $\mathbf{193}$ である．