# 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 Jun 18, 2016 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. Jun 18, 2016 at 10:58
• Ah of course, that makes sense Jun 18, 2016 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? Jun 18, 2016 at 14:00
• @george I believe the "corresponding product" is just for clarification. Your code only needs to output the "result". Jun 18, 2016 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? Jun 18, 2016 at 15:29
• In any case, it's very fast! Less than 2 seconds for the 100-th term Jun 18, 2016 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. Jun 18, 2016 at 15:33
• Well, only you know what your algorithm is... Jun 18, 2016 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. Jun 18, 2016 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. Nov 18, 2017 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.