**補題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}$ である．
公式解説
https://onlinemathcontest.com/contests/omc225/editorial/9208
　公式解説は $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}$ である．
n の偶奇で分けた場合
https://onlinemathcontest.com/contests/omc225/editorial/9208/568
$$f(x)=a_1+a_3x+a_5x^2+\dots,\quad g(x)=a_2+a_4x+a_6x^2+\dots$$
とおく.このとき, 
$$
\begin{aligned}
f(x)-\dfrac{x}{1-x}g(x)&=a_1+(a_3-a_2)x+(a_5-a_4-a_2)x^2+\dots\\\\
&=1\\\\
g(x)-\dfrac{1}{1-x}f(x)-\dfrac{x}{1-x}g(x)&=(a_2-a_1)+(a_4-a_3-a_2-a_1)x+(a_6-a_5-a_4-a_3-a_2-a_1)x^2+\dots\\\\
&=0
\end{aligned}$$
第二式より, $f=(1-2x)g$ であるから, これを第一式に代入することで,
$$
\begin{aligned}
&f(x)=\frac{(1-2x)(1-x)}{1-4x+2x^2}\\\\
&g(x)=\frac{1-x}{1-4x+2x^2}
\end{aligned}$$
が成立. よって,$f(x),g(x)$ それぞれに $1-4x+2x^2 $ をかけるとそれぞれ $3,2$ 次以降の項が $0$ になることから $n\geq 6$ について, $a_n-4a_{n-2}+2a_{n-4}=0$ が分かる.
漸化式を母関数を用いて導出
https://onlinemathcontest.com/contests/omc225/editorial/9208/631
　正整数列 $\lbrace a_{n} \rbrace\_{n=1,2,\ldots}$ を以下のように定めます：

- $a_{1} = 1$．
- $n$ が偶数のとき，$a_{n} = a_{1} + a_{2} + a_{3} + \cdots + a_{n-1}$．
- $n$ が奇数のとき，$a_{n} = a_{2} + a_{4} + a_{6} + \cdots + a_{n-1}$．

　このとき，$\gcd(a_{n}, a_{n+4}) \geq 10^{15}$ をみたす最小の正整数 $n$ を求めてください．