Fibonacci Factorization

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

Answer 1

Jelly, 26 24 23 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.

Answer 2

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 L_n denotes the n^th 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 5i² + 4 and 5i² - 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 5i² + 4 and 5i² - 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 3

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.

Answer 4

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
}

Answer 5

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

Answer 6

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

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 8

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 9

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!

Answer 10

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.