Fibonacci-orial

Question

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

• Obligatory OEIS A003266
• OEIS A000045 - Fibonacci sequence

Answer 1

Clojure, 70 bytes

Clojure isn't really a good language for code golf. Oh well.

Try it at http://tryclj.com.

(last(nth(iterate(fn[[a b r]][b(+ a b)(* r(+ a b))])[0N 1 1])(dec n)))

Answer 2

Swift, 68 Bytes

func f(n:Int,_ a:Int=1,_ b:Int=1)->Int{return n<1 ?1:a*f(n-1,b,a+b)}

Answer 3

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).

Answer 4

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

Answer 5

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

Answer 6

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

Answer 7

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

Answer 8

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.

Answer 9

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!

Answer 10

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

Answer 11

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

Answer 12

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

Answer 13

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!

Answer 14

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.

Answer 15

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!

Answer 16

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!

Answer 17

Vyxal, 7 bytes

ƛÞF$i;Π

Try it Online!

Vyxal r, 6 bytes

ƛÞFi;Π

Try it Online!

        # implicit input
ƛ    ;  # Lambda map (1...input inclusive)
 ÞF     # All fibbonacci numbers
   $    # Swap stack
    i   # Item 
      Π # Reduce by product
        # Implicit output

With r, all functions take arguments in reverse, so $ is not needed.

Answer 18

Vyxal, 4 bytes

ÞFẎΠ

Try it Online!

Come on Vyxal, you can do better.

ÞFẎΠ # Takes a number input
ÞF   # Infinite Fibonacci numbers
  Ẏ  # Limit to first n numbers
   Π # Product of them

Answer 19

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

{}

Answer 20

Pyke, 6 5 bytes

Sm.bB

Try it here!

product(map(nth_fib, input))

Answer 21

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

Answer 22

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.

Answer 23

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

Answer 24

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

Answer 25

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!

Answer 26

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.

Answer 27

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.

Answer 28

R, 36 34 bytes

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

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

Answer 29

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.

Answer 30

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)