The lost sequence P74753


Statement
 

pdf   zip

thehtml

As it is well known by the supporters of the series LOST, the following six numbers are keys in the Valenzetti equation, a mathematical formula to predict the end of humanity.

Dharma Iniciative, whose aim is to change the factors that would bring to the decline of humanity, has made the following program to generate the n first terms of what they call the lost sequence.

int f(int i) { if (i == 0) return -3; if (i == 1) return -1; if (i == 2) return 4; if (i == 3) return 8; if (i == 4) return 15; return f(i-5) + f(i-3) + f(i-1); } int main() { int n; while (cin >> n) { for (int i = 0; i < n; ++i) cout << f(i) << " "; cout << "..." << endl; } }

Unfortunately, this program is much too slow. Help Dharma Iniciative to save the world by writing an equivalent but much faster program.

Input

Input consists of a sequence of natural numbers between 0 and 45.

Output

Print the same as the given program.

Public test cases
  • Input

    8
    10
    

    Output

    -3 -1 4 8 15 16 23 42 ...
    -3 -1 4 8 15 16 23 42 66 104 ...
    
  • Information
    Author
    Jordi Petit
    Language
    English
    Translator
    Carlos Molina
    Original language
    Catalan
    Other languages
    Catalan
    Official solutions
    C++
    User solutions
    C++ Python