OMC194(E)

　$N = 10^5$ とする．
　$b_n = 3n + 2 - a_n$ とすると，問題の条件は以下のように書き換えられる． $$0\leq b_n\leq n+1,\quad b_n\leq b_{n+1}$$ ただし，例外として $b_1 = 3$ となり得ることに注意せよ．

• $b_1\lt 3$ の場合
  　座標平面上で，$(1,0)$ から $(N+1,N+2)$ へ隣り合う格子点を通って行く最短経路のうち，領域 $y \le x+1$ 内の点のみを通るものを一つ選び，$i = 1,2,\ldots,N$ について，その経路の中で最も最初に $x$ 座標が $i + 1$ になった点の $y$ 座標を $b_i$ とすると，得られた数列 $\{b_n\}$ は上の条件を満たす．また，上の条件を満たす $\{b_n\}$ について， $$(1,0),\quad (1,b_1),\quad (2,b_1),\quad (2,b_2),\quad (3,b_2),\quad \ldots,\quad (N+1,b_{N}),\quad (N+1,N+2)$$ を通るような $(1,0)$ から $(N+1,N+2)$ への最短経路は，常に領域 $y\le x+1$ 内を通る．従って，$\{b_n\}$ の数とこのような経路の数は等しい．このような経路の数は，$(-1,0)$ から $(N+1,N+2)$ まで領域 $y\le x+1$ 内を通って行く最短経路のうち，$(0,1)$ を通らない経路の数と一致するので，Catalan数 $C_n = \dfrac{2n!}{(n+1)!\ n!}$ を用いて $C_{N+2} - C_{N+1}$ と表せる．

• $b_1 = 3$ の場合
  　$b_1\le b_2 \le 3$ より $b_2 = 3$ であることに注意すると，上の場合と同様にして，$(2,3)$ から $(N+1,N+2)$ へ領域 $y\le x+1$ 内を通っていく最短経路の数を求めればよく，これは $C_{N-1}$ である．

　以上より， $$X = C_{N+2} - C_{N+1} + C_{N-1} = \frac{(2N-2)!(N+1)(49N^2 + 5N - 6)}{(N-1)!(N+3)!}$$ であるから，$11$ 桁の素数は $49N^2 + 5N - 6$ の約数である． $49N^2 + 5N - 6 = 2\times3\times81666749999$ と素因数分解されるので，$\bf81666749999$ が求める答えである．