21
\$\begingroup\$

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

\$\endgroup\$
  • \$\begingroup\$ 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 \$\endgroup\$ – george Jun 18 '16 at 10:03
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Leaky Nun Jun 18 '16 at 10:58
  • \$\begingroup\$ Ah of course, that makes sense \$\endgroup\$ – george Jun 18 '16 at 11:13
  • \$\begingroup\$ Should you print all the ways in making a number. For example 16 has two ways, or can you just output one? \$\endgroup\$ – george Jun 18 '16 at 14:00
  • 3
    \$\begingroup\$ @george I believe the "corresponding product" is just for clarification. Your code only needs to output the "result". \$\endgroup\$ – trichoplax Jun 18 '16 at 14:19

10 Answers 10

6
\$\begingroup\$

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.
\$\endgroup\$
  • 2
    \$\begingroup\$ What's the complexity of this algorithm, in terms of the input? \$\endgroup\$ – Leaky Nun Jun 18 '16 at 15:29
  • \$\begingroup\$ In any case, it's very fast! Less than 2 seconds for the 100-th term \$\endgroup\$ – Luis Mendo Jun 18 '16 at 15:32
  • \$\begingroup\$ @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. \$\endgroup\$ – Dennis Jun 18 '16 at 15:33
  • 1
    \$\begingroup\$ Well, only you know what your algorithm is... \$\endgroup\$ – Leaky Nun Jun 18 '16 at 15:39
  • \$\begingroup\$ 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. \$\endgroup\$ – Dennis Jun 18 '16 at 16:02
5
\$\begingroup\$

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

Fibonacci/Lucas identity

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

converse Fibonacci/Lucas identity

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.

\$\endgroup\$
5
+200
\$\begingroup\$

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.

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

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
}
\$\endgroup\$
2
\$\begingroup\$

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

\$\endgroup\$
2
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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>

\$\endgroup\$
1
\$\begingroup\$

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.

\$\endgroup\$
1
\$\begingroup\$

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!

\$\endgroup\$
0
\$\begingroup\$

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.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.