36
\$\begingroup\$

Definition

Fibonacci sequence F(n), on the positive integers, are defined as such:

1. F(1) = 1
2. F(2) = 1
3. F(n) = F(n-1) + F(n-2), where n is an integer and n > 2

The Fibonacci-orial of a positive integer is the product of [F(1), F(2), ..., F(n)].

Task

Given positive integer n, find the Fibonacci-orial of n.

Specs

The fibonacci-orial of 100 must compute in under 5 seconds on a reasonable computer.

Testcases

n   Fibonacci-orial of n
1   1
2   1
3   2
4   6
5   30
6   240
7   3120
8   65520
9   2227680
10  122522400
11  10904493600
12  1570247078400
13  365867569267200
14  137932073613734400
15  84138564904377984000
16  83044763560621070208000
17  132622487406311849122176000
18  342696507457909818131702784000
19  1432814097681520949608649339904000
20  9692987370815489224102512784450560000
100 3371601853146468125386964065447576689828006172937411310662486977801540671138589868616500834190029067583665182291701553172011082574587431382310099030394306877775647395167143332483560925112960024644459715300507481235056111434293619038347456390454209587101225261757371666449068625033999573552165524529725467628060170886602001077137613803027158648329335507728698605769992818756765633305318529965186184043999696650407246193257877568825245646129366994079739720698147440310773871269639752334356493678913424390564535389212240038895626811627949132978086070255082668392290037141141291484839596694182152062726390364094447642643912371532491388089634845995941928089653751672688740718152064107169357399466473375804972260594768969952507346694189050233823596316467570584434128052398891223730335019092974935617029638919358286124350711360361279157416837428904150054292406756317837582840596331363581207781793070936765786629772999832857257349696094416616259974304208756997835360702840912518532683324936435856348020736000000000000000000000000

References

\$\endgroup\$
  • \$\begingroup\$ Related. \$\endgroup\$ – Leaky Nun Jul 30 '16 at 3:19
  • 1
    \$\begingroup\$ @LuisMendo The sum of fibonacci is... you've guessed it, fibonacci. Well, minus one. \$\endgroup\$ – Leaky Nun Jul 30 '16 at 9:23
  • 2
    \$\begingroup\$ @LeakyNun Currently the JavaScript answer only completes the test cases up to 15 because JavaScript cannot correctly compare (or manipulate) numbers beyond 2^53 - 1. This is most likely similar for a lot of the submissions here, because most languages don't support numbers that big \$\endgroup\$ – MayorMonty Jul 30 '16 at 13:54
  • 1
    \$\begingroup\$ What do you mean by "reasonable computer"? \$\endgroup\$ – Erik the Outgolfer Jul 31 '16 at 16:26
  • 2
    \$\begingroup\$ -1 because this seems like several challenges tacked together (range, fibonacci of each, factorial) with no particularly interesting shortcuts. \$\endgroup\$ – Esolanging Fruit Dec 28 '17 at 2:25

56 Answers 56

1
\$\begingroup\$

ForceLang, 140 bytes

def s set
s a 0
s b s p 1
s k io.readnum()
if k=1
goto b
label a
s c a+b
s a b
s b c
s p p.mult c
s k k+-1
if k+-1
goto a
label b
io.write p
\$\endgroup\$
1
\$\begingroup\$

Racket 130 bytes

(define(fb n)(cond[(or(= n 1)(= n 2))1][(+(fb(- n 1))(fb(- n 2)))]))
(define(fo n)(for/product((i(range 1(+ 1 n))))(fb i)))(fo n))

Ungolfed:

(define (f n)
  (define (fibonacci n)
    (cond
      [(or (= n 1)(= n 2)) 1]
      [else (+ (fibonacci (- n 1)) (fibonacci(- n 2)))] ))
  (define (f_orial n)
    (for/product ((i (range 1 (add1 n))))
      (fibonacci i)))
  (f_orial n))

Testing:

(f 1)
(f 2)
(f 3)
(f 4)
(f 5)
(f 6)
(f 7)
(f 8)
(f 9)
(f 10)
(f 11)
(f 12)
(f 20)
(f 30)

Output:

1
1
2
6
30
240
3120
65520
2227680
122522400
10904493600
1570247078400
9692987370815489224102512784450560000
607373569868916007005878071331449502263924414704952629297115029592606043656028160000000
\$\endgroup\$
1
\$\begingroup\$

dc, 38 40 30 28 bytes

?si1d[sadlarla+zli>b]sbzli>b[*z1<*]ds*xf

si1d[sadlarla+zli>b*]sbzli>b

Expanded:

si     # Take input from top of stack and store it in register `i'
1d     # Push 1 on stack and duplicate
[      # Open macro definition
 sa    #  Store most recent term of Fibonacci sequence in register `a'
 d     #  Duplicate second most recent term
 la    #  Push most recent term onto stack
 r     #  Rotate top two items on stack
 la    #  Push most recent term onto stack (again)
       #  At this point, we've essentially duplicated the top two terms of the stack
       #    without altering the order of the terms
 +     #  Add top two terms of stack (generate next Fibonacci number)
 zli>b #  Take stack depth and load input (target number of terms); if we don't have
       #  enough terms yet, execute `b'
 *     #  Once we've generated all the terms (factors, really), we'll multiply
       #    them, one * for every time we iterated to generate a term
]sb    # Store macro in register `b'
zli>b  # Look familiar? This way, we change the "do-while" (`dsbx') to just "while"
       # Leave result on top of stack
\$\endgroup\$
  • \$\begingroup\$ z as implicit loop counter in zli!= is nice!!! And I like your idea to collect all factors on the stack and multiply them in a loop... ;-) ...but it hangs on input 1 and 2 here on GNU dc... :-( \$\endgroup\$ – user19214 Jul 30 '16 at 19:31
  • \$\begingroup\$ @yeti Thanks :D And thanks for pointing out the bug; I hadn't noticed. \$\endgroup\$ – Joe Jul 31 '16 at 0:02
1
\$\begingroup\$

Fortran 95, 118 bytes

This version explicitly declares P as an integer, thus the limit is given by the size of the integer (4 bytes by default).

program o
integer,parameter::n=20
integer F(n),P
P=1
F(:2)=1
do i=3,n
F(i)=F(i-1)+F(i-2)
P=P*F(i)
enddo
print*,P
end

If I extend the size of the integer to 16 bytes, the byte count of the code increases by 3: integer*16 F(n),P.

One can also omit P from the declaration and use it as a 4 byte floating point, then the byte count is reduced by 2.

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

Pyt, 5 bytes

←ř⁻ḞΠ

Input is from stdin. Approximately instantaneous for n=100. Takes less than a second for n=1000.

Explanation:

←            Get input
 ř           Get [1,2,...,input]
  ⁻          Decrement all elements by 1
   Ḟ         Get Fibonacci numbers
    Π        Product

Try it online!

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

05AB1E, 6 4 bytes

LÅfP

Try it online!

-1 from Robbie0630, -1 more from an improvement on his suggestion.

\$\endgroup\$
  • 1
    \$\begingroup\$ @robbie0630 LÅfP for 4, haven't looked here in a long time ;), you have to actually be careful with it doesn't work on 2-byte commands. Also, with L, many things vectorize automatically (even list commands) so you don't need an iterator :). \$\endgroup\$ – Magic Octopus Urn Feb 20 '18 at 17:14
1
\$\begingroup\$

Ruby, 35 bytes

A Ruby fork of Dennis's Python answer. Golfing suggestions welcome.

f=->n,a=1,b=1{n<1?1:a*f[n-1,b,a+b]}

Try it online!

Ungolfed:

def f(n)
  a=b=z=1
  (1..n).each do |i|
     z*=a
     a,b=b,a+b
  end
  return z
end
\$\endgroup\$
  • \$\begingroup\$ n<1?1:a*f... is n<1||a*f...? \$\endgroup\$ – Stan Strum Feb 22 '18 at 5:35
  • \$\begingroup\$ @StanStrum In Ruby, true can't be coerced into Integer. \$\endgroup\$ – Sherlock9 Feb 23 '18 at 8:08
1
\$\begingroup\$

cQuents, 16 15 bytes

=1:Zb$
=1,1:Z+Y

Try it online!

Explanation

=1:       Sequence with first term = 1
   Zb$    Each term equals the previous times the next line at the current index

=1,1:     Sequence with the first two terms = 1
     Z+Y  Each term equals the previous two terms added together
\$\endgroup\$
0
\$\begingroup\$

Pyke, 6 5 bytes

Sm.bB

Try it here!

product(map(nth_fib, input))
\$\endgroup\$
0
\$\begingroup\$

ngn/apl, 20 bytes

{×/(+/(!∘⌽⍨⍳))¨1+⍳⍵}

Try it here.

Explanation

{×/(+/(!∘⌽⍨⍳))¨1+⍳⍵}  Input: n
                  ⍵   Get n
                 ⍳    Form the range [0, 1, ..., n-1]
               1+     Add 1 to each to get [1, 2, ..., n]
              ¨       For each value x
           ⍳            Form the range [0, 1, ..., x-1]
         ⌽⍨             Reverse it to get [x-1, ..., 1, 0]
       !∘               Find the binomial coefficient between each pair in the original
                        range and reversed range
    +/                  Reduce using addition to get the xth Fibonacci number
 ×/                   Reduce using multiplication and return
\$\endgroup\$
0
\$\begingroup\$

Maple, 40 bytes

`*`~(seq(combinat:-fibonacci(i),i=1..n))

Usage

> f:=n->`*`~(seq(combinat:-fibonacci(i),i=1..n));
> f(10);
  122522400

This uses the built-in combinat:-fibonacci as well as the element-wise operator ~ to multiply the terms in the sequence.

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

PowerShell v3+, 86 bytes

param($n)$f=,1*$n;2..$n|%{$f[$_]=$f[$_-1]+$f[$_-2]};"[bigint]"+($f[0..$n]-join'*')|iex

The [bigint] data structure was introduced in .NET Framework 4, hence the PowerShell v3+ requirement.

Takes input $n, constructs a new array $f pre-populated with 1s, of length $n. Then we loop from 2..$n and each iteration simply construct the next Fibonacci value. Finally, we take $f from 0 up to $n and -join it together with * (so we have a big ol' string like 1*1*2*3*5*8*...), prepend that string with the cast "[bigint]", and pipe that to |iex (short for Invoke-Expression and similar to eval). The result is left on the pipeline, and output is implicit. We get by with only one data cast, as PowerShell uses the explicit cast from the left-hand-side of an operator as an implicit cast on the right-hand-side.

Tosses an array-index-out-of-bounds style exception to STDERR, but that's shorter than setting the loop to 2..($n-1) ;-)


If we didn't need to go higher than ~55, we can get rid of the cast and parens for the following at 73 bytes. Input values above 13 will result in scientific notation output.

param($n)$f=,1*$n;2..$n|%{$f[$_]=$f[$_-1]+$f[$_-2]};$f[0..$n]-join'*'|iex
\$\endgroup\$
0
\$\begingroup\$

05AB1E, 12 bytes

X$ÍF‚D`ŠŠO}P

Explanation

X$           # push 1, 1, input
  ÍF      }  # input-2 times do:
    ‚D       # pair top 2 elments and duplicate
      `ŠŠ    # flatten one pair and move the remaining pair to the top of the stack
         O   # sum the pair
           P # product of stack
             # implicitly print

Try it online

\$\endgroup\$
  • \$\begingroup\$ ÅF - Fibonacci numbers. \$\endgroup\$ – Magic Octopus Urn Jan 5 '17 at 15:57
0
\$\begingroup\$

Fourier, 34 bytes

Basically, just a small tweak of the Fibonacci sequence program on Fourier's esolangs page.

1~F~x~yI~k(x*F~Fy+x~gy~xg~yi^~i)Fo

If you want to try this program online, I would suggest using Dennis' site, http://fourier.tryitonline.net, because on http://labs.turbo.run/beta/fourier an input of 100 leads to an output of infinity.

Try it online!

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

Lithp, 362 bytes

(
    (platform v1)
    (import "lists")
    (var FL (dict))
    (def fib #N::((if (< N 2) (1) ((+ (fibFL (- N 1)) (fibFL (- N 2)))))))
    (def fibFL #N::((if (dict-present FL N) ((dict-get FL N)) ((var I (fib N)) (set FL (dict-set FL N I)) (I)))))
    (def fib-orial #N::((prod (map (seq 1 N) (scope #I::((fib I)))))))
    (each (seq 2 15) (scope #N :: ((print (fib-orial N)))))
)

As with the JavaScript answer, rounding errors occur at orial of 16. Therefore this program prints the orial of 2 to 15.

This one was tricky, because the run time was well over 10 seconds for even a small number. I solved this by using a dictionary to store results of calls to fib. The result is that instead of 10 seconds and over 100,000 function calls, the code often runs in under 200ms and results in only ~6700 function calls.

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

Pushy, 12 bytes

1&{2-:2d+;P#

Try it online!

This is a straightforward implementation of the specification:

1&    \ Push 1, twice.
{     \ Shift stack left (so input is on top).
      \ Stack: [1, 1, n]

2-:   \ Input - 2 times do (this consume input):
2d+;  \   Push the sum of the last 2 values.
      \ Stack: [fib(1), fib(2)... fib(n)]

P#    \ Output the stack product.
\$\endgroup\$
0
\$\begingroup\$

R, 36 34 bytes

prod(numbers::fibonacci(scan(),T))

Takes input from stdin. -2 bytes due to @Jardo Dubbeldam.

\$\endgroup\$
  • 1
    \$\begingroup\$ prod(numbers::fibonacci(scan(),T)) is a shorter builtin implementation :) \$\endgroup\$ – JAD Jan 5 '17 at 16:15
  • \$\begingroup\$ @JarkoDubbeldam Haha, thanks! You would think I would have tried that, given I was just talking to you about that function... \$\endgroup\$ – rturnbull Jan 5 '17 at 16:48
0
\$\begingroup\$

Perl 6, 23 bytes

{[*] (1,&[+]...*)[^$_]}

Try it online!

  • 1, &[+] ... * is the infinite Fibonacci sequence.
  • [^$_] takes the first $_ elements of the sequence, where $_ is the argument to the function.
  • [*] reduces that subsequence with multiplication.
\$\endgroup\$
0
\$\begingroup\$

Javascript,44 bytes

n=>eval(`for(c=a=b=1;--n;b+=t)t=a,c*=a=b;c`)

based on this Fibbonaci sequence

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

Husk, 4 bytes

Π↑İf

Try it online!

Explanation

Π↑İf  -- input is an integer N, for example 5
  İf  -- fibonacci numbers: [1,1,2,3,5,8,13,21,34…]
 ↑    -- take N: [1,1,2,3,5]
Π     -- product: 30
\$\endgroup\$
0
\$\begingroup\$

J, 30 Bytes

*/@:([{.(,{:+{:@}:)@]^:[&1 1x)

Probably improvable.

Explanation:

*/@:(                        )    | Product of
     [{.                          | First n
        (,{:+{:@}:)@]^:[&1 1x     | n+2 fibonacci numbers:
                        &1 1x     | Apply with the list 1 1 (x specifies extended prescision)
                     ^:[          | n times:
        (,{:+{:@}:)@]             | Append the sum of the last two numbers

Computes the Fibonacc-orial of 100 in 2 ms.

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

Scala, 84 bytes

def f(i:Int,v:BigInt=1,p:BigInt=0,c:BigInt=1):BigInt=if(i==0)c else f(i-1,v+p,v,c*v)

Tail recursive function, based on this Fibonnaci implementation. This version adds a parameter to keep track of the running product.

Run it online (with test cases)

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

Pyt, 3 bytes

Zero indexed

Thanks to mudkip201 for catching my mistake

řḞΠ

Try it online!

         implicit input
ř        range from input to one
 Ḟ       fibonacci over array
  Π      product
         implicit output
\$\endgroup\$
  • \$\begingroup\$ I think you meant Π, not Ʃ \$\endgroup\$ – mudkip201 Feb 18 '18 at 19:22
  • \$\begingroup\$ @mudkip201 good catch \$\endgroup\$ – FantaC Feb 19 '18 at 3:14
0
\$\begingroup\$

Jelly, 4 bytes

RÆḞP

Try it online!

Explanation

R       inclusive range
 ÆḞ     nth fibonacci number
   P    product
\$\endgroup\$
0
\$\begingroup\$

Japt, 7 bytes

õ@MgXÃ×

Try it


Explanation

õ         :Range [1,input]
 @   Ã    :Pass each X through a function
  MgX     :  Xth Fibonacci number
      ×   :Reduce by multiplication
\$\endgroup\$
0
\$\begingroup\$

Common Lisp, 65 bytes

(defun f(n &optional(a 1)(b 1))(if(< n 1)1(*(f(1- n)b(+ a b))a)))

Try it online!

Another port of Dennis's Python answer.

The straight iterative implementation is four bytes more:

(lambda(n)(do((x 1 y)(y 1(+ x y))(i 0(1+ i))(p 1(* p x)))((= i n)p)))
\$\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.