40
\$\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\$
13
  • \$\begingroup\$ Related. \$\endgroup\$ – Leaky Nun Jul 30 '16 at 3:19
  • 2
    \$\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
  • 3
    \$\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

63 Answers 63

1
\$\begingroup\$

JavaScript (ES6), 46 bytes

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

Uses recursion and accumulator variables. Rounding errors start at f(16).

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

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

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

Setanta, 65 62 bytes

gniomh(n){a:=0b:=1x:=1le i idir(0,n){b+=a a=b-a x*=a}toradh x}

Unfortunately isn't exact because this language doesn't have bigints.

Try it here!

\$\endgroup\$
1
+50
\$\begingroup\$

Whispers v3, 43 bytes

> Input
> fₙ
>> 2ᶠ1
>> ∏3
>> Output 4

Try it repl.it!

Needs to be run with

python3 whispers\ v3.py fibonacciorial.wisp < input.txt 2> /dev/null

Finishes well within 5 seconds on repl.it.

\$\endgroup\$
2
  • \$\begingroup\$ I think it should be rather than ? \$\endgroup\$ – Leo Feb 4 at 23:22
  • \$\begingroup\$ @Leo aaaaa missed that completely \$\endgroup\$ – Razetime Feb 5 at 2:49
1
\$\begingroup\$

Tcl, 115 bytes

proc F x {expr $x>1?\[F $x-1]+\[F $x-2]:$x}
proc P x {incr p
while {[incr i]<=$x} {set p [expr $p*[F $i]]}
expr $p}

Try it online!

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

Tcl, 110 bytes

set a 0
set b [incr x]
time {set c [expr $a+$b]
set a $b
set x [expr $x*[set b $c]]} [expr {*}$argv-1]
puts $x

Try it online!

Was able to take off 9 bytes thanks to sergiol!

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

Brain-Flak, 110 104 100 bytes

Try it online!

({}<((())<>)>){({}[()]<<>(({})<>({}<>)<>)>)}<>{}([[]]()){({}()<({}<>)<>({<({}[()])><>({})<>}{})>)}{}

Explanation

First we run an improved version of the Fibonacci sequence generator curtesy of Dr Green Eggs and Iron Man

({}<((())<>)>){({}[()]<<>(({})<>({}<>)<>)>)}<>{}

Then while the stack has more than one item on it

([[]]()){({}()<...>)}

multiply the top two items

({}<>)<>({<({}[()])><>({})<>}{})

and pop the extra zero

{}
\$\endgroup\$
1
  • 2
    \$\begingroup\$ Unfortunately, I think this is invalid since it takes over 10 seconds for an input of 25. The algorithm is very inefficient (just like the language is), so calculating it for 100 would probably take hours. \$\endgroup\$ – James Jul 30 '16 at 13:14
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\$
1
  • \$\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\$
2
  • 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\$

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

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\$
2
  • \$\begingroup\$ I think you meant Π, not Ʃ \$\endgroup\$ – mudkip201 Feb 18 '18 at 19:22
  • \$\begingroup\$ @mudkip201 good catch \$\endgroup\$ – RaviRavioli 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\$

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.