Extended Fibonacci numbers P25832


Statement
 

pdf   zip

html

The well known Fibonacci numbers are defined recursively as follows: F0 = 0, F1 = 1, Fi = Fi−1 + Fi−2 for i ≥ 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) = [f0, f1, …] as f0 = a, f1 = b, fi = fi−1 + fi−2 for i ≥ 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 ≥ 3 where fi = n. For instance, for n = 2 there are exactly three such sequences: S(0, 1) = [0, 1, 1, 2, …], S(1, 0) = [1, 0, 1, 1, 2, …], and S(2, 0) = [2, 0, 2, 2, …].

Input

Input consists of several cases, each with a different natural number n between 1 and 106.

Output

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

Hint

Depending on your solution, Cassini’s identity could be useful: Fi−1 · Fi+1Fi2 = (−1)i.

Public test cases
  • Input

    2
    1
    3
    9
    10
    1000
    1000000
    

    Output

    3
    1
    4
    8
    10
    780
    773883
    
  • Information
    Author
    Salvador Roura
    Language
    English
    Official solutions
    C++
    User solutions
    C++
    Event
    Catorzè Concurs de Programació de la UPC - Final
    Date
    2016-09-21