OMC225(F)

補題1.　$2$ 以上の整数 $n$ に対し，$\ a_{2n} = 2a_{2n-2} + a_{2n-1}, \ a_{2n+1} = a_{2n-1} + a_{2n}$ が成立する．

証明.　$\lbrace a_{n} \rbrace$ の定め方より， $$\begin{aligned} a_{2n} &= (a_{1} + a_{2} + \cdots + a_{2n-3}) + a_{2n-2} + a_{2n-1} = 2a_{2n-2} + a_{2n-1}, \\ a_{2n+1} &= (a_{2} + a_{4} + \cdots + a_{2n-2}) + a_{2n} = a_{2n-1} + a_{2n} \end{aligned}$$ が $n \geq 2$ に対して成立する．■

補題2.　$6$ 以上の整数 $n$ に対し，$a_{n} = 4a_{n-2} - 2a_{n-4}$ が成立する．

証明.　$n$ が偶数のとき，補題1より $$a_{n} = 2a_{n-2} + a_{n-1} = a_{n-3} + 3a_{n-2} = 4a_{n-2} - 2a_{n-4}$$ が $n \geq 6$ に対して成立する．また，$n$ が奇数のとき，補題1より $$a_{n} = a_{n-2} + a_{n-1} = 2a_{n-3} + 2a_{n-2} = 4a_{n-2} - 2a_{n-4}$$ が $n \geq 7$ に対して成立する．■

補題3.　任意の正整数 $n$ に対し，$a_{n}$ と $a_{n+1}$ をともに割り切る奇素数は存在しない．

証明.　$a_{n}$ と $a_{n+1}$ が共通の奇素因数 $p$ をもつような，最小の $n$ をとる．$a_1=a_2=1$ により $n\geq 2$ である．すると，$n$ が偶数のときは $a_{n-1} = a_{n+1} - a_{n}$ が，$n$ が奇数のときは $2a_{n-1} = a_{n+1} - a_{n}$ が $p$ で割り切れることになり，いずれにせよ（$p$ が奇数であることから）$a_{n-1}$ が $p$ で割り切れるから，最小性に矛盾する．■

　補題1と補題3から，「任意の正整数 $n$ に対して，$a_{n}$ と $a_{n+2}$ をともに割り切る奇素数 $p$ は存在しない」ことが示される．さらに，この事実と補題2から，「任意の正整数 $n$ に対して，$a_{n}$ と $a_{n+4}$ をともに割り切る奇素数 $p$ は存在しない」ことが示される．これより，$\gcd(a_{n}, a_{n+4})$ は $2$ 冪になる．よって，以下 $a_{n}$ が $2$ で割り切れる最大の回数 $b_n$ について考える．
　補題2を利用することで，$b_{1} = b_{2} = b_{3} = b_{4} = 0$ および $5$ 以上の添字に対し $$\begin{aligned} b_{8k} &= 2k - 1, & b_{8k+1} &\geq 2k + 2, & b_{8k+2} &= 2k, & b_{8k+3} &= 2k, \\ b_{8k+4} &= 2k, & b_{8k+5} &= 2k + 2, & b_{8k+6} &= 2k+1, & b_{8k+7} &= 2k+1 \end{aligned}$$ が成り立つことが分かる．これより，$\gcd(a_{n}, a_{n+4})=2^{c_{n}}$ とおけば， $$\begin{aligned} c_{8k} &= 2k-1, & c_{8k+1} &= 2k+2, & c_{8k+2} &= 2k, & c_{8k+3} &= 2k, \\ c_{8k+4} &= 2k, & c_{8k+5} &= 2k + 2, & c_{8k+6} &= 2k + 1, & c_{8k+7} &= 2k + 1 \end{aligned}$$ が成り立つ．$2^{49} \lt 10^{15} \lt 2^{50}$ により，求める最小値は $n = \mathbf{193}$ である．