# Is this number a factorial?

Given a natural number as input, your task is to output a truthy or falsey value based on whether the input is a factorial of any natural number. You can assume that the input number will always be in the range of numbers supported by your language, but you must not abuse native number types to trivialize the problem.

Standard Loopholes apply.

## Input

You'll be given a natural number (of type Integer or similar).

You can take input in any way you want except assuming it to be in a predefined variable. Reading from file, console, dialog box (prompt), input box etc. is allowed. Input as function argument is allowed as well!

## Output

Your program should output a truthy or falsey value based on whether the input number is a factorial of any natural number.

Make sure that your truthy/falsey values are consistent for all inputs, i.e, if you are using pair of 1 and 0 to denote truthy and falsey values respectively, then your program must output 1 for all inputs that should have truthy values and 0 for all inputs that should have falsey values.

You can take output in any way you want except writing it to a variable. Writing to file, console, screen etc. is allowed. Function return is allowed as well!

Your program must not produce errors for any input!

## Test Cases

Input     Output

1         Truthy (0! or 1!)
2         Truthy (2!)
3         Falsey
4         Falsey
5         Falsey
6         Truthy (3!)
7         Falsey
8         Falsey
24        Truthy (4!)
120       Truthy (5!)


## Winning Criterion

This is , so the shortest code in bytes wins!

• If the language supports only numbers in the range {0,1}, can I expect the input to always be 1? May 20, 2017 at 9:45
• @eush77 Abusing native number types to trivialize a problem is forbidden by default. May 20, 2017 at 17:56
• is 4! a truthy? May 20, 2017 at 22:04
• Question: Why aren't you using the I/O defaults? May 22, 2017 at 23:15
• @CalculatorFeline Didn't know they existed, if you still want to know the answer :-P Sorry Mar 18, 2021 at 11:14

# Brachylog, 1 byte

ḟ


Try it online!

### Explanation

ḟ is a built-in that asserts the following relation: its output is the factorial of its input. We simply give it a set output and see whether it suceeds or not with a variable input.

• @BetaDecay That's because it's the way it's printed in Prolog (this has to do with the fact that true. is a statement and true is not) May 20, 2017 at 9:46
• It's a trivial solution, but it's clever because of the way prolog works. May 21, 2017 at 6:18
• @Nayuki This one, which is custom May 22, 2017 at 21:11
• First custom languages, then custom encodings... code golf is dead. We've completely subverted the whole point of these fun problems in the first place May 23, 2017 at 5:57
• @Alexander Custom encodings are irrelevant to whatever problem you're talking about. I could use any "existing" encoding instead and it would still be 1 byte. It would just be much less readable. May 23, 2017 at 6:15

# ECMAScript Regex, 733⚛690⚛158119118 92 bytes

• dropped 1 byte (119 → 118) using a trick found by Grimmy that can futher shorten division in the case that the quotient is guaranteed to be greater than or equal to the divisor
• dropped 26 bytes (118 (117🐌) → 92) thanks to Grimmy in collaboration with H.PWiz. I've finally analyzed, commented, and proved this version.

My interest in regex has been sparked with renewed vigor after over 4½ years of inactivity. As such, I went in search of more natural number sets and functions to match with unary ECMAScript regexes, resumed improving my regex engine, and started brushing up on PCRE as well.

I'm fascinated by the alienness of constructing mathematical functions in ECMAScript regex. Problems must be approached from an entirely different perspective, and until the arrival of a key insight, it's unknown whether they're solvable at all. It forces casting a much wider net in finding which mathematical properties might be able to be used to make a particular problem solvable.

Matching factorial numbers was a problem I didn't even consider tackling in 2014 – or if I did, only momentarily, dismissing it as too unlikely to be possible. But last month, I realized that it could be done.

As with my other ECMA regex posts, I'll give a warning: I highly recommend learning how to solve unary mathematical problems in ECMAScript regex. It's been a fascinating journey for me, and I don't want to spoil it for anybody who might potentially want to try it themselves, especially those with an interest in number theory. See this earlier post for a list of consecutively spoiler-tagged recommended problems to solve one by one.

So do not read any further if you don't want some advanced unary regex magic spoiled for you. If you do want to take a shot at figuring out this magic yourself, I highly recommend starting by solving some problems in ECMAScript regex as outlined in that post linked above.

This was my idea:

The problem with matching this number set, as with most others, is that in ECMA it's usually not possible to keep track of two changing numbers in a loop. Sometimes they can be multiplexed (e.g. powers of the same base can be added together unambiguously), but it depends on their properties. So I couldn't just start with the input number, and divide it by an incrementally increasing dividend until reaching 1 (or so I thought, at least).

Then I did some research on the multiplicities of prime factors in factorial numbers, and learned that there's a formula for this – and it's one that I could probably implement in an ECMA regex!

After stewing on it for a while, and constructing some other regexes in the meantime, I took up the task of writing the factorial regex. It took a number of hours, but ended up working nicely. As an added bonus, the algorithm could return the inverse factorial as a match. There was no avoiding it, even; by the very nature of how it must be implemented in ECMA, it's necessary to take a guess as to what the inverse factorial is before doing anything else.

The downside was that this algorithm made for a very long regex... but I was pleased that it ended up requiring a technique used in my 651 byte multiplication regex (the one that ended up being obsolete, because a different method made for a 50 byte regex). I had been hoping a problem would pop up that required this trick: Operating on two numbers, which are both powers of the same base, in a loop, by adding them together unambiguously and separating them at each iteration.

But because of the difficulty and length of this algorithm, I used molecular lookaheads (of the form (?*...)) to implement it. That is a feature not in ECMAScript or any other mainstream regex engine, but one that I had implemented in my engine. Without any captures inside a molecular lookahead, it's functionally equivalent to an atomic lookahead, but with captures it can be very powerful. The engine will backtrack into the lookahead, and this can be used to conjecture a value which cycles through all possibilities (for later testing) without consuming characters of the input. Using them can make for a much cleaner implementation. (Variable-length lookbehind is for most uses at least equal in power to molecular lookahead, but the latter tends to make for more straightforward and elegant implementations. Molecular lookahead may also be able to do things in loops that aren't possible with variable-length lookebehind.)

So the 733 and 690 byte lengths do not actually represent ECMAScript-compatible incarnations of the solution – hence the "⚛" after them; it's surely possible to port that algorithm to pure ECMAScript (which would increase its length quite a bit) but I didn't get around to it... because I thought of a much simpler and more compact algorithm! One that could easily be implemented without molecular lookaheads. It's also significantly faster.

This new one, like the previous, must take a guess at the inverse factorial M, cycling through all possibilities and testing them for a match. It divides N by 2 to make room for the work it needs to do, and then seeds a loop in which it will repeatedly divide the input by a divisor that starts at 3 and increments up to M-1.* (As such, 1! and 2! can't be matched by the main algorithm, and must be dealt with separately.) The divisor is kept track of by adding it to the running quotient; these two numbers can be unambiguously separated because, assuming M! == N, the running quotient will continue to be divisible by M until it equals M.

*But it later turned out that starting the divisor at M-1, and decrementing down to 3, can result in a shorter regex. This was part of golfing 118 → 92 bytes.

This regex does division-by-a-variable in the innermost portion of the loop. The division algorithm is the same as in my other regexes (and similar to the multiplication algorithm): for A≤B, A*B=C if any only if C%A=0 and B is the largest number which satisfies B≤C and C%B=0 and (C-B-(A-1))%(B-1)=0, where C is the dividend, A is the divisor, and B is the quotient. (A similar algorithm can be used for the case that A≥B, and if it is not known how A compares to B, one extra divisibility test is all that is needed.)

So I love that the problem was able to be reduced to even less complexity than my golf-optimized Fibonacci regex, but I do sigh with disappointment that my multiplexing-powers-of-the-same-base technique will have to wait for another problem that actually requires it, because this one doesn't. It's the story of my 651 byte multiplication algorithm being supplanted by a 50 byte one, all over again!

With no further ado, here's the regex:

True/false version (92 bytes):

^(((x+)\3+)(?=\3\3\2$)(x(?=\3+(x*))(?=\5+$)(?=((x+)(?=\5\7*$)x)\6*$)\3+(?=\5\7$))*\3xx|x?)x$

Try it online!

Return inverse factorial or no-match (109 bytes):

^(?=((x(x*))\2+)(?=\2\2\1$)(x(?=\2+(x*))(?=\5+$)(?=((x+)(?=\5\7*$)x)\6*$)\2+(?=\5\7$))*\2xxx$)(\3|xx)?x|^xx?$ (relies on ECMAScript no-empty-optional behavior) Try it online! Return inverse factorial or no-match, in ECMAScript + \K (103 bytes): ^(((x(x*))\3+)(?=\3\3\2$)(x(?=\3+(x*))(?=\6+$)(?=((x+)(?=\6\8*$)x)\7*$)\3+(?=\6\8$))*x\Kxx(\K\4)?|x?)x$ (relies on ECMAScript no-empty-optional behavior) Return inverse factorial or no-match, in ECMAScript + (?*) (103 bytes): When adapted to molecular lookahead, this regex can match $$\3!\$$ in a straightforward way: ^(?=(?*(x+))(\1*)(?=\1\1\2$)(x(?=\1+(x*))(?=\4+$)(?=((x+)(?=\4\6*$)x)\5*$)\1+(?=\4\6$))*\1xxx$)\1|^xx?$

Return inverse factorial or no-match, in ECMAScript + (?*) + \K (99 bytes):

^(?*(x+))(\1*)(?=\1\1\2$)(x(?=\1+(x*))(?=\4+$)(?=((x+)(?=\4\6*$)x)\5*$)\1+(?=\4\6$))*xxx\K\1$|^xx?$ And the free-spaced version with comments: # Match factorial numbers in the domain ^x*$
^                           # N = tail = input
(
((x+)\3+)(?=\3\3\2$) # \3 = conjectured inverse factorial of N if N >= 4! = 24; # \2 = N/2 - \3; assert tail is divisible by \3 and by 2; # assert tail is divisible by a number >= 6; # tail = N/2 + \3; # Note that if N = 3! = 6, \3 will behave differently, # because sticking to the pattern, we'd need \2=0, which # is of course impossible, because we must have \2 >= \3. # However, when N=6, \3=1 happens to result in a match after # zero loop iterations. # The loop is seeded: X = N/2; I = \3 - 1; tail = X + I + 1 # The loop will divide X by the numbers in the range \3-1 downward to 3, inclusive. # Since we don't divide by \3 itself, and already divided by 2, if N is factorial, # the end result of these divisions will be X = \3. ( # Main loop x # tail = tail-1 = X + I (?=\3+(x*)) # \5 = tail % \3 = I; assert X >= \3 (?=\5+$)            # assert X is divisible by I; if \3=1, then \5=0,
# and the main loop will exit after zero iterations
(?=
(               # \6 = tail / \5 = (X+I)/I = X/I + 1
(x+)        # \7 = \6-1 = X/I; assert X/I >= 1
(?=\5\7*$) x ) \6*$
)
\3+(?=\5\7$) # Prepare the next iteration of the loop: X = \7; I -= 1; # tail = X + I + 1; # Assert that the tail difference is divisible by \3, i.e. # that, with our previous values of X and I: # X + I - (X/I + I-1 + 1) # = X/I*(I-1) is divisible by \3 # Since I is coprime with I-1, if X was divisible by \3 # but X/I is not, then X/I*(I-1) will not be either, so this # indirectly asserts that X/I, our new X, is divisible by \3. # The initial value of X was asserted to be divisible by \3 # before the loop started, so by induction, every new value # of X will be asserted to be divisible by \3. This is # important because we use modulo by \3 to recover the value # of I at the beginning of each loop iteration. # And if N = \3! and the previous of I=2 and X was able to be # divided by 2, this will force this iteration of the loop to # fail, and the loop will exit with the values of X and I # backtracked to their values before this iteration, i.e. # with X = \3 and I = 2. )* \3xx # assert tail = \3 + 2 + 1, meaning when the loop finished # we ended up with X = \3 and I = 2 | x? # match N=1 and N=2, which the main algorithm can't ) x$


The full history of my golf optimizations of these regexes is on github:

## Optimized for returning the inverse factorial

The above algorithm has the quirk of happening to match $$\3!\$$ by coincidence, yielding a false inverse factorial value of $$\1\$$ instead of $$\3\$$. This complicates turning the regex into one that returns the inverse factorial as a match.

The below algorithm is cleaner in that it straightforwardly matches $$\3!\$$ with the correct inverse factorial value. It does however result in a longer true/false regex.

True/false version – returns inverse factorial minus 1 in \1 (96 bytes):

^(x*)(?=x(x\1)*$)((?=\2*(x*)(?=\2)\4(x+))(?=\5+$)(?=((x*)(?=\5\7*$)x)\6*$)\2*(?=x\4\6$)\1)*\1x?$

Try it online! - true/false
Try it online! - return value in \1

Return inverse factorial or no-match (103 bytes):

^(?=(x*)(?=x(x\1)*$)((?=\2*(x*)(?=\2)\4(x*))(?=\5+$)(?=((x*)(?=\5\7*$)x)\6*$)\2*(?=x\4\6$)\1)*\1x?$)x\1

Try it online!

Return inverse factorial in \1 or no-match, in ECMAScript + (?*) (97 bytes):

^(?*(x(x*))\1*$)\2((?=\1*(x*)(?=\1)\4(x*))(?=\5+$)(?=((x*)(?=\5\7*$)x)\6*$)\1*(?=x\4\6$)\2)*\2x?$

Return inverse factorial or no-match, in ECMAScript + \K (101 bytes):

^(x*)(?=x(x\1)*$)((?=\2*(x*)(?=\2)\4(x(x*)))(?=\5+$)(?=((x*)(?=\5\8*$)x)\7*$)\2*\4(?=x\7$)\K\6)*\1x?$

Return inverse factorial minus 1 or no-match, in ECMAScript + \K (98 bytes):

^(x*)(?=x(x\1)*$)((?=\2*(x*)(?=\2)\4(x+))(?=\5+$)(?=((x*)(?=\5\7*$)x)\6*$)\2*(?=x\4\6$)\1)*x?\K\1$

# Match factorial numbers in the domain ^x*$and return the inverse factorial as the match ^ # N = tail = input (?= (x*) # \1 = conjectured inverse factorial - 1; tail -= \1 (?=x(x\1)*$)            # \2 = conjectured inverse factorial; assert \2 divides N;
#      assert N >= 2 * \2;
# If N=1 or N=2, then \2 will be unset (having experienced 0
# iterations of its mini-loop) and \1=0 or \1=1, respectively
# The loop is seeded: X = N; I = \1; tail = X - I
# The loop will divide X by the numbers in the range \2-1 downward to 2, inclusive.
# We don't divide by \2 itself, so if N is factorial, the end result of these
# divisions will be X = \2 - 1.
(
(?=
\2*(x*)(?=\2)   # \4 = tail % \2 = \2-I; assert tail >= \2
\4(x*)          # \5 = \2-\4 = I
)
(?=\5+$) # assert X is divisible by I (?= ( # \6 = tail / \5 = (X-I)/I = X/I - 1 (x*) # \7 = \6-1 (?=\5\7*$)
x
)
\6*$) \2*(?=x\4\6$)\1     # Prepare next iteration of loop: X = \6+1; I -= 1;
# tail = X - I;
# Assert that, with our previous values of X and I:
#      (X - I) - (1 + \2-I + X/I - 1)
#    = X - \2 - X/I                   is divisible by \2
# Assuming X was already divisible by \2, this asserts
# X/I is also divisible by \2. The initial value of X was
# asserted to be divisible by \2, so by induction, every
# new value of X will be asserted to be divisible by \2.
# This is important because we use modulo by \2 to recover
# the value of I at the beginning of each loop iteration.
# And if I = 1, this iteration of the loop will fail
# because in this case,
#      1 + \4 + \6 > tail
#      \2-I + X/I > X - I
#      \2 > 0
# and the loop will exit with I = 1.
# But note that if N = \2!, then when we reach I = 1, and
# thus have X = \2 and tail = \2 - 1, this iteration of the
# loop will have already failed at its beginning due to the
# assertion that tail >= \2.
)*
\1x?$# assert tail = \1 = \2-1, meaning when the loop finished we # ended up with X = \2 and I = 1, # or tail = \1+1 (what would be \2), which can only happen if # \2 is unset and N=1 or N=2 and the loop did 0 iterations. ) x\1 # return \1 + 1 as a match; don't use \2 because it will be # unset in the case of N=1 or N=2  # Jelly, 4 bytes Œ?IE  Not the shortest Jelly answer, but it's rather efficient. Try it online! ### How it works Œ?IE Main link. Argument: n Œ? Yield the n-th permutation of the positive integers, without the sorted tail. For 120, this yields [5, 4, 3, 2, 1], the tail being [6, 7, 8, ...]. I Increments; compute all forward differences. For 120, this yields [-1, -1, -1, -1]. E Check if all differences are equal.  • Because us code golfers care about efficiency. – Okx May 20, 2017 at 15:10 • It's a dramatic complexity improvement at the cost of one byte and it's a clever use of a built-in if I may say so myself. ¯\_(ツ)_/¯ May 20, 2017 at 15:16 • Interestingly, this returns true for 0, while @LeakyNun's 3 byte answer, while much slower in general, correctly returns false for 0. Are extra bytes needed to return false for 0 in an efficient-execution-time answer? Jan 31, 2019 at 17:43 • @Deadcode Checking for 0 would require two extra bytes. If not sure if the OP's definition of "natural numbers" includes 0 or not. The test cases don't... Jan 31, 2019 at 19:07 # Jelly, 3 bytes !€ċ  Try it online! 1 for yes, 0 for no. ## How it works !€ċ argument as z !€ [1!, 2!, 3!, ..., z!] ċ count the number of occurrence of z  ## JavaScript (ES6), 3029 28 bytes Expects a positive integer. Returns -1 for falsy and -2 for truthy. f=(n,k=2)=>n>1?f(n/k,k+1):~n console.log(1, '-->',f(1)) // Truthy (0! or 1!) console.log(2, '-->',f(2)) // Truthy (2!) console.log(3, '-->',f(3)) // Falsey console.log(4, '-->',f(4)) // Falsey console.log(5, '-->',f(5)) // Falsey console.log(6, '-->',f(6)) // Truthy (3!) console.log(7, '-->',f(7)) // Falsey console.log(8, '-->',f(8)) // Falsey console.log(24, '-->',f(24)) // Truthy (4!) console.log(120,'-->',f(120)) // Truthy (5!) Note: This function supports pretty large inputs (you should read this as: 'pretty large for JS'). It should work safely up to 253 - 1. It will fail for sure starting at N = 121,645,100,408,831,992, this input being rounded to 19! = 121,645,100,408,832,000 because of its IEEE-754 encoding. There may be other false positive results before 121,645,100,408,831,991 because of rounding errors, but I don't know for sure. • Nice - really like the use of ~ at the end. May 21, 2017 at 22:46 • Can you edit so I can undownvote? (If you want to know why I downvoted, it's because I forgot about this question's unusual I/O rules.) May 25, 2017 at 1:15 • @Arnauld Undownvoted. May 26, 2017 at 21:02 # Python 3, 39 38 bytes f=lambda n,i=1:n>1and f(n/i,i+1)or n<1  A recursive function taking an integer, n, returning a boolean value inversley representing the result (truthy: False, falsey: True) Try it online! Repeatedly divides n by i, with an initial value of 1, until the remainder is less than or equal to 1 then tests if that remainder is less then 1, only factorials will end with a remainder equal to 1, and < is a byte shorter than ==. • @ovs we have been restricted to a two consistent outputs. That, unfortunately, returns 1 for all factorials except 1 for which it returns True. May 20, 2017 at 10:29 # Java 8, 46 bytes i->{int j=1,c=0;for(;j<i;j*=++c);return j==i;}  This is based on Roman Gräf's entry that I was able to knock a dozen or so bytes off of. I would have suggested it there but I don't have enough reputation to comment yet! My modified test runner code: import java.util.function.Function; import java.util.stream.IntStream; public class IsFactorial { public static Function<Integer, Boolean> isFactorial = i->{int j=1,c=0;for(;j<i;j*=++c);return j==i;}; public static int[] truthyCases = {1,2,6,24,120}; public static int[] falsyCases = {3,4,5,7,8}; public static void main(String[] args){ System.out.println( IntStream.of(truthyCases).allMatch(i->isFactorial.apply(i)) && IntStream.of(falsyCases).allMatch(i->!isFactorial.apply(i))); } }  # Retina, 50 38 bytes 12 bytes saved thanks to @Neil by combining shortening the loop and by getting rid of the ; .+ 1¶$&$* +^(1+)¶(\1)+$
1$1¶$#2$* ¶.$


Try it online!

Outputs 1 for true and 0 for false.

.+ matches the entire number

1¶$&$* replacing it with 1 followed by a newline and the match converted to unary

The remaining program divides the unary number in the bottom line by successively increasing positive integers, kept track in the top line, while it is possible to do so.

+ loop until string remains same

• ^(1+)¶(\1)+$ match the top line many 1s and a multiple of it many 1s on the bottom line and replace it with • 1$1¶$#2$* the top line many 1s with another 1, that is, increasing the number represented by the top line by 1, followed by the newline and the number of matches of the top line in the bottom line (ie. count of matches of the second capturing group) many 1s, that is, dividing the bottom number by the top number

Once it is no longer possible to do so,

¶.$ give the number of matches of this regex, ie. does there exist a lone 1 on the bottom line, which only happens if the number is a factorial If no-crash/crash is allowed instead of truthy/falsy values, then I can get 36 34 bytes. ^ 1¶ {.+$
$* ^(1+)¶(\1)+$
1$1¶$#2


This goes by the same approach, but combines the $* into the third and fourth lines. The third line onward is a part of the same loop, { is short for +( where the ( groups the remaining lines into the loop. Factorials end in the program breaking out of the loop, while non-factorials get stuck in the loop forever until Retina throws an OverflowException caused by the last replacement failing thus having the bottom in unary instead of in decimal, and the first replacement of the loop converts the bottom line from decimal to unary, so it blows up quickly. • Save a byte by removing the 1 as it is implied when $* is at the end of the replacement.
– Neil
May 20, 2017 at 10:38
• Better still, combine the $* with the other two lines. – Neil May 20, 2017 at 10:41 • Try it online! – Neil May 20, 2017 at 10:43 • I'm impressed that you found a way to crash Retina conditionally. :) May 20, 2017 at 16:36 • Can you add an explanation? May 22, 2017 at 23:13 # 05AB1E, 4 bytes L!QO  Try it online! Explanation L # range [1 ... input] ! # calculate factorial of each Q # compare with input for equality O # sum  • Wouldn't you need to duplicate the input first because L pops its input? Also, Å! gives you a list of factorial less than or equal to the input. May 21, 2017 at 8:33 • @NeilA. Fortunately the input is popped again if there are not enough arguments on the stack for an operation, so I don't need D here. Good catch about Å!. I always forget about the list-commands. It won't save any bytes, but it is more efficient for sure. May 21, 2017 at 8:37 • I didn't know about input being popped again...that sure could save a lot of bytes. May 21, 2017 at 8:42 • @NeilA. It is a fairly new feature. It was added less than a month ago I think. May 21, 2017 at 8:53 # C++, 102100 92 Bytes #include<cmath> int a(int n){int i=n,j=0;for(;i;)j|=lround(exp(lgamma(i--+1)))==n;return j;}  Loops through all the values from 0 to n and calculates the factorial and then checks if it's equal to n. Thanks Christoph! (saved 8 bytes) • Hi! Welcome to PPCG! Nice first answer! Good luck for the future! May 20, 2017 at 17:09 • Nice first answer ! You can save a few byte like this: int a(int n){int i=n,j=0;for(;i;)j|=lround(exp(lgamma(i--+1)))==n;return j;}. lround and lgamma are already C++11 so could simply #include<cmath>. Maybe you can even further improve my suggestions :) May 22, 2017 at 9:04 # Haskell, 43 26 bytes f n=elem n$scanl1(*)[1..n]


Try it online!

• Saved 17 bytes, thanks to Laikoni
• f n=elem n$scanl1(*)[1..n] is ridiculous inefficient but shorter. May 20, 2017 at 11:17 • Isn't there some rule about code efficiency? May 20, 2017 at 12:15 • None that I am aware of. code-golf asks for a solution in as few bytes as possible without any efficiency statements. Also on my machine the function works up to 40430 without noticeable delay. May 20, 2017 at 12:44 • I meant something along the lines of "the solution should terminate within a reasonable timeframe", but I guess it fits the requirements either way. Thanks! May 20, 2017 at 16:24 • Nice and simple. I thought I could do better with division—say, divMod by [1..] successively until reaching a zero remainder with a quotient of 1 (factorial) or a nonzero remainder (non-factorial), but it doesn’t seem to be the right approach. I did find this cute 46-character solution, though: f|let x%n=mod n x==0&&(x+1)%div n x||n==1=(1%). May 23, 2017 at 2:48 # Haskell, 38 bytes m#n=n<2||mod n m<1&&(m+1)#div n m (2#)  Try it online! Example usage: (2#) 24. Returns True or False. This is the shortest I could get while still being very efficient. Even for numbers as large as 145183092028285869634070784086308284983740379224208358846781574688061991349156420080065207861248000000000000000000  the result is immediately given. The solution works by dividing the input n by m = 2,3,4,5,... until either the result is one or n is not divisible by m. For the shorter but incredible inefficient 26-byte solution which computes n! for inputs that are not factorials look here. # MATL, 5 bytes t:Ypm  Try it online! ### Explanation t % Implicit input. Duplicate : % Range from 1 to that Yp % Cumulative product m % Ismember. Implicit display  # Fourier, 40 39 bytes I~Q1~N(i^~i*N~N{Q}{1~Xo}N>Q{1}{1~X0o}X)  Try it on FourIDE! Basically multiplies the number N by an increasing amount until N is either equal to (output 1) or greater than (output 0) the input. Explanation Pseudocode: Q = Input N = 1 While X != 1 i += 1 N = N*i If N = Q Then Print 1 X = 1 End If If N > Q Then Print 0 X = 1 End If End While  # Japt, 8 6 bytes ol x¥U  Try it online! This outputs 0 for false and 1 for true. # Explanation  ol x¥ U Uol x==U Uo # Create the range [0 ... input] l # Replace each element by its factorial ==U # Compare each element to the input (yielding 1 if equal and 0 otherwise) x # And sum the result  • I really should add a "contains" built-in :P May 20, 2017 at 11:14 • Oh hey, you could change aU ¦J to x¥U (map each X to X==U and sum), though it won't work on TIO. May 20, 2017 at 11:16 • Fails for 2 becuase o will only give you [0,1]. Here's a fix with a 1 byte saving. Sep 26, 2017 at 14:51 # C++ (clang), 51 47 bytes -4 bytes thanks to Grimmy Recursion wins out as far as golfing goes. 47 bytes, with floating point and a global variable: int i;int f(double n){return n>1?f(n/++i):i=n;} Try it online! double is used instead of float because otherwise it'd start giving false positives around 11! (everything from 39916798 to 39916802 would be identified as factorial). This takes advantage of global variables being initialized (in the case of the integer i, to zero). i=n casts a double floating point value to int. Any n<1 will be rounded down to 0 (falsey). A value of 1 (truthy) will result if and only if n==1 exactly. The function cleans up after its change to the global variable upon finishing its recursion, by setting it to 0 or 1 with i=n. Which of those it is makes no difference; an value of 1 will merely result in the initial division by 1 being skipped the next time the function is invoked. 49 bytes, with floating point: int f(double n,int i=2){return n>1?f(n/i,i+1):n;} Try it online! 51 bytes, zero is true: int f(int n,int i=2){return n<2?!n:n%i|f(n/i,i+1);} This sacrifices quite a lot of speed for 1 byte of savings. Replace the | with || to make it fast, due to short-circuit evaluation of the logical OR. Try it online! (51 byte slow version) Try it online! (52 byte fast version) Ungolfed slow version: int isFactorial(int n, int i=2) // returns 0 for true, and nonzero for false { if (n < 2) // same as "if (n==0 || n==1)" in our natural number input domain { if (n==0) return 1; // not factorial else // n==1 return 0; // is factorial (could be either 0! or 1!) } // Because any nonzero value represents "false", using "|" here is equivalent // to "||", provided that the chain of recursion always eventually ends. And // it does always end, because whether or not "n" is factorial, the "n / i" // repeated division will eventually give the value of zero or one, satisfying // the above condition of termination. return (n % i) | isFactorial(n / i, i+1); }  Ungolfed fast version: int isFactorial(int n, int i=2) // returns 0 for true, and nonzero for false { if (n < 2) // same as "if (n==0 || n==1)" in our natural number input domain { if (n==0) return 1; // not factorial else // n==1 return 0; // is factorial (could be either 0! or 1!) } if (n % i != 0) return 1; // not factorial else return isFactorial(n / i, i+1); }  There are many ways to rearrange this. 52 bytes, nonzero is true: int f(int n,int i=2){return n<2?n:n%i?0:f(n/i,i+1);} Try it online! 52 bytes, zero is true: int f(int n,int i=2){return!n?1:n%i?n-1:f(n/i,i+1);} Try it online! Before resorting to recursion, I tried making some iterative versions, and they came close. 54 bytes, nonzero is true: int f(int n){for(int i=2;n>1;)n=n%i?0:n/i++;return n;} Try it online! 54 bytes, zero is true (based on Roman Gräf's Java 8 submission): int f(int n){int a=1,i=0;for(;a<n;a*=++i);return a-n;} Try it online! But as Grimmy pointed out, with floating point it can be shorter, even when done iteratively... 50 bytes, nonzero is true, floating point: int f(double n){for(int i=2;n>1;)n/=i++;return n;} Try it online! Now, for the bottom of the barrel, recursive versions with no n==0 handling (I consider these invalid, because 0 is a natural number, and any definition in which it is not makes for "natural numbers" of very limited use). In the below versions, the infinite recursion of f(0) either triggers a segfault due to overflowing the stack, or with compilers that optimize it to iteration, loops endlessly: 48 bytes, zero is true: int f(int n,int i=2){return n%i?n-1:f(n/i,i+1);} Try it online! 48 bytes, zero is true (based on Hagen von Eitzen's 33 byte C (gcc) submission): int f(int n,int e=0){return n%++e?n-1:f(n/e,e);} Try it online! • 50 EDIT: 49, without recursion. May 3, 2019 at 16:31 • Back to recursion for 48. And you probably won’t like this, but 44 by using a global var. May 3, 2019 at 17:25 # Perl 5, 31 bytes $a=<>;$a/=++$i while$a>1;exit$a


Input is taken via STDIN, output is given via exit code (1 for factorial, 0 for non-factorial).

The input is divided by successive integers until it's either 1 or some fraction less than one, which is truncated into the result.

• -5 bytes TIO Jan 22, 2019 at 11:14

# Perl 6, 29 bytes

{($_,{$_/++$}...2>*).tail==1}  Test it ## Expanded: { # bare block lambda with implicit parameter ｢$_｣

(              # generate a sequence

$_, # starting with the input {$_ / ++$# divide previous element by an ever increasing number # 1,2,3,4,5,6,7,8 ... * } ... # keep generating until 2 > * # 2 is greater than what was generated # ( 1 or a fractional number ) ).tail == 1 # check if it ended at 1 }  • 17 bytes: {$_∈[\*] 1..$_}. Another interesting approach is 2>*.polymod(1..*).sum. Nov 11, 2018 at 12:36 # setlX, 32 bytes f:=n|=>exists(x in{0..n}|n==x!);  Creates a function called f where your use your potential factorial as parameter. It works with arbitrary integer size but it's fairly inefficient. (by the way: this is my first participation at a programming puzzle) # C (gcc), 33 bytes e;f(n){n=n%++e?n==!(e=0):f(n/e);}  Note that some authors define "natural number" as positive integer. Hence I don't care that f(0) causes an infinite recursion. • Try it online! Jan 27, 2019 at 17:57 • Can be dropped to 32 bytes: Try it online! or 31 bytes by returning nonzero for false: Try it online! Jan 27, 2019 at 18:44 ## ><>, 24 22 bytes -2 bytes thanks to @Aaron I'm trying a new language (since my Mathematica licence expired…) 01\{=n; ?!\$1+:@*:{:}(


Try it online, or at the fish playground

Assumes the input number is already on the stack, and returns 0 or 1. It works by multiplying together the first n numbers until that stops being less than the input, and then printing 1 if it equals the input, and 0 if it doesn't.

• You could transform you v>\n<^ into \\n/ ; see here May 22, 2017 at 15:53
• @Aaron, that's brilliant, thank you! May 23, 2017 at 1:11

# R, 28 22 bytes

scan()%in%gamma(1:171)


Try it online!

• Make it a 22 bytes full program? May 21, 2018 at 1:46
• I'm worried I'll start using this stuff in production code.
– ngm
May 22, 2018 at 17:03

# C# (.NET Core), 68 bytes

bool f(System.Numerics.BigInteger n,int k=2)=>n<2||n%k<1&f(n/k,k+1);


Try it online!

Not the shortest solution, but works with really big numbers. The TIO link includes an example with 10000!.

Here is a shorter version that uses int which has a maximum value of 2147483647.

# C# (.NET Core), 45 bytes

bool f(int n,int k=2)=>n<2||n%k<1&f(n/k,k+1);


Try it online!

Credit to @KevinCruijssen for golfing 3 bytes in total from both answers!

• The && can be golfed to &, and the trailing ; doesn't have to be counted for lambda functions. Also, can't the ulong k=2 be uint k=2 in your 50-byte answer? Jan 22, 2019 at 12:40
• Good catch on the & vs &&. I thought I was getting a stack overflow, but it seems to work afterall. ulong is 64 bits while uint is 32. It looks like others are using int so maybe I'll just use that for the short version. With regards to the trailing ;, these are full functions, not lambdas, so I think I need include them?
– dana
Jan 22, 2019 at 12:56
• That's really strange how .NET can resolve / and % between ulong and uint, but not ulong and int. Didn't know that :)
– dana
Jan 22, 2019 at 13:13
• @Oliver - With double you start to see rounding at some point - for example, 24! and 120! fail. While System.Numerics.BigInteger has the most precision, int is the shortest answer :)
– dana
Jan 22, 2019 at 19:28
• @Deadcode - You are right about 0 :) Based on the examples in the challenge, I interpreted "natural numbers" to mean 1,2,... I agree that in the real world, it is better to use the short circuiting && operator. But this is code golf ;) Glad you like the 10000! example!
– dana
Jan 31, 2019 at 14:21

# APL (Dyalog Unicode), 5 67 bytes

Golfed a byte by changing ×/ to ! thanks to Erik the Outgolfer

⊢∊!∘⍳


Try it online!

### Explanation

    ⍳                      Range of numbers from 1 to argument, 1 2 3 4 .. n
!                       Factorial; 1! 2! 3! 4! .. n!
⊢∊                         Is the right argument a member of this list?

• Cumulative sum? May 20, 2017 at 12:32
• @LeakyNun Fixed May 20, 2017 at 12:32
• One extra byte in GNU APL 1.2 N∊×\⍳N←⎕ How does this take an argument? I don't see n anywhere. Is this a Dyalog-specific thing? May 21, 2017 at 2:15
• @Arc676 My solution is a train and you call it like so: (⊢∊(×/⍳)) right_argument as you can see in the TIO link. And the ⊢ refers to the right argument. May 21, 2017 at 7:57
• Notes: AGL will save you a byte; ⊢∊×\ä⍳. The "correct" (but longer) solution would be 0=1|!⍣¯1; "Is the inverse factorial an integer?"
May 22, 2017 at 6:02

## Mathematica, 20 bytes

!FreeQ[Range[#]!,#]&


other version to test big numbers (see comments)

Range[10^3]!~MemberQ~#&


tests up to 1000!

• As I understand the question, if Mathematica is capable of taking 1001! as an input then this doesn't meet the spec. May 20, 2017 at 10:26
• You could even save three bytes while making it valid for all inputs. Just replace 10^3 with # ; you could save another byte with using Range@# May 20, 2017 at 11:06
• @Julien Klugethen searching for 1243234 would take forever... May 20, 2017 at 12:47
• I think you can save another byte by replacing Range[#] with Range@# :) May 21, 2017 at 1:45
• Looks like you can save yet another byte with infix syntax: !Range@#!~FreeQ~#&. May 21, 2017 at 2:06

# Cubix, 24 bytes

U0O@1I1>-?1u>*w;W;@Orq)p


Try it online

Cubified

    U 0
O @
1 I 1 > - ? 1 u
> * w ; W ; @ O
r q
) p


We start by pushing 1, Input, 1 onto the stack. These will be our index, our target, and our accumulator, respectively.

We then loop. At each iteration, we subtract the accumulator from the input. If the result is 0, we're done, so we push 1, Output, and exit. If it's negative, we've gone too far, so we push 0, Output, and exit. Otherwise, we see

;p)*rq;
;         Pop the difference off the stack.
p)       Move the index to the top of the stack and increment it.
*      Multiply the accumulator by the index to get the next factorial.
rq;   Put the stack back in the right order.


# Neim, 8 bytes

𝐈Γ𝐈𝐩₁𝔼)𝐠


Explanation:

Example input: 6
𝐈         Inclusive range [1 .. input]
[1, 2, 3, 4, 5, 6]
Γ        For each...
𝐈         Inclusive range [1 .. element]
[[, [1, 2], [1, 2, 3], [1, 2, 3, 4], [1, 2, 3, 4, 5], [1, 2, 3, 4, 5, 6]]
𝐩        Product
[1, 2, 6, 24, 120, 720]
𝔼      Check for equality with
₁       the first line of input
[[0, 0, 1, 0, 0, 0]]
)   End for each
𝐠  Select largest element



Try it!

# Neim, 3 bytes (non-competing)

Non-competing as the contains token and factorial token were added after the challenge was made.

𝐈𝐓𝕚


Explanation:

Example input: 6
𝐈     Inclusive range [1 .. input]
[[1, 2, 3, 4, 5, 6]
𝐓    Factorial each
[[1, 2, 6, 24, 120, 720]]
𝕚   Check that the [cycled] input is in the list



Try it!

# Julia 1.0, 26 bytes

x->x in Base._fact_table64


Factorial is implemented as a lookup table in Julia, so lets just see if our value is in the table. Accurate for Int64, would be wrong for factorials that require a larger Integer type to represent.

Try it online!

# TI-BASIC, 13 bytes

sum(Ans=seq(X!,X,1,69


Input is an integer in Ans.
Output is 1 if the input is a factorial, 0 if not.

Due to precision in = checks being limited to 10 decimal places, this program will produce erroneous answers for numbers whose length is $$\>10\$$ digits.

Explanation:

        seq(X!,X,1,69  ;generate a list of all factorial numbers that
;  TI-BASIC can store
Ans=               ;equality check of the input against all members,
;  1 if true, 0 if false
sum(                   ;sum the elements in the list
;leave the result in Ans
;implicit print of Ans


Examples:

720:prgmCDGF27
1
25:prgmCDGF27
0


Note: TI-BASIC is a tokenized language. Character count does not equal byte count.

# cQuents, 3 bytes

?$!  Try it online! As I said in another question, cQuents is made for this. ? # Query (Outputs if in the sequence)$! # Factorial
`