# 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

• 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 Jun 18 '16 at 10:03
• 7 cannot be expressed as the product of Fibonacci numbers. Therefore, the 1st required number is 1, the 2nd is 2, ..., the 6th is 6, but the 7th is 8. – Leaky Nun Jun 18 '16 at 10:58
• Ah of course, that makes sense – george Jun 18 '16 at 11:13
• Should you print all the ways in making a number. For example 16 has two ways, or can you just output one? – george Jun 18 '16 at 14:00
• @george I believe the "corresponding product" is just for clarification. Your code only needs to output the "result". – trichoplax Jun 18 '16 at 14:19

# Jelly, 262423 21 bytes

ÆDf÷ß€FðḊ¡
1ç#2+Ð¡1¤Ṫ


Try it online!

### 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.

• What's the complexity of this algorithm, in terms of the input? – Leaky Nun Jun 18 '16 at 15:29
• In any case, it's very fast! Less than 2 seconds for the 100-th term – Luis Mendo Jun 18 '16 at 15:32
• @LeakyNun I have no idea how to calculate that, but seeing how input 400 takes 32 times longer than input 100, I'd say it's exponential. Handles 100 with ease though. – Dennis Jun 18 '16 at 15:33
• Well, only you know what your algorithm is... – Leaky Nun Jun 18 '16 at 15:39
• I managed to make it a lot faster by not recomputing the Fibonacci sequence for every tested number. I'll add an explanation as soon as I'm done golfing. – Dennis Jun 18 '16 at 16:02

# 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!

### Background

In Advanced Problems and Solutions, H-187: Fibonacci is a square, the proposer shows that

where Ln denotes the nth Lucas number, and that – conversely – if

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.

## 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 kth 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.

• According to this table at OEIS, g(k) exceeds k*k when k = 47000 and above. – isaacg Nov 18 '17 at 1:49

# Perl 6,  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
}


# Python 3, 175170 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

# 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.

### 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 nth 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.

# 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>

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.

# 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!

More efficient version for 14 bytes:

Try it online!

# Python 2, 129128125123 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.