[Question]
  [
# 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
```
# References
* [Obligatory OEIS A065108](https://oeis.org/A065108)
  
[Answer]
# [Jelly](http://github.com/DennisMitchell/jelly), ~~26~~ ~~24~~ ~~23~~ 21 [bytes](https://github.com/DennisMitchell/jelly/wiki/Code-page)
```
ÆDf÷ß€FðḊ¡
1ç#2+Ð¡1¤Ṫ
```
[Try it online!](http://jelly.tryitonline.net/#code=w4ZEZsO3w5_igqxGw7DhuIrCoQoxw6cjMivDkMKhMcKk4bmq&input=&args=MTAw)
### How it works
```
1ç#2+Ð¡1¤Ṫ  Main link. Argument: n (integer)
        ¤   Combine the three links to the left into a niladic chain.
   2          Set the left argument and the return value to 2 (third positive
              Fibonacci number).
       1      Yield 1 (second positive Fibonacci number).
    +Ð¡       Compute the sum of the return value and right argument, replacing the
              return value with the sum and the right argument with the previous
              return value.
              Do this n times, collecting all return values in a list.
              This returns A, the first n Fibonacci numbers greater than 1.
1             Set the return value to 1.
 ç#           Call the helper link with left argument k = 1, 2, 3... and right
              argument A = [2, 3, 5...] until n of them return a truthy value.
              Collect the matches in a list.
           Ṫ  Tail; extract the last (n-th) match.
ÆDf÷ß€FðḊ¡    Helper link. Left argument: k. Right argument: A
        Ḋ     Dequeue; yield r := [2, ..., k].
       ð ¡    If r in non-empty, execute the chain to the left. Return k otherwise.
ÆD              Yield the positive divisors of k.
   ÷            Divide k by all Fibonacci numbers in A.
  f             Filter; keep divisors that belong to k÷A, i.e., all divisors
                d for which k÷d belongs to A.
    ß€          Recursively call the helper link for each kept divisor d, with left
                argument d and right argument A.
      F         Flatten the result, yielding a non-empty array iff any of the
                recursive calls yielded a non-empty array or a number.
                If the left argument is 1, the helper link returns 1, so the
                array will be non-empty if the consecutive divisions by Fibonacci
                numbers eventually produced a 1.
```
[Answer]
# Julia, 79 bytes
```
!k=any(i->√(5i^2+[4,-4])%1∋k%i<!(k÷i),2:k)^~-k
<|(n,k=1)=n>0?n-!k<|-~k:~-k
```
[Try it online!](http://julia.tryitonline.net/#code=IWs9YW55KGktPuKImig1aV4yK1s0LC00XSklMeKIi2slaTwhKGvDt2kpLDI6aylefi1rCjx8KG4saz0xKT1uPjA_bi0hazx8LX5rOn4tawoKZm9yIG4gaW4gWzE6MjA7MTAwXQogICAgQHByaW50ZigiJTNkOiAlM2RcbiIsIG4sIDx8KG4pKQplbmQ&input=)
### Background
In [Advanced Problems and Solutions, H-187: Fibonacci is a square](http://www.fq.math.ca/Scanned/10-4/advanced10-4.pdf), the proposer shows that
![Fibonacci/Lucas identity](https://i.stack.imgur.com/NN5DR.png)
where **Ln** denotes the **n**th [Lucas number](https://en.wikipedia.org/wiki/Lucas_number), and that – conversely – if
![converse Fibonacci/Lucas identity](https://i.stack.imgur.com/yB3Qn.png)
then **n** is a Fibonacci number and **m** is a Lucas number.
### How it works
We define the binary operator `<|` for our purposes. It is undefined in recent versions of Julia, but still recognized as an operator by the parser.
When called with only one argument (**n**), `<|` initializes **k** as **1**. While **n** is positive, it subtracts **!k** (**1** if **k** is a product of Fibonacci numbers, **0** if not) from **n** and recursively calls itself, increments **k** by **1**. Once **n** reaches **0**, the desired amount of products have been found, so `<|` returns the previous value of **k**, i.e., **~-k = k - 1**.
The unary operator `!`, redefined as a test for Fibonacci number products, achieves its task as follows.
* If **k = 1**, **k** is a product of Fibonacci numbers. In this case, we raise the return value of `any(...)` to the power **~-k = k - 1 = 0**, so the result will be **1**.
* If **k > 1**, the result will be the value of `any(....)`, which will return **true** if and only if the predicate `√(5i^2+[4,-4])%1∋k%i<!(k÷i)` returns **true** for some integer **i** such that **2 ≤ i ≤ k**.
The chained conditions in the predicate hold if `k%i` belongs to `√(5i^2+[4,-4])%1` and `k%i` is less than `!(k÷i)`.
	+ `√(5i^2+[4,-4])%1` takes the square root of **5i2 + 4** and **5i2 - 4** and computes their residues modulo **1**. Each modulus is **0** if the corresponding number is a perfect square, and a positive number less than **1** otherwise.
	
	
	Since `k%i` returns an integer, it can only belong to the array of moduli if **k % i = 0** (i.e., **k** is divisible by **i**) and at least one among **5i2 + 4** and **5i2 - 4** is a perfect square (i.e., **i** is a Fibonacci number).
	+ `!(k÷i)` recursively calls **1** with argument **k ÷ i** (integer division), which will be greater than **0** if and only if **k ÷ i** is a product of Fibonacci numbers.
By induction, **!** has the desired property.
[Answer]
## Python, 90 bytes
```
f=lambda n,a=2,b=3:n<2or n%a<f(n/a)or n-a>0<f(n,b,a+b)
g=lambda k,n=1:k and-~g(k-f(n),n+1)
```
The main function `g` outputs the `k`th Fibonacci product, 1-indexed. It computes `g(100)` as `315` almost instantly. It goes so with a general recursive recipe of counting up numbers `n` looking for `k` instances that satisfy the function `f`. Each such instance lowers the required count `k` until it reaches `0`.
The auxiliary function `f` tests a number for being a Fibonacci product. It recursively generates the Fibonacci numbers in its optional arguments `a` and `b`. It outputs "yes" if any of the following is true:
* `n<2`. This implies `n==1`, the trivial product)
* `n%a<f(n/a)`. This requires `n%a==0` and `f(n/a)==True`, i.e. that `n` is a multiple of the Fibonacci number `a`, and removing this factor of `a` still yield a Fibonacci product.
* `n-a>0<f(n,b,a+b)`, equivalent to `n>a and f(n,b,a+b)`. Checks that the current Fibonacci number being tested isn't at least `n`, and some greater Fibonacci number works. Thanks to Dennis for 2 saving bytes using the inequality short-circuit instead of `and`.
The function `g` can be one byte shorter as
```
lambda k:filter(f,range(k*k+1))[k]
```
if `g(k)` is always at most `k*k`, which I'm not sure is asymptotically true. A bound of `2**k` suffices, but then `g(100)` takes too long. Maybe instead the recursive of `g` can be done in `f`.
[Answer]
# [Perl 6](http://perl6.org), ~~95~~ 93 bytes
```
~~{(1..\*).grep({$/=$\_;map {->{$/%$\_||($//=$\_);$/}...\*!%%$\_;0},reverse 2,3,&[+]...\*>$\_;2>$/})[$\_]}~~
{(1..*).grep({$/=$_;map {->{$/%$_||($//=$_);$/}...*%$_;0},reverse 2,3,&[+]...*>$_;2>$/})[$_]}
```
( 0 based index )
### Test:
```
my &fib-prod = {(1..*).grep({$/=$_;map {->{$/%$_||($//=$_);$/}...*%$_;0},reverse 2,3,&[+]...*>$_;2>$/})[$_]}
say fib-prod 0 ..^ 20;
# (1 2 3 4 5 6 8 9 10 12 13 15 16 18 20 21 24 25 26 27)
say time-this { say fib-prod 100 -1; };
# 315
# 1.05135779
sub time-this (&code) {
  my $start = now;
  code();
  now - $start;
}
```
### Explanation:
```
{
  (1..*).grep(
    {
      $/ = $_; # copy the input ($_) to $/
      map { # map used just for side effect
        ->{
          $/ % $_    # if $/ is divisible by the current fib factor
        ||
          ($/ /= $_) # divide it out once
        ;
          # return the current value in $/
          $/
        }
        ... # repeat until that returns:
        * !%% $_ # something that is not divisible by the current fib factor
        ;0
      },
      # the possible fibonacci factors plus one, reversed
      # ( the extra is to save one byte )
      reverse 2,3,&[+] ... *>$_;
      # is the end result of factoring equal to 1
      # ( for the grep above )
      2 > $/
    }
  )[ $_ ] # get the value at 0-based index
}
```
[Answer]
# Python 3, ~~175~~ ~~170~~ 148 bytes
*Thanks to @Dennis for -22 bytes*
```
j=x=int(input())
y=1,1
exec('y+=y[-2]+y[-1],;'*x)
i=c=0
while c<x:
    if j>=x:j=0;i+=1;t=i
    if t%y[~j]<1:t/=y[~j];j-=1
    if t<2:c+=1;j=x
    j+=1
print(i)
```
Takes input from STDIN and prints to STDOUT. This is one-indexed. Computing the 100th term takes roughly a tenth of a second.
**How it works**
```
j=x=int(input())                Get term number x from STDIN and set Fibonacci number index
                                j to x to force initialisation of j later 
y=1,1                           Initialise tuple y with start values for Fibonacci sequence
exec('y+=y[-2]+y[-1],;'*x)      Compute the Fibonacci sequence to x terms and store in y
i=c=0                           Initialise test number i and term counter c
while c<x:                      Loop until x th term is calculated
    if j>=x:j=0;i+=1;t=i        Initialise Fibonacci number index j, increment i and
                                initialise temp variable t for looping through all j for
                                some i. Executes during the first pass of the loop since
                                at this point, j=x
    if t%y[~j]<1:t/=y[~j];j-=1  Find t mod the j th largest Fibonacci number in y and if no
                                remainder, update t by dividing by this number.
                                Decrementing j means that after a later increment, no
                                change to j occurs, allowing for numbers that are 
                                divisible by the same Fibonacci number more than once by
                                testing again with the same j
    if t<2:c+=1;j=x             If repeated division by ever-smaller Fibonacci numbers
                                leaves 1, i must be a Fibonacci product and c is
                                incremented. Setting j equal to x causes j to be reset
                                to 0 during the next loop execution
    j+=1                        Increment j
print(i)                        i must now be the x th Fibonacci product. Print i to STDOUT
```
[Try it on Ideone](http://ideone.com/gpUFCK)
[Answer]
# Python 2, ~~120~~ 107 bytes
```
g=lambda k:1/k+any(k%i==0<g(k/i)for i in F)
F=2,3;k=0;n=input()
while n:F+=F[k]+F[-1],;k+=1;n-=g(k)
print k
```
Test it on [Ideone](http://ideone.com/MjvRR5).
### How it works
We initialize **F** as the tuple **(2, 3)** (the first two Fibonacci number greater than **1**), **k** as **0** and **n** as an integer read from STDIN.
While **n** is positive, we do the following:
* Append the next Fibonacci number, computed as **F[k] + F[-1]**, i.e., the sum of the last two elements of **F** to the tuple **F**.
* Increment **k**.
* Subtract **g(k)** from **n**.
**g** returns **1** if and only if **k** is a product of Fibonacci numbers, so once **n** reaches **0**, **k** is the **n**th Fibonacci number and we print it to STDOUT.
**g** achieves its purpose as follows.
* If **k** is **1**, it is a product of Fibonacci numbers, and `1/k` makes sure we return **1**.
* If **k** is greater than **1**, we call `g(k/i)` recursively for all Fibonacci numbers **i** in **F**.
`g(k/i)` recursively tests if **k / i** is a Fibonacci number product. If `g(k/i)` returns **1** and **i** divides **k** evenly, **k % i = 0** and the condition `k%i<g(k/i)` holds, so **g** will return **1** if and only if there is a Fibonacci number such that **k** is the product of that Fibonacci number and another product of Fibonacci numbers.
[Answer]
# JavaScript (ES6), 136
Quite slow golfed this way, computing term 100 in about 8 seconds in my PC.
```
(n,F=i=>i>1?F(i-1)+F(i-2):i+1,K=(n,i=1,d,x)=>eval('for(;(d=F(i++))<=n&&!(x=!(n%d)&&K(n/d)););x||n<2'))=>eval('for(a=0;n;)K(++a)&&--n;a')
```
*Less golfed* and faster too (avoiding `eval`)
```
n=>{
  F=i=> i>1 ? F(i-1)+F(i-2) : i+1; // recursive calc Fibonacci number
  K=(n,i=1,d,x)=>{ // recursive check divisibility
    for(; (d=F(i++))<=n && !(x=!(n%d)&&K(n/d)); );
    return x||n<2
  };
  for(a=0; n; )
    K(++a) && --n;
  return a
}
```
**Test**
```
X=(n,F=i=>i>1?F(i-1)+F(i-2):i+1,K=(n,i=1,d,x)=>eval('for(;(d=F(i++))<=n&&!(x=!(n%d)&&K(n/d)););x||n<2'))=>eval('for(a=0;n;)K(++a)&&--n;a')
function test() {
  var i=+I.value
  O.textContent=X(i)
}
test()
```
```
<input id=I value=100 >
<button onclick="test()">Go</button><pre id=O></pre>
```
[Answer]
## Haskell, 123 bytes
```
f=2:scanl(+)3f
m((a:b):c)=a:m(b?(a#c))
v#((a:b):c)|v==a=b?(v#c)
_#l=l
y?(z:e)|y>z=z:y?e
a?b=a:b
l=1:m[[a*b|b<-l]|a<-f]
(l!!)
```
Very lazy, much infinite!
Possibly not the shortes way, but I had to try this approach, a generalization of a quite well known method to compute the list of hamming numbers. `f` is the list of fibonacci numbers starting from 2. For brevity, let's say that a lol (list of lists) is an infinite list of ordered infinite lists, ordered by their first elements. `m` is a function to merge a lol, removing duplicates. It uses two infix helper functions. `?` inserts an infinite sorted list into a lol. `#` removes a value from a lol that may appear as head of the first lists, reinserting the remaining list with `?`.
Finally, `l` is the list of numbers which are products of fibonacci numbers, defined as 1 followed by the merge of all the lists obtained by multiplying `l` with a fibonacci number. The last line states the required function (as usual without binding it to a name, so don't copy it as is) using `!!` to index into the list, which makes the function 0-indexed.
There is no problem computing the 100th or 100,000th number.
[Answer]
# [Husk](https://github.com/barbuz/Husk), 13 bytes
Note that Husk is newer than this challenge. However it and the most useful function for this golf (`Ξ`) were not created with this challenge in mind.
```
S!!Ṡ¡ȯuΞIṪ*İf
```
[Try it online!](https://tio.run/##ASEA3v9odXNr//9TISHhuaDCocivdc6eSeG5qirEsGb///8xMDA "Husk – Try It Online")
**More efficient version for 14 bytes:**
[Try it online!](https://tio.run/##ASUA2v9odXNr///ihpJVTSHhuaDCocivdc6eSeG5qirEsGb///8xMDAw)
[Answer]
# Python 2, ~~129~~ ~~128~~ ~~125~~ ~~123~~ 121 bytes
```
g=lambda k:1/k|any(abs(round(5**.5*i)**2-5*i*i)==4>k%i<g(k/i)for i in range(k+1))
f=lambda n,k=1:n and f(n-g(k),k+1)or~-k
```
Test it on [Ideone](http://ideone.com/zjkUa6).
]