# 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 '11 at 22:43
• @SHiNKiROU, even golfscript can manage 125! less than 1/10th of a second and it's and interpreted interpreted language! – gnibbler Feb 8 '11 at 3:21
• @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. – Michael Stern Jan 7 '14 at 3:18
• Completes in under a minute seems a very hardware-dependent requirement. Completes in under a minute on what hardware? – sergiol Aug 24 '17 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. – Kevin Brown Aug 24 '17 at 21:20

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

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

• product is probably shorter – univalence Aug 5 '19 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. – kirbyfan64sos Jun 25 '15 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). – Kyle Kanos Jun 25 '15 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. – Sainan Feb 5 '16 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 '16 at 16:15
• @YoYoYonnY thanks, I updated the answer – KeksArmee Feb 8 '16 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. – FryAmTheEggman Apr 9 '16 at 19:08
• @FryAmTheEggman What kind of sorcery is this ? – FliiFe Apr 9 '16 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. – FryAmTheEggman Apr 9 '16 at 19:40
• @FryAmTheEggman I still have a lot to learn... – FliiFe Apr 9 '16 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. – Alexandru Feb 7 '11 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. – akozi Feb 20 '19 at 14:49

# Jelly, 2 bytes

RP


Try it online!

Alternatively, a builtin answer is one byte:

!


Try it online!

# 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. – Calculuswhiz Jun 22 '20 at 17:25
• @Calculuswhiz you are right, it doesn't. Python 2's int has a max size. – RGS Jun 22 '20 at 17:33
• You can fix it at the cost of 2 bytes. – Bubbler Aug 13 '20 at 0:49
• @Bubbler indeed I can, thanks o/ – RGS Aug 13 '20 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: {{} {<{}(<><<>()>{})>} [(<>()) ()]}  # 8088 / 8087 machine code, 13 bytes D9 E8 FLD1 ; start with 1 E3 08 JCXZ DONE ; if N = 0, return 1 FACT_LOOP: 51 PUSH CX ; push current N onto stack 8B F4 MOV SI, SP ; SI to top of stack for N DE 0C FIMUL WORD PTR[SI] ; ST = ST * N 59 POP CX ; remove N from stack E2 F8 LOOP FACT_LOOP ; decrement N, loop until N = 0 DONE: C3 RET ; return to caller  Input $$\n\$$ is in CX, output $$\{n!}\$$ is in ST(0). Test output displayed using Borland Turbo Debugger 3: n = 1: n = 15: n = 50: n = 125: Notes: • Calculates $$\{125!}\$$ in an imperceptible amount of time (difficult to accurately profile in DOS) • Language is not newer than the challenge • "Language is not newer than the challenge" facepalm – S.S. Anne Mar 18 '20 at 19:03 ## 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. # C#: 37 int f(int n){return n>0?n*f(n-1):1;} • This function returns 1 always. – Alexandru Jul 4 '11 at 11:15 • whoopsies, you're right. – Origamiguy Jul 10 '11 at 12:38 • int is way too small to hold 125!, which is something like 1.88e+209. – Justin Morgan Jul 12 '11 at 19:05 ## 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? – user unknown Jan 11 '12 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. – Dan D. Jan 11 '12 at 9:55 # Golfscript, 10 chars: ~,{)}%{*}*  ## Mathematica f = If[# > 0, # f[# - 1], 1] & f[125] = 188267.....  • If[#>0,#0[#-1]#,1]& 19 bytes – J42161217 May 31 '20 at 8:37 # Mathematica, 17 f = Times@@Range@#&  works more or less instantaneously for f[125]. • 1##& is 1 byte shorter than Times – LLlAMnYP Jan 19 '17 at 10:01 # Ruby, 35 characters, def f(x);p 1.upto(x).inject(:*);end Test: f(5) => 120 # 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 '15 at 7:44 # Bash+coreutils, 21 bytes seq$1|paste -sd\*|bc


# 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. – Frédéric Aug 26 '16 at 16:11
• @Frédéric or better yet "if"((n=scan())>0,prod(1:n),1) for 30 bytes. – Giuseppe Aug 24 '17 at 17:34
• @Giuseppe 0^(n=scan())+prod(1:n) is 22 bytes. – Robin Ryder Oct 31 '19 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? – Cyoce Feb 5 '16 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. – Kametrixom Feb 5 '16 at 13:30 • ok, thanks for the clarification – Cyoce Feb 5 '16 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. – Cyoce Jan 27 '16 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? – AdmBorkBork Nov 23 '15 at 20:16 • Yes, because pd (Product) is defined to be 1 for empty lists. – mroman Nov 24 '15 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. – lirtosiast Jan 24 '16 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  ## JavaScript, 52 bytes function f(m){n=1;for(i=1;i<=m;i++){n*=i;}return n;}  • You can shorten that too function f(m){for(n=i=1;i<=m;)n*=i++;return n}. It's 6 character in less. – HoLyVieR Feb 7 '11 at 3:57 ## K, 9 bytes f:*/1f+!: k) f 125 1.882677e+209  Computes 125! in under a millisecond; 15ms for 10k iterations # 05AB1E, 4 bytes (non-competing) Since the language postdates the challenge, this is non-competing 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 – Kevin Cruijssen Aug 9 '18 at 14:04 • Ý¦P is one byte shorter. – Grimmy May 29 '19 at 13:28 # Detour (non-competing), 5 bytes ?1RP.  Try it online! ?1 means "if n is 0, set n to 1" RP means product [1..n], . is output Terminates in 6ms for 170 (the highest number whose factorial can be represented in JS) on my craptop 4-year-old macbook air with 2GB RAM. Here's a 100% symbolic method: # Detour, 10 bytes [{<]?1}&*.  Try it online! Old recursive way: # Detour, 1713 11 bytes <Q0\ .$;p>P


Try it online!

This is non-competing, as I just finished the language today.

There's no good way to explain it, the website will give a visualization of the data flow at runtime.

It's a shame I have to handle 0!=1, or this could be a one-liner.

Another 11-byte solution (faster):

# Detour, 11 bytes

?1[\$Q<]x
P.


Try it online!

• add permalinks. o_o – Conor O'Brien Jan 21 '16 at 4:13
• @CᴏɴᴏʀO'Bʀɪᴇɴ as a matter of fact I am working on non-essentials such as permalinks and speed sliders now. :) – Cyoce Jan 21 '16 at 4:21
• – Conor O'Brien Jan 21 '16 at 4:30
• @CᴏɴᴏʀO'Bʀɪᴇɴ done. – Cyoce Jan 21 '16 at 5:11