# Find the Factorial!

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.

• 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)?
– Ami
Feb 6, 2011 at 22:43
• @SHiNKiROU, even golfscript can manage 125! less than 1/10th of a second and it's and interpreted interpreted language! Feb 8, 2011 at 3:21
• Completes in under a minute seems a very hardware-dependent requirement. Completes in under a minute on what hardware? Aug 24, 2017 at 18:05
• @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. Aug 24, 2017 at 21:20
• Why aren't built-ins allowed? You haven't specified what built-ins are, and if you said that it was up to a "reasonable person" to decide (which is completely subjective, but ignoring that), you still say that any form of eval is a built-in for the factorial, even though it evaluates code, not the factorial of a given number. May 7, 2019 at 2:02

# Python 2, 45 bytes

lambda n:reduce(long.__mul__,range(1,n+1),1L)


Try it online! Not the shortest Python solution but I thought it would be interesting to post a solution with reduce and long.__mul__.

• Doesn't work past 22. Jun 22, 2020 at 17:25
• @Calculuswhiz you are right, it doesn't. Python 2's int has a max size.
– RGS
Jun 22, 2020 at 17:33
• You can fix it at the cost of 2 bytes. Aug 13, 2020 at 0:49
• @Bubbler indeed I can, thanks o/
– RGS
Aug 13, 2020 at 7:11

# Flurry, 32 bytes

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


This is an anonymous function that takes an argument as a Church numeral and returns a Church numeral as output.

You can test it with the interpreter as follows:

$./Flurry -nin -c '{{}{<{}(<><<>()>{})>}[(<>())()]}{}' 9 362880  While the function itself returns quickly for N=125, the resulting Church numeral is too large to be practically useful for any purpose, including being converted into an integer and displayed by the interpreter. ## Explanation As with my Fibonacci answer, we're iterating a function $$\n\$$ times and storing an additional variable using the stack. In this case, the variable on the stack is the counter, so the step function looks like this: next = λn. n * push(1 + pop())  This admits a straightforward translation that uses function composition for multiplication and <><<>()> for the successor function: {<{} (<> <<> ()> {})>}  The main function is responsible for setting up initial values and calling next the appropriate number of times. It looks like this: main = λn. push(0); n (next) (1)  The Church numeral representation of zero is λab. b; in other words, a constant function that ignores its argument and returns the identity function. By coincidence, the Church numeral representation of one is λab. ab, which is itself the identity function. Thus we can rewrite it as: main = λn. n (next) (push(0) (arbitrary value))  This can again be translated directly: {{} {<{}(<><<>()>{})>} [(<>()) ()]}  # V (vim), 33 bytes S<C-r>=r<Tab>1,<C-r>"<BS>) <C-o>:%s/\n/*/g <C-o>C<C-r>=<C-r>"<BS><BS>  Try it online! Explanation: S<C-r>=r<Tab>1,<C-r>"<BS>) # Replace N with [1, ..., N] <C-o>:%s/\n/*/g # Merge all lines with * <C-o>C<C-r>=<C-r>"<BS><BS> # Remove trailing * and evaluate.  Overflows for any N greater than 49, but would work properly otherwise. # 05AB1E, 4 bytes Code: L0KP  Explanation: L # Create the list [1, ..., input] 0K # Remove all occurencies of zero P # Calculate the product  I have no idea why this works for 0, but it does. • Why does the list in the range [1,N] for N=0 becomes [0].. I did know taking the product of [] becomes 1. Both seem to be the ideal situation for the 0 edge-case here.. xD Aug 9, 2018 at 14:04 • Ý¦P is one byte shorter. May 29, 2019 at 13:28 # Pari/GP, 45 bytes x=input();forstep(y=x-1,1,-1,x=x*y);print(x);  Try it online! • Input is input. Mar 5 at 1:42 • @alephalpha I know that, but how do I convert it to an integer? Mar 5 at 1:43 • input reads the input as a PARI/GP expression and evaluate it. So when you input an integer, you don't need to convert. Mar 5 at 1:45 • Or you can write a function instead of a full program: x->forstep(y=x-1,1,-1,x=x*y);x Mar 5 at 1:45 • Or shorter: x->prod(y=1,x,y), or even x->x!. Mar 5 at 1:50 ## Befunge - 2x20 = 40 characters 0\:#v_# 1#<$v *\< >:1-:#^_>\:#^_  This is a function in that it is a standalone block of code not utilising the wraparound. You have to place the argument on the top of the stack then enter from the top-left going right, the function will exit from the bottom-right going right with the result on the top of the stack. E.g. to calculate the factorial of 125 555** 0\:#v_# 1#<$v *\< >:1-:#^_$>\:#^_$.@  Testing 0 0 0\:#v_# 1#<\$v *\<
>:1-:#^_$>\:#^_$    .@

• I know this is pretty old, but I think this is somewhat shorter and quicker : &:!#@_>:# 1# -# :# _$>\# :#* _$.@ (where & should be replaced by the input). It's 32 chars/bytes Apr 7, 2016 at 11:08

# J - 6 characters

*/>:i.


Does this count? I know it is very similar to the earlier J example, but it is a little shorter :)

I'm a beginner with J, but it's a lot of fun so far!

# In C (23 Characters)

This abuses the GCC "feature" that makes the last assignment count as a return if no return is specified.

f(a){a=a>0?f(a-1)*a:1;}


In proper C, 28 characters

f(a){return a>0?f(a-1)*a:1;}

• +1 for the GCC "feature". I think GCC even allows a block return value (Can remember doing something like this) 0 == ({printf("Hello, world!"); 0;});
– yyny
Feb 6, 2016 at 16:11

# Haskell, 20

Gee, I sure hope folds don't count as built in functions...

f n=foldl(*)1[1..n]

• product is probably shorter Aug 5, 2019 at 18:15

## Kona (11 6)

*/1.+!


K works right-to-left (for the most part), so we enumerate x (make a list/array of numbers from 0 to x-1), add 1 to it (list ranges 0 to x), then multiply all numbers together. If it weren't a requirement to compute 125!, I could save 1 more byte by eliminating . next to the 1. In any event, 125! is computed in mere milliseconds:

  */1.+!125.
1.882677e+209

• You don't need a lot of this. K has currying, so the entire answer becomes */1.+!: 6 bytes. Jun 25, 2015 at 14:43
• @kirbyfan64sos: True & I'll edit it in. I think when I wrote this ~18 months ago, I was still stuck on everything must be callable (i.e., function). Jun 25, 2015 at 15:00

# BrainFuck, 125 / CompressedFuck, 47

,[>+>+>>>+<<<<<-]>>-<[[>[->+>+<<]>>[-<<+>>]<<<-]>>>>[<<<<+>>>>-]<<<<->[-]>[<+>-]<<[>>>>+>+<<<<<-]>>>>>[<<<<<+>>>>>-]<<<<<-]>.


In 8-bit text encodings the program had 1000 bits.

However, any BrainFuck program could be stored with a 3-bit encoding. 125*3=375

375 bits / 8 = 47 bytes

EDIT: In the CompressedFuck format it has 47 bytes :)

Also I forgot to mention that this program only works with infinite-sized cells

• Still impressive. Feb 5, 2016 at 11:05
• Take a look at esolangs.org/wiki/CompressedFuck. But code-golf is more about competing with other programs in the same language than it is about competing with the rest, and 125 characters for brainfuck is pretty impressive :)
– yyny
Feb 6, 2016 at 16:15
• @YoYoYonnY thanks, I updated the answer Feb 8, 2016 at 12:40

## Pyth, 8 bytes

It's a shame that, 5 years after the challenge has been posted, there is no pyth answer. So I'm doing it now, even if it's ridiculous :). BTW, this is non-competiting, since the language is newer than the challenge...

Lu*GHSb1

You call it with yx, where x is a number. Test it here !

## Explanation

Lu*GHSb1
L          Defines a lambda 'y' with argument 'b'
Sb    Create a range from one to 'b' (function argument)
*GH      Lambda function that takes two arguments and multiply them
u     1   Reduce the range with the above lambda.

• L*F+1Sb is a bit shorter. Apr 9, 2016 at 19:08
• @FryAmTheEggman What kind of sorcery is this ? Apr 9, 2016 at 19:38
• F is fold, basically a reduce over the list, it expands pretty much into what you did, but without the start at 1 thing. So I manually add a 1 to the list Sb creates, which of course won't change the product. Apr 9, 2016 at 19:40
• @FryAmTheEggman I still have a lot to learn... Apr 9, 2016 at 20:20

# Python, 35 bytes

def f(n):return n and n*f(n-1) or 1


or

def f(n):return n*f(n-1) if n else 1

• I posted a shorter similar solution. No need to repeat it you don't have an extra insight. Feb 7, 2011 at 12:33
• @Alexandru if he wrote this without referencing your answer, I don't see why he shouldn't be allowed to post it just because it's longer. All Runners in a race get to post their score regardless of being first or last. Feb 20, 2019 at 14:49

# Factor, 24 bytes

[ [1,b] 1 [ * ] reduce ]


Try it online!

Computes 125 factorial very quickly

-2 bytes thanks to @chunes

# Factor, 12 bytes

[ [1,b] Π ]


Try it online!

Thanks to @chunes

• No need to print the result inside your function -- you can let it return the result to the data stack instead. Here's a simpler input setup as well: Try it online! Mar 26, 2021 at 9:45
• Now consider there's already a word for a multiplying reduce -- product. And the math.unicode vocabulary can shorten product to Π. Try it online! Mar 26, 2021 at 9:48

## PowerShell, 34

{($p=1)..$_-ge1|%{$p*=$_};$p}  Creates a list of numbers from one to the argument, selects those greater than or equal to one and multiplies those. For 0 the list 1, 0 will be created where then only 1 remains, yielding the correct answer. To test: > &{($p=1).."$args"-ge1|%{$p*=$_};$p} 125
1,88267717688893E+209


It's just a scriptblock; i.e. a function without a name.

## Pico, 23

f(x):if(x=0,1,x*f(x-1))


but Pico max out at 12:

>f(12)
479001600

• Does it work with 125? Jan 11, 2012 at 2:45
• @userunknown No, it doesn't as Pico's number type has the same limits as C's int. and fixing it so that it could would require implementing big integer multiplication and that would require at least 500-4000 characters. Jan 11, 2012 at 9:55

# Golfscript, 10 chars:

~,{)}%{*}*


## Mathematica

f = If[# > 0, # f[# - 1], 1] &
f[125] = 188267.....

• If[#>0,#0[#-1]#,1]& 19 bytes May 31, 2020 at 8:37

# Mathematica, 17

f = Times@@Range@#&


works more or less instantaneously for f[125].

• 1##& is 1 byte shorter than Times Jan 19, 2017 at 10:01

# Ruby, 35 characters,

def f(x);p 1.upto(x).inject(:*);end

Test:

f(5)

=> 120

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

• I like this solution! Sep 9, 2014 at 10:45

# Julia - 14 characters (19 with non-arbitrary-precision input)

f(n)=prod(1:n)


If you want it to work all the way up to n=125, precision becomes an issue. If requiring the input value to be "big" to match the output is unacceptable, then an extra 5 characters can be used to overcome the problem:

g(n)=prod(1:big(n))


big(n) converts n to an arbitrary precision integer, and the code remains in arbitrary precision from there. The alternative is, with the 14 character code above, making the input arbitrary precision - for instance, calling f(big(125)).

• And it works fast enough even for ridiculously high n. For n=100,000 my old i5-2410 laptop needs only 10.3 seconds. Displaying the 456,574 digits of the result is kind of a problem, though ;) At first I didn’t see that there already was a Julia solution. I would have almost made a double post.
– M L
Jun 28, 2015 at 7:44

# R, 22 (9 w/o function def; 35 w/ recursion)

Simply

f=function(n)prod(1:n)


Or, without defining a function:

prod(1:n)


Or, recursive:

f=function(n)if(n<2)1 else n*f(n-1)

• Only the last will work entirely (i.e. give 1 for n=0). A shorter solution would be : ifelse((n=scan())>0,prod(1:n),1), with 32 bytes. Aug 26, 2016 at 16:11
• @Frédéric or better yet "if"((n=scan())>0,prod(1:n),1) for 30 bytes. Aug 24, 2017 at 17:34
• @Giuseppe 0^(n=scan())+prod(1:n) is 22 bytes. Oct 31, 2019 at 7:33

# Swift: 43

var f:Double->Double;f={$0<1 ?0:f($0-1)*$0}  Swift is definitely not made for conciseness, but I though let's give it a try anyways. This solution is obviously recursive. There's also the more native Swift way to do it which is a bit longer (57 characters): let f={stride(from:1,through:$0,by:1.0).reduce(1){$0*$1}}


If it would be allowed to add an additional rule for very typey languages:

• You may add functions with the same behaviour as functions in the standard library for the purpose of shorter names

Then I would declare these two:

func ...(lhs: Double, rhs: Double) -> StrideThrough<Double> {
return stride(from: lhs, through: rhs, by: 1)
}

extension SequenceType {
func r<T>(initial: T, @noescape _ combine: (T, Self.Generator.Element) -> T) -> T {
return reduce(initial, combine: combine)
}
}


which redeclares stride(from: a, through: b, to:1.0) to a...b which I even think should be in the standard library, and reduce(a, combine: f) becomes r(a, f). This would one enable to do this:

let f={(1...$0).r(1,*)}  which would be 23 characters. I'm even thinking about creating a Code Golf Swift extension, which just redeclares all the standard methods to something more concise. Any of those can be called like: f(0) // 0 f(120) // 6.689502913449124e+198 f(170) // 7.257415615307994e+306  All of them can go up to 170, where the result will be Double.infinity when above. The times are as follows (for input 170): recursive (43 chars): 0.00000101 s native (rule-bend) : 0.00000027 s native : 0.00000027 s  • Why is it var f:Double->Double? Isn't that declaring the type twice? var seems to declare it to be of "variable" type, whereas Double->Double seems to declare it to be a function that accepts a double and returns a double. If this is not the case, can I get an explanation of the type signature for someone who doesn't know swift? Feb 5, 2016 at 6:21 • @Cyoce If I was using let instead, the compiler would complain because I'm using the function itself in its definition without it being declared beforehand. By using var we can trick the compiler into thinking that f is declared already. Feb 5, 2016 at 13:30 • ok, thanks for the clarification Feb 5, 2016 at 15:56 JavaScript ES6 21 chars Note: I'm just extending Casey Chu's answer using ES6 with minor change f=(n)=>n<2?1:n*f(n-1)  fiddle: Factorial 1) Does not use any built-in functions 2) Calculates factorial up to 170 3) Calculates factorial for 0 too 4) Execution time is less than a millisecond Note: It will work only in browsers that supports ES6. FF(22+) and Chrome(45+) supports arrow functions as per MDN at the time of writing this answer. • You don't need parens around the argument. f=n=>… is fine. Jan 27, 2016 at 3:34 # Simplex v.0.5, 12 bytes (The Docs page may be outdated; mainly, the * also increments the pointer and the J being the max of two elements.) h*M{*LTRpM}]  This defines a macro that performs the factorial function on the current byte. It maintains the structure of the strip, but inserts an extra 0 at the next byte. You can delete this by adding another command p before the function ends. This one works for inputs on a strip whose sole member is the input. I.e., a strip which looks like [N,/,/,...] (/ is the empty or null bit.) It clocks in at… # 11 Bytes!! This beats the GolfScript entry, FYI. h{*M}pwT1J]  This is what it does: h{*M}pwT1J] h ] ~~ define new macro { } ~~ repeat inside until zero met * ~~ copy the current byte and increment pointer M ~~ decrement byte p ~~ remove trailing zero wT ~~ spreads T (multiplication) across strip backwards; sets pointer to after the result 1J ~~ Takes the maximum of 1 and the current byte  Here the non-destructive version being used in an example code: h*M{*LTRpM}p]ih0o  This defines the macro, asks for numeric input (i), calls the first macro (h0) and outputs the byte as a number (o). Here is the pseudo-code I used: Function factorial(N) A = N - 1 While A > 1 N = A * N A = A - 1 End While Return N End Function  This is the expanded explanation. h ~~ open macro, implicit [ * ~~ A=N [N,A] M ~~ A=N-1 [N,A-1] { ~~ Loop until current byte is zero * ~~ [N,A-1,A-1] LT ~~ [N*(A-1),0,A-1] Rp ~~ [N*(A-1),A-1] M ~~ [N*(A-1),A-2] } p ~~ [N!] ] ~~ close macro  ## Burlesque, 4 bytes Burlesque has a built-in ?! to do that, but since that is forbidden by the rules we can just use ropd (runs in less than a fraction of a second): blsq ) 125ropd 188267717688892609974376770249160085759540364871492425887598231508353156331613598866882932889495923133646405445930057740630161919341380597818883457558547055524326375565007131770880000000000000000000000000000000 blsq ) 5ropd 120 blsq ) 125?! 188267717688892609974376770249160085759540364871492425887598231508353156331613598866882932889495923133646405445930057740630161919341380597818883457558547055524326375565007131770880000000000000000000000000000000  Basically factorial is just the product of a list [1..N] and ro creates [1..N] and pd is the product of a list. Simple as that. • Does this account for 0!=1? Nov 23, 2015 at 20:16 • Yes, because pd (Product) is defined to be 1 for empty lists. Nov 24, 2015 at 9:37 ## Python - 33 f=lambda n:n*(n and f(n-1))+(n<1)  • We already have this shorter answer using the same approach. Jan 24, 2016 at 23:25 # JacobFck, noncompeting 43 bytes. This answer is noncompeting, because the language was invented after the challenge was posted. Might be a bit late but this is too good to pass up. <^0|=_s~$t$c:m^1^c|=_e-$c^t*\$t_m:e^t>!:s^1>


Here is the commented and expanded: here

## Python, 29 bytes

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