13
\$\begingroup\$

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
\$\endgroup\$
  • 5
    \$\begingroup\$ The statement isn't quite correct. E.g. 2 can be decomposed as -1 + 3. The correct statement of Zeckendorf's theorem is that a positive Fibonacci number can be uniquely decomposed as a sum of non-consecutive Fibonacci numbers with positive index. \$\endgroup\$ – Peter Taylor May 13 '16 at 10:07
  • 1
    \$\begingroup\$ @PeterTaylor I don't consider negative Fibonacci numbers part of the series for this question. Consecutive or not only matters when you want the indices, we do not care about the indices for this question. \$\endgroup\$ – orlp May 13 '16 at 10:09
  • 1
    \$\begingroup\$ I'm not saying that you should change the question to support negative Fibonacci numbers: I'm saying that you should edit it to be explicit about the assumptions which you're making. \$\endgroup\$ – Peter Taylor May 13 '16 at 11:03
  • 1
    \$\begingroup\$ @orlp consecutive or not matters quite a bit, since two different forms would give two different products. You already stated the problem in a way that already implicitly rules out consecutive Fibonacci terms, though, so there's nothing to worry about there. \$\endgroup\$ – hobbs May 13 '16 at 20:44
  • 2
    \$\begingroup\$ (specifically: F(n) and F(n+1) can't both appear in the output because the algorithm guarantees that, before considering them, the remainder is already less than F(n+2) = F(n) + F(n+1)) \$\endgroup\$ – hobbs May 13 '16 at 20:46

13 Answers 13

5
\$\begingroup\$

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.  
\$\endgroup\$
  • 6
    \$\begingroup\$ This seems big, Dennis. \$\endgroup\$ – orlp May 13 '16 at 16:32
9
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ The explanation should mention that octal 061 is the ASCII encoding for the character '1'. Nice hack to use $\ to get it printed for near-free. \$\endgroup\$ – Peter Cordes May 15 '16 at 0:35
2
\$\begingroup\$

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

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

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

Pyth, 28 bytes

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

I think it can be golfed much further...

Try it online!

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

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.

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

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

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
\$\endgroup\$
  • \$\begingroup\$ Does Actually have its own encoding? I count 35 bytes across 22 chars. mothereff.in/… \$\endgroup\$ – cat May 14 '16 at 13:31
  • 1
    \$\begingroup\$ @cat Just like Seriously, it uses CP437. \$\endgroup\$ – Mego May 14 '16 at 14:56
1
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ There's one superflouous whitespace. :P \$\endgroup\$ – cat May 14 '16 at 13:33
1
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ I count 46 bytes across 42 chars. If RETURN uses some kinda special encoding, it should be 42 bytes across 42 chars, but it appears to be unicode, so it's 46. \$\endgroup\$ – cat May 14 '16 at 13:30
  • \$\begingroup\$ Actually, I just realized that I forgot to put in some unprintables. \$\endgroup\$ – Mama Fun Roll May 14 '16 at 17:32
  • \$\begingroup\$ I needed a microscope to tell what they are, so I linked to them for you. :D (I couldn't tell if it was SOH or BOM) \$\endgroup\$ – cat May 14 '16 at 17:39
0
\$\begingroup\$

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.

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

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

\$\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.