${ n }^{ 2 }$ and ${ 2 }^{ n }$

Lemma: $n^2+n+1$ divides $n^{2a} + n^a + 1$ as long as $a$ is not divisible by $3.$

Proof: Since $x^2+x+1$ is the minimal polynomial of $\omega,$ a primitive third root of unity , it is enough to note that $\omega^{2a} + \omega^a + 1 = 0.$ $\Box$

Now, to solve the problem, let $k$ be a nonnegative integer. Let $m = 2^k.$ Let $n = 2^m.$ Let $a = 2^{m-k},$ so that $ma=n.$ Then $n^{2a} + n^a + 1 = 4^{ma} + 2^{ma} + 1 = 4^n + 2^n + 1.$

By the lemma, then, since $a$ is not divisible by $3,$ $\frac{4^n+2^n+1}{n^2+n+1}$ is an integer. There are infinitely many $k,$ hence infinitely many $n.$

A slightly different approach to Patrick's...

For any $m \in \mathbb{N} \cup \{0\}$ , define $k = 2^{2^m-m}-1$ . Then $k+1$ is a power of $2$ , so is coprime to $3$ . Thus the map $u \mapsto 3u$ from $\mathbb{Z}_{k+1}$ to itself is bijective. For any positive integer $n$ , $\sum_{u=0}^k n^{3u} \; \equiv \; \sum_{u=0}^k n^{f(u)} \; \equiv \; \sum_{u=0}^k n^u \hspace{1cm} \pmod{n^{k+1}-1}$ so we deduce that $\sum_{u=0}^k n^{3u} \equiv \sum_{u=0}^kn^ u \; \equiv \; 0 \hspace{1cm} \pmod{\sum_{j=0}^k n^u}$ which implies that $\frac{\displaystyle\sum_{u=0}^k n^{3u} }{\displaystyle\sum_{u=0}^k n^u}$ is an integer. Now note that $(1 + n + n^2)\left(\sum_{u=0}^k n^{3u}\right) \; = \; \sum_{u=0}^{3k+2}n^u \; =\; \big(1 + n^{k+1} + n^{2k+2}\big) \left(\sum_{u=0}^k n^u\right)$ and hence we see that $\frac{n^{2k+2} + n^{k+1} + 1}{n^2 + n + 1} \;= \; \frac{\displaystyle\sum_{u=0}^k n^{3u} }{\displaystyle\sum_{u=0}^k n^u}$ is an integer. If we now put $n = 2^{2^m}$ then $n^{k+1} \; = \; 2^{(k+1)2^m} \; = \; 2^{2^{2^m}} \; = \; 2^n$ and hence we deduce that $\frac{4^n + 2^n + 1}{n^2 + n + 1}$ is an integer whenever $n = 2^{2^m}$ for any $m \in \mathbb{N}\cup\{0\}$ . Thus the answer is $\boxed{-777487}$ .

Observe that n=2 and n=4 and n=16 are solutions. Maybe every $n=2^{2^k}$ is?

Without a rigorous proof, I could see a pattern in the polynomial divisions below that made me quite confident that it would always come out for such n.

Observe that

• $n^{3k}/(n^2+n+1) = \sum_{t=-\infty}^{k}n^{3t-2}-n^{3t-3}$
• $n^{3k+1}/(n^2+n+1) = \sum_{t=-\infty}^{k}n^{3t-1}-n^{3t-2}$
• $n^{3k+2}/(n^2+n+1) = \sum_{t=-\infty}^{k}n^{3t}-n^{3t-1}$

Observe that the three powers of n in each row (e.g. $64, 32$ and $0$ ) have different remainders (mod 3), so that the infinite tails of their power series cancel out, and the division becomes finite.