　三倍角の公式より次が成り立つ．
$$4\cos^3\frac{\pi}{9}-3\cos\frac{\pi}{9}=\cos\frac{\pi}{3}=\frac{1}{2}$$
よって$\cos\dfrac{\pi}{9}$ は三次方程式 $8x^3-6x-1=0$ の解の一つである．
$x$ を $\dfrac{x-1}{2}$ と置き変えれば，$1+2\cos\dfrac{\pi}{9}$ は三次方程式 $x^3-3x^2+1=0$ の解の一つであることがわかる．

　$f(x):=x^3-3x^2+1$ とおく．
$$f(-1)=-3,\quad f(0)=1,\quad f\left(\frac{1}{\sqrt{2}}\right) = \frac{\sqrt{2}-2}{4}, \quad f(2)=-3,\quad f(3)=1$$
より，三次方程式 $f(x)=0$ は $(-1,0),\left(0,\dfrac{1}{\sqrt2}\right),(2,3)$ の範囲にそれぞれ実数解を少なくとも一つ持つ．
よって代数学の基本定理，また $1+2\cos\dfrac{\pi}{9}\gt 1$ と合わせれば三次方程式 $f(x)=0$ は実数解を $3$ つ持ち，それらを $\alpha,\beta,\gamma\~(\alpha\lt\beta\lt\gamma)$ とすれば次が成り立つ．
$$-1\lt\alpha\lt 0\lt\beta\lt \dfrac{1}{\sqrt2},\quad \gamma=1+2\cos\dfrac{\pi}{9}$$
さらに $f(-\alpha)=-2\alpha^3\gt 0$ に注意すれば $-\alpha=|\alpha|\lt\beta$ がわかるため，任意の正整数 $n$ について $0\lt\alpha^n+\beta^n\lt 1$ であることが示せる．
なおこれらの結論は微分を用いた議論によっても示される．

　$b_n=\alpha^n+\beta^n+\gamma^n$ とおく．
解と係数の関係より 
$$\alpha+\beta+\gamma=3,\quad\alpha\beta+\beta\gamma+\gamma\alpha=0,\quad\alpha\beta\gamma=-1$$
であるから，計算によって
$$b_1=3,\quad b_2=9,\quad b_3=24,\quad b_{n+3}=3b_{n+2}-b_n$$
が得られる．
これより明らかに任意の $n$ について $b_n$ は整数であるから，$0\lt\alpha^n+\beta^n\lt 1$ より $a_n$ は $b_n-1$ を $9$ で割ったあまりであることがわかる．
$b_n$ の初めの数項を $9$ で割ったあまりを計算すれば
$$\begin{array}{c|cccccccccc}
n&1&2&3&4&5&6&7&8&9&\cdots\\\\
\hline
b_n\bmod 9&3&0&6&6&0&3&3&0&6&\cdots
\end{array}
$$
となることから，$b_n$ を $9$ で割った余りは周期 $6$ で $3,0,6,6,0,3$ を繰り返すことが分かる.   ゆえに $a_n$ は周期 $6$ で $2,8,5,5,8,2$ を繰り返すため，求める値は
$$(2+8+5+5+8+2)\times166+2+8+5+5={\bf 5000}.$$
公式解説
https://onlinemathcontest.com/contests/omc172/editorial/4279
　正整数 $n$ に対し，$\Bigl(1+ 2\cos\dfrac{\pi}{9}\Bigr)^n$ の整数部分を $9$ で割った余りを $a_n$ とするとき，
$$a_1+a_2+\cdots+a_{1000}$$
を求めてください．