Fibonacci products

Question

You can decompose a number greater than 0 as a unique sum of positive Fibonacci numbers. In this question we do this by repeatedly subtracting the largest possible positive Fibonacci number. E.g.:

1 = 1
2 = 2
3 = 3
4 = 3 + 1
12 = 8 + 3 + 1
13 = 13
100 = 89 + 8 + 3

Now, I call a Fibonacci product the same lists as above, but with the addition replaced by multiplication. For example, f(100) = 89 * 8 * 3 = 2136.

Write a program or function that given a positive integer n returns the Fibonacci product of that number.

---

Testcases:

1: 1
2: 2
3: 3
4: 3
5: 5
6: 5
7: 10
8: 8
9: 8
42: 272
1000: 12831
12345: 138481852236

Answer 1

Jelly, 16 15 bytes

Rf1+С¤ṪạµÐĿIAP

Not particularly fast or memory friendly, but efficient enough for all test cases. Try it online!

How it works

Rf1+С¤ṪạµÐĿIAP  Main link. Argument: n (integer)

         µ       Combine the chain to the left into a link.
          ÐĿ     Apply that link until the results are no longer unique.
                 Return the list of unique results.
      ¤            Combine the two links to the left into a niladic chain.
  1                  Set the left (and right) argument to 1.
   +D¡               Apply + to the left and right argument, updating the left
                     argument with the sum, and the right argument with the
                     previous value of the left one. Return the list of results.
                     Repeat this process n times.
                   This yields n + 1 Fibonacci numbers, starting with 1, 2.
R                  Range; map k to [1, ..., k].
 f                 Filter; keep the items in the range that are Fibonacci numbers.
       Ṫ           Tail; yield the last one or 0 if the list is empty.
        ạ          Absolute difference with k.
                   This is the argument of the next iteration.
            I    Compute the increments of the arguments to the loop, yielding
                 the selected Fibonacci numbers (with changed sign).
             A   Apply absolute value to each.
              P  Compute their product.  

Answer 2

Python, 54 bytes

f=lambda n,a=1,b=1:n<1or b>n and a*f(n-a)or f(n,b,a+b)

Just some good old recursion.

Answer 3

Perl, 69 63 + 4 (-pl61 flag) = 67 bytes

#!perl -pl61
while($_){$n=$m=1;($n,$m)=($m,$n+$m)until$m>$_;$_-=$n;$\*=$n}}{

Using:

> echo 42 | perl -pl61e 'while($_){$n=$m=1;($n,$m)=($m,$n+$m)until$m>$_;$_-=$n;$\*=$n}}{'

Ungolfed:

while (<>) {
# code above added by -p
    # $_ has input value
    # $\ = 1 by -l61
    while ($_ != 0) {
        my $n = 1;
        my $m = 1;
        while ($m <= $_) {
            ($n, $m) = ($m, $n + $m);
        }
        $_ -= $n;
        $\ *= $n;
    }
} {
# code below added by -p
    print;  # prints $_ (undef here) and $\
}

Ideone.

Answer 4

><>, 57 bytes

111\ ;n{/
:@+>:{:})?\$:@@
~{*}:0=?\}>:0${:})?$~:{$-$:1@?$

Expects the input number to be present on the stack at program start.

Builds up the Fibonacci sequence (f0, f1, f2, ..., fn) on the stack until a number is reached that is greater than the the input (i). Then, with a product (p) initialised to 1...

while (i != 0)
   if (fn <= i)
      i = i - fn
      p = p * fn
   else
      i = i - 0
      p = p * 1
   discard fn
output p

Try it out online!

Answer 5

JavaScript (ES6), 78 42 bytes

f=(n,a=1,b=1)=>n?b>n?a*f(n-a):f(n,b,a+b):1

Port of @Sp3000's answer. Original 78 byte version:

f=(n,a=[2,1])=>n>a[0]?f(n,[a[0]+a[1],...a]):a.map(e=>e>n?0:(r*=e,n-=e),r=1)&&r

Answer 6

Pyth, 28 bytes

K1WQJ0 .WgQH+Z~JZ1=*KJ=-QJ;K

I think it can be golfed much further...

Try it online!

Answer 7

Javascript (ES6) 134 106 92 bytes

Thanks for @cat for spotting a space.

n=>{for(c=[a=b=s=1,1];a+b<=n;)a+=b,c.unshift(b+=a,a);c.map(i=>i<=n&&(n-=i)&(s*=i));alert(s)}

Just an unoptimized version made on my phone, I golf it down, once I get home. Ideas are welcome.

Answer 8

Pyth, 24 bytes

W=-QeaYh.WgQeH,eZsZ1;*FY

Try it online: Demonstration or Test Suite

Explanation:

Q is assigned with the input number.

The part h.WgQeH,eZsZ1 calculates the biggest Fibonacci number, that is smaller or equal to Q

h.WgQeH,eZsZ1
            1   start with H=Z=1
 .WgQeH         while Q >= end(H):
       ,eZsZ       H=Z=(end(Z), sum(Z))
h               first

So if Q = 10, it generates the numbers/pairs:

1 -> (1,1) -> (1,2) -> (2,3) -> (3,5) -> (5,8) -> (8,13) -> 8

The rest of the code calculates the partition and multiplies the numbers together:

W=-QeaY...;*FY    implicit: Y = empty list
     aY...        add the calculated Fibonacci number to the empty list
    e             take the last element of Y (yes the number we just added)
 =-Q              and update Q with the difference of Q and ^
W         ;       continue until Q == 0
           *FY    multiply all number in Y and print

There are obviously a lot of shorter solutions (with really bad run-times though), like *FhfqQsTyeM.u,eNsNQ1.

Answer 9

Haskell, 44 bytes

Yay for mutual recursion:

(a&b)c|c<1=1|b>c=a*f(c-a)|d<-a+b=b&d$c
f=0&1

• a is the previous Fibonacci number
• b is the current Fibonacci number
• c is the input
• f is the desired function

Less golfed:

(a & b) c | c == 0    = 1
          | c <  b    = a * f (c-a)
          | otherwise = b & (a + b) $ c
f x = (0 & 1) x

Answer 10

Actually, 22 bytes

W;╗uR♂F;`╜≥`M░M;╜-WXkπ

Try it online!

Explanation:

W;╗uR♂F;`╜≥`M░M;╜-WXkπ
                        (implicit input)
W                 W     while top of stack is truthy:
 ;╗                       push a copy of n to reg0
   uR♂F;                  push 2 copies of [Fib(a) for a in range(1, n+2)]
        `╜≥`M░            filter: take values where n <= Fib(a)
              M;          two copies of maximum (call it m)
                ╜-        subtract from n (this leaves n-m on top of the stack to be the new n next iteration, with a copy of m below it)
                   X    discard the 0 left over after the loop ends
                    kπ  product of all stack values

Answer 11

RETURN, 44 bytes

[a:[a;][1$[¤¤+$a;->~][]#%$␌a;\-a:]#␁[¤][×]#]

Try it here.

Astonishingly inefficient anonymous lambda that leaves result on Stack2. Usage:

12345[a:[a;][1$[¤¤+$a;->~][]#%$␌a;\-a:]#␁[¤][×]#]!

NOTE: ␌ and ␁ are placeholders for their respective unprintable chars: Form Feed and Start of Heading.

Explanation

[                                           ]  lambda
 a:                                            store input to a
   [  ][                         ]#            while loop
    a;                                           check if a is truthy
        1$[¤¤+$a;->~][]#%                        if so, generate all fibonacci numbers less than a 
                         $␌                      push copy of TOS to stack2
                           a;\-a:                a-=TOS
                                   ␁[¤][×]#   get product of stack2

Answer 12

PHP, 119 bytes

The code (wrapped on two lines for readability):

for($o=$c=1;$c<=$n=$argv[1];$f[++$k]=$c,$a=$b,$b=$c,$c+=$a);
for($i=$k;$i;$i--)for(;$n>=$d=$f[$i];$n-=$d,$o*=$d);echo$o;

The first line computes in $f the Fibonacci numbers smaller than $n (the argument provided in the command line). The second line computes the Fibonacci factors (by subtraction) and multiplies them to compute the product in $o.

Prepend the code with <?php (technically not part of the program), put it in a file (fibonacci-factors.php) then run it as:

$ php -d error_reporting=0 fibonacci-factors.php 100
# The output:
2136

Or run it using php -d error_reporting=0 -r '... code here ...' 100.

The ungolfed code and the test suite can be found on Github.

Answer 13

Q, 47 Bytes

m:{*/1_-':|(0<){y-x x bin y}[*+60(|+\)\1 0]\x}

Test

+(i;m'i:1 2 3 4 5 6 7 8 9 42 1000 12345)

read it as pairs (i,map(m,i)), where m is the calculating function and i the different args

writes

1     1
2     2
3     3
4     3
5     5
6     5
7     10
8     8
9     8
42    272
1000  12831
12345 138481852236

Explanation

n funtion\arg applies function(function(function(...function(args))) n times (internally uses tal recursion), and returns the sequence of results. We calculate the 60 first items of fibonnaci series as *+60(|+\)\1 0. In that case the function is (|+): +\ applied over a sequence calculates partial sums (ex +\1 2 3 is 1 3 6), and | reverses seq. So each 'iteration' we calculate partial sums of the two previous fibonacci number and return the partial sums reversed. 60(|+\)\1 0 generates sequences 1 0, 1 1, 2 1, 3 2, 5 3, 8 5, 13 8, 21 13, ... *+ applied over this result flip (traspose) it and takes the first. Result is sequence 1 1 2 3 5 8 13 21 34 55 ..

(cond)function\args applies function(function(..function(args))) while cond true, and returns the sequence of partial results

function[arg] applied over a function of more than one argument creates a projection (partial application)

We can give name to the args, but the implicit names are x,y,z

{y-x x bin y}[*+60(|+\)\1 0] declares a lambda with args x,y with partial projection (arg x is fibonacci series, calculates as *+60(|+)\1 0). x represent fibonacci values, and y the number to process. Binary search (bin) is used to locate the index of the greater fibonacci number <=y (x bin y), and substract the corresponding value of x.

To calculate product from partial resuls we reverse them and calculate difference of each pair (-':|), drop the first (1_ because is 0) and multiply over (*/).

If we are interested in accumulated sum the code is the same, but with +/ instead of */. We can also use any other diadic operator instead of + or *

About execution efficiency

I know that in this contest efficiency is not an issue. But in this problem we can range from lineal cost to exponential cost, so i'm curious about it.

I developed a second version (length 48 Bytes excluding comment) and repeated test cases battery 1000 times on both versions.

f:*+60(|+\)\1 0;m:{*/1_-':|(0<){x-f f bin x}\x}    /new version

execution time is: original version 0'212 seg, new version 0'037 seg

Original version calculates fibbonaci serie once per function application; new version calculates fibonacci just one.

In both cases calculation of fibonacci series uses tail recursion