Unpredictable u's

Notice that

$u_{n+2}=(u_{n+1}-1)(u_n-1)+1$

Using this, we get that

$u_k-1=(u_{k-1}-1)(u_{k-2}-1)$

Plugging this into the original recurrence, we get that

$u_{n+2}=(u_n-1)(u_{n-1}-1)(u_n-1)+1=(u_{n}-1)^2.(u_{n-1})+1$

We can do that again:

$u_{n+2}=((u_{n-1}-1)(u_{n-2}-1))^2.(u_{n-1})+1=(u_{n-1}-1)^3.(u_{n-2}-1)^2+1$

Seeing the pattern?There is a recurrence relation in the exponents, a quite famous one.That's right- the Fibonacci sequence!It is easy to see that every time we substitute using the formula, we would have to sum two powers for one of the $u_i-1$ and leave the first power to $u_{i-1}-1$ .That means that

$u_{n+2}=(u_{n-j+1}-1)^{F_{j+2}}.(u_{n-j}-1)^{F_{j+1}}+1$

Now plugging $j=n-1$ we would get

$u_{n+2}=(u_2-1)^{F_{n+1}}.(u_1-1)^{F_n}+1$

But we know that $u_2=3,u_1=2$ .So

$u_{n+2}=2^{F_{n+1}}+1$

So the sequence is

$u_{n+1}=2^{F_n}+1$

But this number is prime only for $F_n$ being a power of 2.But it is well known that the only Fibonacci powers of two are 1,2 and 8!This fact is not hard to prove, just look mod 16 and mod 3.But then we still need to count $u_1=2$ .

Thus our answer is $2+3+5+257=\boxed{267}$

Note:This problem is not original.While struggling to find a solution, I posted the same problem, but with the wrong answer.Sorry if you lost your ranks and thank you Finn for telling me there is an error :D

Note that the recurrence is equivalent to $u_{n+2} - 1 = (u_{n+1} - 1)(u_n - 1)$ . Thus consider the sequence $a_n = u_n - 1$ ; we have $a_1 = 1, a_2 = 2$ , and $a_{n+2} = a_{n+1} a_n$ . Consider again the sequence $b_n = \log_2 a_n$ . We have $b_1 = 0, b_2 = 1$ , and $b_{n+2} = b_{n+1} + b_n$ . Thus $b_{n+1}$ is the Fibonacci sequence; letting $F_1 = F_2 = 1$ and $F_{n+2} = F_{n+1} + F_n$ , we have $b_n = F_{n-1}$ , or $a_n = 2^{F_{n-1}}$ , or $u_n = 2^{F_{n-1}} + 1$ .

Now observe that if $k \ge 1$ has an odd prime factor $d$ , then $2^k + 1$ is composite; this is easy to prove, because $2^{k/d} + 1$ is a divisor. (Use $a^n + b^n = (a+b)(a^{n-1} - a^{n-2}b + a^{n-3}b^2 - \ldots + b^{n-1})$ for odd $n$ , with $a = 2^{k/d}, b = 1$ .) Thus if $F_{n-1}$ has an odd prime factor, $u_n$ is not prime, with the exception at $n = 1$ , since $F_0 = 0$ . Thus we're looking for $F_{n-1}$ that is a power of two (any other number leads to $F_{n-1}$ having an odd prime factor).

Now, it's easy to see that $F_1 = 1, F_2 = 1, F_3 = 2, F_6 = 8$ . Beyond this, all powers of two in the Fibonacci sequence must be at least 16; thus, taking modulo 16, it must be 0. The Fibonacci sequence modulo 16 repeats with period 24, and it is congruent to 0 every 12th term:

1, 1, 2, 3, 5, 8, 13, 5, 2, 7, 9, 0 , 9, 9, 2, 11, 13, 8, 5, 13, 2, 15, 1, 0 , 1, 1, ...

However, taking the Fibonacci sequence modulo 3, it repeats with period 8 and is congruent to 0 every 4th term:

1, 1, 2, 0 , 2, 2, 1, 0 , 1, 1, ...

(They both repeat because we showed the sequence comes back to 1, 1, and since the Fibonacci sequence only depends on the previous two terms, we can be sure that the rest of the sequence matches the start.)

Now, we see that whenever $F_{n-1}$ is divisible by 16, it is also divisible by 3. Thus it cannot be a power of two. Hence there is no power of two greater than 8 in the Fibonacci sequence.

Finally, we check that each of these candidates gives a prime:

• $F_0 = 0$ (exception to the odd prime factor one): $a_1 = 2^0 + 1 = 2$ is prime
• $F_1 = F_2 = 1$ (only counted once): $a_2 = a_3 = 2^1 + 1 = 3$ is prime
• $F_3 = 2$ : $a_4 = 2^2 + 1 = 5$ is prime
• $F_6 = 8$ : $a_7 = 2^8 + 1 = 257$ is prime

Thus their sum is $2 + 3 + 5 + 257 = \boxed{267}$ .

Note that we could have used a theorem by Y. Bugeaud, M. Mignotte, and S. Siksek, that proved that 8 and 144 are the only nontrivial perfect powers. Thus the only powers of two that appear in the Fibonacci sequence are 1 (trivial perfect power), 2 (not a perfect power), and 8, because all other powers of two besides 1 and 2 must be perfect powers by definition. But this is a much more difficult theorem.