Sequence like Fibonacci

If the prime factorization of a number $n$ is

$\large n = p_1^{\alpha_1}p_2^{\alpha_2}...p_k^{\alpha_k}$

where $p_i$ are distinct primes, then $n$ is a perfect power $x^y$ if and only if $\gcd(\alpha_1, \alpha_2,..., \alpha_k) > 1$ . If $\gcd(\alpha_1, \alpha_2,..., \alpha_k) = 1$ , then $n$ cannot be expressed as a perfect power. This is easier to see with an example:

Suppose that $n = p^iq^i$ , where $p$ and $q$ are distinct primes. If $\gcd(i, j) = k > 1$ , then $n$ can be expressed as $n = p^iq^j = p^{fk}q^{gk}$ where $\gcd(f, g) = 1$ . Hence, $n = \left(p^fq^g\right)^k$ . Letting $m = p^fq^g$ , we have $n = \left(p^fq^g\right)^k = m^k$ . How about a more concrete example?

Let's see if $1728$ can be expressed as a perfect power. Its prime factorization is $3^3 \cdot 2^6$ , and we notice that $\gcd(3, 6) = 3 > 1$ . Rewriting that product as $\left(3^1 \cdot 2^2\right)^3$ , we see that $1728$ is indeed $12^3$ .

Now, let's examine the first few terms of the sequence.

$\displaystyle \begin{aligned} & a_1 = 2 = 2^1 \\ & a_2 = 3 = 3^1 \\ & a_3 = 6 = 2^1 3^1 \\ & a_4 = 18 = 2^1 3^2 \\ & a_5 = 108 = 2^2 3^3 \\ & a_6 = 1944 = 2^3 3^5 \\ & a_7 = 209952 = 2^5 3^8 \\ & a_8 = 408146688 = 2^8 3^{13} \\ & \cdot \\ & \cdot \\ & \cdot \end{aligned}$

We can write a general term for $a_n$ :

$\large a_n = \begin{cases} 2, n = 1 \\ 3, n = 2 \\ 2^{F_{n - 2}} \ 3^{F_{n - 1}}, n \geq 3 \end{cases}$

where $F_k$ is the $k^{\text{th}}$ Fibonacci with $F_1 = 1$ and $F_2 = 1$ . Where'd the Fibonacci numbers come from? They result in multiplying successive powers of $2$ and $3$ , with powers adding up due to exponent rules.

Now let's prove that any two consecutive Fibonacci numbers are coprime using induction.

We have $F_1 = 1, F_2 = 1, F_3 = 2,…$ , so $\gcd(F_1, F_2) = 1$ . Hence, the base case $P(1)$ is true.

Now suppose that $\gcd(F_n, F_{n+1}) = 1$ ; we will show that $\gcd(F_{n+1}, F_{n+2}) = 1$ . Consider $\gcd(F_{n+1}, F_{n+2}) = \gcd(F_{n+1}, F_{n+1} + F_n)$ . Then $\gcd(F_{n+1}, F_{n+1} + F_n) = \gcd(F_{n+1}, F_n) = 1$ , because $\gcd(a, a + b) = \gcd(a, b)$ . We have proven that $P(n + 1)$ is true.

Hence, $\gcd(F_n, F_{n+1}) = 1 \ \forall \ n > 0$ .

We can see that $a_1 = 2$ and $a_2 = 3$ cannot be expressed in the form $x^y$ for positive integers $x, y$ with $y > 1$ . Since consecutive Fibonacci numbers $F_{n - 2}$ and $F_{n - 1}$ will always be coprime for $n \geq 3$ , $a_n = 2^{F_{n - 3}} \ 3^{F_{n - 2}}$ cannot be expressed as a perfect power $x^y$ .

Our answer is $\boxed{0}$ .