This was a really interesting problem! I don’t think I’ve ever solved an infinitely polynomial series like this before so I definitely learned something new. Which is super awesome.
I did some research about how to solve these infinite polynomial series. I found that $\sum_{n=0}^\infty x^n=\frac1{1-x}$. That didn’t apply here, but what was interesting was how this solution was derived. I then used a similar method to figure out the answer to this $A(x)$. Let $F(n)$ be the Fibonacci sequence with $F(0)=0$, $F(1)=1$, and $F(2)=1$:
\[A(x)=\displaystyle\sum_{n=0}^\infty F(n)\,x^n=x+x^2+2x^3+3x^4+5x^5+8x^6+\dots\]Multiply each side by $x$:
\[x\,A(x)=x^2+x^3+2x^4+3x^5+5x^6+\dots\]Add $A(x)$ and $x\,A(x)$ together
\[(x+1)\,A(x)=x+2x^2+3x^3+5x^4+8x^5+13x^6+\dots\]Multiply each side by $x$ again:
\[x(x+1)\,A(x)=x^2+2x^3+3x^4+5x^5+8x^6+\dots{}=A(x)-x\]Rearranging:
\[A(x)\,x^2+\left(A(x)+1\right)x-A(x)=0\]And since we know $A(x)$ and are solving for $x$, we can use the quadradic formula to solve for $x$. This means that for $x$ to be rational, then the determinant must be a perfect square. This allows us to find all the values of $A(x)$ for which $x$ is rational.
Since I knew the value of $A(x)$ would probably be pretty large, I looked for a pattern in the values of the determinant for which $x$ was rational. These numbers followed the pattern in https://oeis.org/A033889. It was from here that I was able to get the answer.
def fib(n):
if n < 3:
return 1
f1 = f2 = 1
for _ in range(n - 2):
f1, f2 = f2, f1 + f2
return f2
def solve(n):
d = fib(4*n + 1)
return int((5*d**2 - 4)**0.5 - 1) // 5
if __name__ == '__main__':
import sys
n = eval(sys.argv[1])
print(solve(n))
import pytest
from problem import solve
_test_solve = (
(1, 2),
(10, 74049690),
)
@pytest.mark.parametrize('n,expect', _test_solve)
def test_solve(n, expect):
assert expect == solve(n)