21
3
Fibonacci Numbers
Fibonacci Numbers start with f(1) = 1
and f(2) = 1
(some includes f(0) = 0
but this is irrelevant to this challenge. Then, for n > 2
, f(n) = f(n-1) + f(n-2)
.
The challenge
Your task is to find and output the n
-th positive number that can be expressed as products of Fibonacci numbers. You can choose to make it 0-indexed or 1-indexed, whichever suits you better, but you must specify this in your answer.
Also, your answer must compute the 100th term in a reasonable time.
Testcases
n result corresponding product (for reference)
1 1 1
2 2 2
3 3 3
4 4 2*2
5 5 5
6 6 2*3
7 8 2*2*2 or 8
8 9 3*3
9 10 2*5
10 12 2*2*3
11 13 13
12 15 3*5
13 16 2*2*2*2 or 2*8
14 18 2*3*3
15 20 2*2*5
16 21 21
17 24 2*2*2*3 or 3*8
18 25 5*5
19 26 2*13
20 27 3*3*3
100 315 3*5*21
In the test case why are some of them n=result, whereas for 7 and above they are not equal. Maybe I don't understand the question. But I just want to check – george – 2016-06-18T10:03:59.050
1
7
cannot be expressed as the product of Fibonacci numbers. Therefore, the1
st required number is1
, the2
nd is2
, ..., the6
th is6
, but the7
th is8
. – Leaky Nun – 2016-06-18T10:58:14.210Ah of course, that makes sense – george – 2016-06-18T11:13:11.033
Should you print all the ways in making a number. For example 16 has two ways, or can you just output one? – george – 2016-06-18T14:00:28.337
3@george I believe the "
corresponding product
" is just for clarification. Your code only needs to output the "result
". – trichoplax – 2016-06-18T14:19:41.100The terms of this sequence are derived by multiplying exactly two Fibonacci numbers, or by multiplying any number of Fibonacci terms? The OEIS sequence doesn't match the sequence shown. – Joe – 2016-06-22T17:39:05.000