The answer is 7, achieved by the sequence 5, 2, 7, 9, 16, 25, 41. Suppose there exist a sequence with length 8 satisfying the condition. Odd prime powers cannot be three consecutive terms due to parity, so there must be at least two terms that are power of 2. Let $2^a < 2^b$ are two terms of the sequence. If $2^a$ and $2^b$ are consecutive terms, all the terms are even, hence all the form of $2^k$. Then we cannot make the sequence have more than three terms, contradiction. Otherwise, there should be exactly two terms between $2^a$ and $2^b$ (because of parity issue). Let $2^a$, $p^s$, $q^t$, $2^b$ be four consecutive terms of the sequence where $p$, $q$ are odd primes. If $a \geq 2$, we have $4\;\vert\;2^a = q^t - p^s$ and $4\;\vert\;2^b = q^t + p^s$, so $4\;\vert\;2q^t$, contradiction. Hence $a=1$. Now we divide into three cases. Note that the equation $\vert 2^x - 3^y\vert = 1$ only has solutions $(x, y) = (1, 1), (2, 1), (3, 2)$ over positive integers. Case 1. $p^s\equiv 0\;(mod\;3)$ In this case $p=3$, and we have $2^b = q^t + p^s = 2p^s + 2 \Leftrightarrow 2^{b-1} = 3^s + 1$. So $s=1$ and $b=3$, then the sequence cannot have more than 5 terms. (Just compute, we have ...1, 2, 3, 5, 8, 13, 21, ... and 1, 21 isn't a prime power.) Case 2. $p^s\equiv 1\;(mod\;3)$ $q^t = p^s + 2 \equiv 0\;(mod\;3)$ so $q=3$, and we have $2^b = q^t + p^s = 2q^t - 2 \Leftrightarrow 2^{b-1} = 3^t - 1$. So $(t, b) = (1, 2)$ or $(t, b) = (2, 4)$. If $(t, b) = (1, 2)$, $p^s = q^t - 1 = 3^1 - 1 = 2$, contradiction. If $(t, b) = (2, 4)$, we have the sequence to be ...-3, 5, 2, 7, 9, 16, 25, 41, 66... and -3, 66 isn't a prime power, so the sequence cannot have more than 8 terms. Case 3. $p^s\equiv 2\;(mod\;3)$ $2^b = q^t + p^s = 2p^s + 2 \equiv 0\;(mod\;3)$, contradiction. We've exhausted all cases, so we're done.

mjk20016 wrote: The answer is 5, achieved by the sequence 2, 3, 5, 8, 13 or 2, 7, 9, 16, 25. The answer is not $5$.

GorgonMathDota wrote: mjk20016 wrote: The answer is 5, achieved by the sequence 2, 3, 5, 8, 13 or 2, 7, 9, 16, 25. The answer is not $5$. Sorry, I suddenly thought 41 isn't a prime power Now edited

mjk20016 wrote: The answer is 6, achieved by the sequence 2, 7, 9, 16, 25, 41. Why don't you extend it to $5, 2, 7, 9, 16, 25, 41$

RevolveWithMe101 wrote: mjk20016 wrote: The answer is 6, achieved by the sequence 2, 7, 9, 16, 25, 41. Why don't you extend it to $5, 2, 7, 9, 16, 25, 41$ Oops. There was an additional flaw Edited now Maybe now the solution would be complete..

We know that $5, 2, 7, 9, 16, 25, 41$ is a sequence that satisfies the conditions of the problem for $n=7$. We claim that there isn't a sequence that satisfies for any $n\geq8$, and we will prove it by contradiction. Case $1$, $a_1$ and $a_2$ are both even Suppose $a_1=2^x$ and $a_2=2^y$. We will have $a_4=2^x+2^{y+1}$ Since $a_4$ can't have an odd factor, then $x=y+1$. We will have $a_3=2^x+2^y=2^{y+1}+2^y=3.2^y$, a contradiction since $a_3$ can't have an odd factor. Case $2$, $a_1$ and $a_2$ are both odd We know that $a_6=3a_1+5a_2=3(a_1+a_2)+2a_2$ can't have an odd factor. We also know that $a_3=a_1+a_2$ can be written in the form $2^x$ Since $3$ and $a_2$ are both odd, then $a_1+a_2=2$, a contradiction since $a_1,a_2>2$ Case $3$, $a_1$ is even and $a_2$ is odd Suppose $a_1=2^x$ We know that $a_7=5a_1+8a_2$ can't have an odd factor Since $5$ and $a_2$ are both odd, then $a_1=8$ We know that $a_4=a_1+2a_2=8+2a_2=2(4+a_2)$ Since $a_2$ is odd, then $4+a_2$ is also odd. That means $a_4$ will have an odd factor, a contradiction. Case $4$, $a_1$ is odd and $a_2$ is even We can use a similar technique to the one that we used in Case $3$ We have proven that when $n\geq8$, each of the $4$ cases led to a contradiction.

I hope this work. (You can tell me if there is something wrong) We claim that the largest n is 7 Lower bound : consider sequence $ 5,2,7,9,16,25,41 $ satisfies the conditions So $ n \geq 7 $ Upper bound : We assume that there is a sequence with length $ 8 $ $ a,b,a+b,a+2b,2a+3b,3a+5b,5a+8b,8a+13b $ It’s easy to see that if $a $and $b $are even number. $a+b $isn’t perfect power. Now we consider 3 cases 1. $a $ and $b $are odd number Let $ a+b = 2^m $ and $ 3a+5b = 2^n $ So $ a+2b = 2^{n-1} - 2^{m-1} $ But $a+2b $ is odd number So $ m=1 \rightarrow a+b=2 $ contradiction 2. $a $ is odd number and $b $ is even number We do the same thing with case 1 and so $ b=2 $ Let $ 2a+6 = 2^m $ and $ 8a+26 = 2^n $ So $ 3a+10 = 2^{n-1} - 2^{m-1} $ But $3a+10 $ is odd number then $m=1$ contradiction 3. We can do same thing with case 2