The lost sequence P74753
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