Super Duper Powered Sum

We first try to evaluate $\alpha^{2^n} + \beta^{2^n}$ for small $n$ to determine a pattern

It's trivial by Vieta's formula that $\alpha + \beta = 1, \alpha \beta = -3$

Let $a_n = \alpha^{2^n} + \beta^{2^n}$ , then $a_0 = 1$

$a_1 = \alpha^{2^1} + \beta^{2^1} = \left ( \alpha + \beta \right )^2 - 2 (\alpha \beta ) = 1^2 - 2(-3) = 7$

$a_2 = \alpha^{2^2} + \beta^{2^2} = \left ( \alpha^2 + \beta^2 \right )^2 - 2 (\alpha \beta )^2 = 7^2 - 2(-3)^2 = 31$

$a_3 = \alpha^{2^3} + \beta^{2^3} = \left ( \alpha^4 + \beta^4 \right )^2 - 2 (\alpha \beta )^4 = 31^2 - 2(-3)^4 = 799$

It become obvious that we have a recurrence relation $a_0 = 1, a_1 = 7$ , and for $n = 2,3,4, \ldots$ that $a_n = (a_{n-1})^2 - 2 \cdot 3^{2^{n-1}}$

Since we're only interested in the last three digits, we find $\text{modulo } 1000$ , that is $a_n = \left ( (a_{n-1})^2 - 2 \cdot 3^{2^{n-1}} \right ) \bmod {1000}$

Notice that there is a term raised to the power of another power, so we can simplify the calculation by appealing to Euler Totient Function because $\text{gcd}(3,1000) = 1$ , thus $\phi(1000) = 1000(1- \frac {1}{2})(1 - \frac {1}{5}) = 400$ , we augment $a_n$ to

$\large a_n = \left ( (a_{n-1})^2 - 2 \cdot 3^{2^{n-1} \bmod{400}} \right ) \bmod {1000}$

By python

lookup = {0:1,1:7}
def ABC(x):
    if x not in lookup:
        fx = ((ABC(x-1))**2 - 2*(3**((2**(x-1)) % 400))) % 1000
        lookup[x]= fx
    return lookup[x]
print ABC(999)

Output

799