Extended Fibonacci numbers P25832

The well known Fibonacci numbers are defined recursively as follows: $F_0 = 0$, $F_1 = 1$, $F_i = F_{i-1} + F_{i-2}$ for $i \ge 2$. The first Fibonacci numbers are 0, 1, 1, 2, 3, 5, 8, 13, 21, ….

Let us generalize the Fibonacci numbers. For every pair of natural numbers $a$ and $b$, define the sequence $S(a, b) = [f_0, f_1, \dots]$ as $f_0 = a$, $f_1 = b$, $f_i = f_{i-1} + f_{i-2}$ for $i \ge 2$. Note that $S(0, 1)$ is the traditional Fibonacci sequence.

You are given a natural number $n$. Please compute how many pairs $(a, b)$ exist such that $S(a, b)$ has a $i \ge 3$ where $f_i = n$. For instance, for $n = 2$ there are exactly three such sequences: $S(0, 1) = [0, 1, 1, 2, \dots]$, $S(1, 0) = [1, 0, 1, 1, 2, \dots]$, and $S(2, 0) = [2, 0, 2, 2, \dots]$.

Input

Input consists of several cases, each with a different natural number $n$ between 1 and $10^6$.

Output

For every $n$, print the number of pairs $(a, b)$ such that $n$ appears at a position $i \ge 3$ in $S(a, b)$.

Hint

Depending on your solution, Cassini’s identity could be useful: $F_{i-1} \cdot F_{i+1} - F_i^2 = (-1)^i$.