81
\$\begingroup\$

Create the shortest program or function that finds the factorial of a non-negative integer.

The factorial, represented with ! is defined as such

$$n!:=\begin{cases}1 & n=0\\n\cdot(n-1)!&n>0\end{cases}$$

In plain English the factorial of 0 is 1 and the factorial of n, where n is larger than 0 is n times the factorial of one less than n.

Your code should perform input and output using a standard methods.

Requirements:

  • Does not use any built-in libraries that can calculate the factorial (this includes any form of eval)
  • Can calculate factorials for numbers up to 125
  • Can calculate the factorial for the number 0 (equal to 1)
  • Completes in under a minute for numbers up to 125

The shortest submission wins, in the case of a tie the answer with the most votes at the time wins.

\$\endgroup\$
13
  • 13
    \$\begingroup\$ How many of the given answers can actually compute up to 125! without integer overflow? Wasn't that one of the requirements? Are results as exponential approximations acceptable (ie 125 ! = 1.88267718 × 10^209)? \$\endgroup\$
    – Ami
    Feb 6 '11 at 22:43
  • 7
    \$\begingroup\$ @SHiNKiROU, even golfscript can manage 125! less than 1/10th of a second and it's and interpreted interpreted language! \$\endgroup\$
    – gnibbler
    Feb 8 '11 at 3:21
  • 6
    \$\begingroup\$ @ugoren the two-character solution to the other question uses a built-in factorial function. That's not allowed in this version of the challenge. \$\endgroup\$ Jan 7 '14 at 3:18
  • 5
    \$\begingroup\$ Completes in under a minute seems a very hardware-dependent requirement. Completes in under a minute on what hardware? \$\endgroup\$
    – sergiol
    Aug 24 '17 at 18:05
  • 4
    \$\begingroup\$ @sergiol Incredibly that hasn't been an issue in the last 2 years, I suspect most languages can get it done in under a minute. \$\endgroup\$ Aug 24 '17 at 21:20

191 Answers 191

1 2 3
4
5
7
1
\$\begingroup\$

Mathematica – 46 characters

f[x_]:=Integrate[(x+1)^(t-1)Exp[-x-1],{t,0,∞}]

This is using the integral definition of the Gamma Function.

\$\endgroup\$
1
  • \$\begingroup\$ I like this solution! \$\endgroup\$ Sep 9 '14 at 10:45
1
\$\begingroup\$

C#, 30

double a=1;while(p>0){a*=p--;}

With spaces for ease of reading:

double a = 1;
        while(p > 0)
        {
            a *= p--;
        }

a is the factorial result, while p is the number for which factorial is computed.

\$\endgroup\$
2
  • \$\begingroup\$ Couldn't you just say "while(p)statement;" instead of "while(p>0){statement;}"? Unless C# behaves differently from C, it should work. \$\endgroup\$ Apr 1 '14 at 18:59
  • \$\begingroup\$ if p is bool, it would. Here I need to continue checking p with 0... \$\endgroup\$
    – s3l1n
    Apr 2 '14 at 5:20
1
\$\begingroup\$

Python 2.7.5 - 29 characters

f=lambda n:n and n*f(n-1)or 1

29 characters. It's still mathematically sound for a negative input value, since (-n)! = ∞ and therefore the program gives a Runtime Error maximum recursion depth exceeded.

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

Ruby: 22 characters

n.downto(1).reduce(:*)
\$\endgroup\$
1
\$\begingroup\$

Simplefunge, 87 chars including whitespace

v

     v  *&<
     >   &V
     `    &
 v     <  o
     ^H^  @
v>>!1-^
>iV    
  >1o@

I don't actually have time to test this right now, but it should work. If it doesn't work, I'll fix it tomorrow.

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

Scala, 28 (39 w/ recursion)

Solution:

def f(n:Int)=(1 to n)product

Recursive solution:

def f(n:Int):Int=if(n<2)1 else n*f(n-1)
\$\endgroup\$
1
\$\begingroup\$

R - 33

function(x) ifelse(x,prod(1:x),1)

> (function(x) ifelse(x,prod(1:x),1))(0)
[1] 1
> (function(x) ifelse(x,prod(1:x),1))(5)
[1] 120
> (function(x) ifelse(x,prod(1:x),1))(120)
[1] 6.689503e+198
\$\endgroup\$
1
\$\begingroup\$

Powershell, 31

$a=1;$args[0]..1|%{$a=$_*$a};$a

usage

powershell -nologo .\fact125.ps1 0
0
powershell -nologo .\fact125.ps1 1
1
owershell -nologo .\fact125.ps1 5
120
powershell -nologo .\fact125.ps1 125
1.88267717688893E+209
\$\endgroup\$
2
  • \$\begingroup\$ This doesn't account for 0!=1. You can use the Invoke-Expression command to evaluate on-the-fly, and then use bool casting to select the appropriate answer -- try param($a)$b=1..$a-join'*'|iex;($b,1)[!$a] for 41 bytes \$\endgroup\$ Nov 23 '15 at 20:13
  • 1
    \$\begingroup\$ Actually, we can move the |iex and skip the $b entirely -- 37 Bytes for param($a)((1..$a-join'*'),1)[!$a]|iex \$\endgroup\$ Nov 23 '15 at 20:38
1
\$\begingroup\$

Python, 43 38

import math
f=lambda n:math.gamma(n+1)

Explanation: The gamma function is a very quickly-growing complex function which, at integer values, is equal to the factorial of one less than the number. So we add one to n and take the gamma function of it.

I hope this isn't considered cheating, since the gamma function is not technically able to directly calculate the factorial.

\$\endgroup\$
1
  • 1
    \$\begingroup\$ To quote Wikipedia, "In mathematics, the gamma function is an extension of the factorial function, with its argument shifted down by 1, to real and complex numbers". Some would say it's "close enough" to a factorial function that it shouldn't count, I personally don't care because it's longer than the other Python answers. \$\endgroup\$ Oct 14 '15 at 17:49
1
\$\begingroup\$

Clojure/ClojureScript, 26 bytes

#(apply *(range 1(inc %)))
\$\endgroup\$
1
\$\begingroup\$

Bash/coreutils/dc, 25

dc<<<"1 `seq -f%g* $1`p"

This forms a dc script and evaluates it. So ,with input of 5, we evaluate

1 1*
2*
3*
4*
5*p

It took my machine 2.05 seconds to compute 10000! here (that's factorial ten-thousand, with 36693 digits), so seems to scale reasonably well. For the zero case, seq produces no output, so the dc script is just 1 p which produces the correct output 1.

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

R 27 Bytes

function(n)prod(seq_len(n))
\$\endgroup\$
1
\$\begingroup\$

APL (13)

∇R←F X
R←×/ιX
∇

May need a ⎕IO←1 line to be sure ι starts at 1 - it's been awhile since I last used APL.

\$\endgroup\$
1
  • \$\begingroup\$ ⎕IO←1 is default in many APLs. Also, you can save 3 bytes: Remove the and the last line break, giving the ⎕CR instead of the ⎕VR. Typo: * should be ×. The former is Power: n*2 = n². \$\endgroup\$
    – Adám
    Jan 25 '16 at 14:35
1
\$\begingroup\$

PlatyPar, 8 bytes

c?1,_p\1

Try it online!

Explanation:

c?        ## if (n != 0)
  1,_p     ## product [1..n]
       \  ## else
        1  ## 1
\$\endgroup\$
2
  • \$\begingroup\$ This does not seem to handle the special 0 case. \$\endgroup\$ Jan 26 '16 at 4:04
  • \$\begingroup\$ @ՊՓԼՃՐՊՃՈԲՍԼ oops, I completely forgot. Adding... \$\endgroup\$
    – Cyoce
    Jan 26 '16 at 4:46
1
\$\begingroup\$

JavaScript, 34 bytes

function f(n){return n?n*f(n-1):1}

(or)

function f(n){return n?n*f(--n):1}

Explanation

Function takes in a value, returns itself multiplied by
if n != 0: the same function on the number decreased by one
if n == 0: 1

The final f(0) returns first with 1, times 1, times 2, etc.

Terminator removed, may upset use strict.

\$\endgroup\$
1
  • \$\begingroup\$ There were already some similar answers but uses ES6. \$\endgroup\$
    – jimmy23013
    Jan 26 '16 at 22:42
1
\$\begingroup\$

Japt, 8 bytes (non-competing)

This answer is non-competing because Japt was created long after this challenge.

UòJ ¤r*1

Test it online!

How it works

UòJ ¤r*1   // Implicit: U = input integer                5
UòJ        // Create the inclusive range [-1..U].        [-1, 0, 1, 2, 3, 4, 5]
    ¤      // Slice off the first two items.             [1, 2, 3, 4, 5]
     r*1   // Reduce by multiplication, starting at 1.   1*1=1*2=2*3=6*4=24*5=120
           // Implicit output                            120
\$\endgroup\$
4
  • \$\begingroup\$ This does not handle the zero case correctly (0! should return 1). \$\endgroup\$ Jan 27 '16 at 3:40
  • \$\begingroup\$ @ՊՓԼՃՐՊՃՈԲՍԼ Thanks, fixed now. \$\endgroup\$ Jan 27 '16 at 23:21
  • \$\begingroup\$ I know this is old but, wouldn't á be enough? \$\endgroup\$ Aug 7 '18 at 17:51
  • \$\begingroup\$ @LuisfelipeDejesusMunoz I think you mean l, but yes :-) \$\endgroup\$ Aug 8 '18 at 15:30
1
\$\begingroup\$

𝔼𝕊𝕄𝕚𝕟, 9 chars / 19 bytes (noncompetitive)

+!ï⋎⨴⩤⁽1ï

Try it here (Firefox only).

Ay, 19th byte!

Great thing about this is that it also calculates factorials up to 171 instantly without returning Infinity.

Bonus solution!

+!ï⋎⨴МĂ⩤⁽1ï

Try it here (Firefox only).

This one allows you to calculate past 171 without getting Infinity. Still superbly fast!

\$\endgroup\$
2
  • \$\begingroup\$ Mind explaining how this gets around Infinity? :) \$\endgroup\$ Jan 27 '16 at 18:30
  • \$\begingroup\$ МĂ is math.js's bignumber function. \$\endgroup\$ Jan 27 '16 at 23:07
1
\$\begingroup\$

Lua, 47 bytes

function f(n)return(n<1 and 1 or n*f(n-1))end
\$\endgroup\$
1
\$\begingroup\$

PARI/GP, 16 bytes

n->prod(i=2,n,i)

The shortest answer would be the native ! which is disallowed.

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

PHP

Short, 58

<?$r=$i=$argv[1];while($i>1){$i--;$r=$r*$i;}echo($r==0?1:$r);

Tests

0 -> 1

1 -> 1

5 -> 120

125 -> 1.8826771768889E+209

170 -> 7.257415615308E+306

171 -> INF

Executes in microseconds.

Ungolfed

<?php
$r = $i = $argv[1]; // Set $r and $i to Arg.
while($i > 1) // Calculate while $i bigger than 1
{
    $i--; // Decrement $i (so it's not infinite)
    $r = $r * $i; // Calculation the Factorial
 }
 echo ($r==0 ? 1: $r); // Output and make 0! = 1
 ?>

Slighty Longer, 86

<?$r=$i=(isset($argv[1])?$argv[1]:0);while($i>1){$i--;$r=$r*$i;}echo($r==0?1:$r)."\n";

Improvements

  • Output with \n
  • Doesn't throw error if no arg defined
\$\endgroup\$
1
\$\begingroup\$

DUP, 19 bytes

[$[$1-a;!*][%1]?]a:

Try it here!

A recursive lambda that leaves result on the stack. Usage:

6[$[$1-a;!*][%1]?]a:a;!

Explanation

[               ]a: {set a to lambda}
 $                  {check if top of stack >0}
  [       ][  ]?    {conditional}
   $1-a;!*          {if so, top of stack *a(top of stack -1)}
            %1      {otherwise, replace top of stack with 1}
\$\endgroup\$
1
\$\begingroup\$

Hoon, 29 bytes

|=(@ (reel (gulf [1 +<]) mul)

Hoon's native number is a bignum, so it works fine with 125 (or even 2000). It also correctly gives 1 for 0.

It uses +< in order to access the sample of the gate. This is axis navigation syntax: It means to access the tail of the subject, and then the head, which is where the sample is stored in the binary tree model Hoon uses.

Urbit drops you into a shell and Hoon REPL when you start it, :dojo. To test this, simply enter %. 125 on one line and then the snippet for 125! Note there are two spaces between the dot and 1.

\$\endgroup\$
2
  • \$\begingroup\$ Hoon is a beautiful mystery. \$\endgroup\$
    – Lynn
    Mar 1 '16 at 1:10
  • 1
    \$\begingroup\$ It's a surprisingly nice language to code in! It takes a little bit to learn all the runes, but you don't even need to internalize them to read it since they belong in "families" based on the first symbol. The fact it's strongly typed and has a novel type system is just icing on the cake. \$\endgroup\$ Mar 1 '16 at 1:36
1
\$\begingroup\$

Desmos, 18 bytes

a=1
\prod _{n=1}^an

Uses the formula for a! instead of a!

Formula

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

Joy, 13 bytes

[1][*]primrec

30 char requirement in codegolf?

\$\endgroup\$
2
  • \$\begingroup\$ @FryAmTheEggman To make a function you would actually have to write DEFINE f==[1][*]primerec.. I believe program arguments are thrown on the stack when the program starts, and that everything outside a define block is executed \$\endgroup\$
    – BlackCap
    Jun 8 '16 at 20:12
  • 1
    \$\begingroup\$ It'd be best if you knew for sure rather than just believing ;) Anyway, seems alright then, but you also wouldn't run in to that 30 character requirement if you gave some explanation of your code :P \$\endgroup\$ Jun 8 '16 at 20:16
1
\$\begingroup\$

Yup, 33 31 29 bytes

*{{:0e-}]~{~|~|0~--e~}~#\}0e#

Here's the github. Invoke like this:

node yup.js <location>.yup -n <input>

Or

node yup.js -l "*{{:0e-}]~{~|~|0~--e~}~#\}0e#" -n <input>

or Try it online!

Examples:

λ node yup.js -l "*{{:0e-}]~{~|~|0~--e~}~#\}0e#" -n 5
120
λ node yup.js examples\factorial.yup -n 0
1

Explanation

*{{:0e-}]~{~|~|0~--e~}~#\}0e#
*                              ` take input
 {                       }     ` while TOS -- if zero, we advance to the }
                          0e#  ` print number 1 (exp(0))
                               ` otherwise (nonzero)
  {    }                       ` while TOS is not zero
   :                           ` duplicate TOS
    0                          ` push 0
     e                         ` pop 0, push exp(0) = 1
      -                        ` subtract 1
                               ` we eventually are at zero.
        ]                      ` we move that zero to the bottom of the stack
         ~                     ` switch top two for looping offset
          {~        ~}         ` while STOS
            |~|0~--e           ` multiply two elements (see further down)
                      ~        ` switch the top zero with the result
                       #       ` print the result
                        \      ` exit program (so we don't print the final one)

Multiplication

In this program, I have multiplication defined as thus:

|~|0~--e

First, observe 0~--. This pushes a zero behind the TOS, and subtracts twice:

command | stack
        | a b
0       | a b 0
~       | a 0 b
-       | a (-b)
-       | a - (-b) = a + b

This performs addition. Let's replace 0~-- with + for clarity:

|~|+e

Now, | is ln. So watch the stack:

command | stack
        | a b
|       | a ln(b)
~       | ln(b) a
|       | ln(b) ln(a)
+       | (ln(b)+ln(a))
e       | exp(ln(b)+ln(a))

And, by the theorem of logarithms, this is multiplication.

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

Maple, 17 bytes

n->`*`(seq(1..n))

Usage:

> f:=n->`*`(seq(1..n));
> f(0);
  1
> f(5);
  120
> f(125);
  188267717688892609974376770249160085759540364871492425887598231508353156331613598866882932889495923133646405445930057740630161919341380597818883457558547055524326375565007131770880000000000000000000000000000000
\$\endgroup\$
1
\$\begingroup\$

Fourier, 18 bytes

Non-competing: Fourier is newer than the challenge

1~NI(i^~iN*i~Ni)No

Try it online!

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

Oasis, 3 bytes

Try it online

n*1

Explanation:

n*1
n    Push n
 *   Multiply the two items on the top of the stack
     Because there is only one item on the stack, A(n - 1) is pushed
     Implicit output
  1  Special case A(0) = 1
\$\endgroup\$
1
\$\begingroup\$

Pushy, 3 bytes

Non-competing as the language postdates the challenge.

RP#

Explanation:

R  \ Push the inclusive range of the input
P  \ Push the product
#  \ Print

Try it online!

\$\endgroup\$
6
  • \$\begingroup\$ Factorial built-ins aren't allowed, sorry. \$\endgroup\$ Jan 19 '17 at 20:16
  • \$\begingroup\$ Is that in the question? I must have missed it. \$\endgroup\$
    – user63571
    Jan 19 '17 at 20:20
  • \$\begingroup\$ You can do RP# which gets the range and prints the product. \$\endgroup\$
    – FlipTack
    Jan 19 '17 at 20:23
  • \$\begingroup\$ Thanks for using Pushy, but as it postdates this challenge you should mark the answer as non-competing (and maybe include a TIO link) \$\endgroup\$
    – FlipTack
    Jan 19 '17 at 20:24
  • \$\begingroup\$ I'm a bit hazy on the time Pushy was made \$\endgroup\$
    – user63571
    Jan 19 '17 at 20:31
1
\$\begingroup\$

Alice, 13 bytes

/o
\i@/r.1~&*

Try it online!

Explanation

This is a basic framework for arithmetic programs to read and write integer I/O and process them in Cardinal mode:

/o
\i@/...

As for the actual computation:

r    Range: Replace the input N with 0, 1, 2, ..., N.
.    Duplicate N.
1~   Put a 1 underneath the copy to initialise the product correctly
     for N = 0.
&    Repeat the next command N times.
*    Multiply (N times, multiplying up the entire stack).
\$\endgroup\$
1 2 3
4
5
7

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.