45
\$\begingroup\$

The Task

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!

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

88 Answers 88

40
\$\begingroup\$

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.

\$\endgroup\$
10
  • 9
    \$\begingroup\$ @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) \$\endgroup\$ – Fatalize May 20 '17 at 9:46
  • 8
    \$\begingroup\$ It's a trivial solution, but it's clever because of the way prolog works. \$\endgroup\$ – Esolanging Fruit May 21 '17 at 6:18
  • 5
    \$\begingroup\$ @Nayuki This one, which is custom \$\endgroup\$ – Fatalize May 22 '17 at 21:11
  • 18
    \$\begingroup\$ 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 \$\endgroup\$ – Alexander May 23 '17 at 5:57
  • 21
    \$\begingroup\$ @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. \$\endgroup\$ – Fatalize May 23 '17 at 6:15
27
\$\begingroup\$

ECMAScript Regex, 733 690 158 119 118 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:

regex for matching factorial numbers - multiplicity-comparing method, with molecular lookahead.txt
regex for matching factorial numbers.txt (the one shown above)

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
\$\endgroup\$
20
\$\begingroup\$

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.
\$\endgroup\$
4
  • 2
    \$\begingroup\$ Because us code golfers care about efficiency. \$\endgroup\$ – Okx May 20 '17 at 15:10
  • 12
    \$\begingroup\$ 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. ¯\_(ツ)_/¯ \$\endgroup\$ – Dennis May 20 '17 at 15:16
  • \$\begingroup\$ 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? \$\endgroup\$ – Deadcode Jan 31 '19 at 17:43
  • \$\begingroup\$ @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... \$\endgroup\$ – Dennis Jan 31 '19 at 19:07
19
\$\begingroup\$

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
\$\endgroup\$
0
15
\$\begingroup\$

JavaScript (ES6), 30 29 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.

\$\endgroup\$
3
  • \$\begingroup\$ Nice - really like the use of ~ at the end. \$\endgroup\$ – Steve Bennett May 21 '17 at 22:46
  • \$\begingroup\$ 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.) \$\endgroup\$ – CalculatorFeline May 25 '17 at 1:15
  • \$\begingroup\$ @Arnauld Undownvoted. \$\endgroup\$ – CalculatorFeline May 26 '17 at 21:02
11
\$\begingroup\$

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

\$\endgroup\$
1
  • \$\begingroup\$ @ovs we have been restricted to a two consistent outputs. That, unfortunately, returns 1 for all factorials except 1 for which it returns True. \$\endgroup\$ – Jonathan Allan May 20 '17 at 10:29
11
\$\begingroup\$

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)));
    }
}
\$\endgroup\$
10
+100
\$\begingroup\$

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.

\$\endgroup\$
6
  • \$\begingroup\$ Save a byte by removing the 1 as it is implied when $* is at the end of the replacement. \$\endgroup\$ – Neil May 20 '17 at 10:38
  • \$\begingroup\$ Better still, combine the $* with the other two lines. \$\endgroup\$ – Neil May 20 '17 at 10:41
  • \$\begingroup\$ Try it online! \$\endgroup\$ – Neil May 20 '17 at 10:43
  • 3
    \$\begingroup\$ I'm impressed that you found a way to crash Retina conditionally. :) \$\endgroup\$ – Martin Ender May 20 '17 at 16:36
  • 2
    \$\begingroup\$ Can you add an explanation? \$\endgroup\$ – CalculatorFeline May 22 '17 at 23:13
8
\$\begingroup\$

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
\$\endgroup\$
4
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Neil A. May 21 '17 at 8:33
  • \$\begingroup\$ @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. \$\endgroup\$ – Emigna May 21 '17 at 8:37
  • \$\begingroup\$ I didn't know about input being popped again...that sure could save a lot of bytes. \$\endgroup\$ – Neil A. May 21 '17 at 8:42
  • \$\begingroup\$ @NeilA. It is a fairly new feature. It was added less than a month ago I think. \$\endgroup\$ – Emigna May 21 '17 at 8:53
8
\$\begingroup\$

C++, 102 100 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)

\$\endgroup\$
2
  • \$\begingroup\$ Hi! Welcome to PPCG! Nice first answer! Good luck for the future! \$\endgroup\$ – Arjun May 20 '17 at 17:09
  • \$\begingroup\$ 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 :) \$\endgroup\$ – Christoph May 22 '17 at 9:04
7
\$\begingroup\$

Haskell, 43 26 bytes

f n=elem n$scanl1(*)[1..n]

Try it online!

  • Saved 17 bytes, thanks to Laikoni
\$\endgroup\$
6
  • 2
    \$\begingroup\$ f n=elem n$scanl1(*)[1..n] is ridiculous inefficient but shorter. \$\endgroup\$ – Laikoni May 20 '17 at 11:17
  • \$\begingroup\$ Isn't there some rule about code efficiency? \$\endgroup\$ – sudee May 20 '17 at 12:15
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – Laikoni May 20 '17 at 12:44
  • \$\begingroup\$ 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! \$\endgroup\$ – sudee May 20 '17 at 16:24
  • 1
    \$\begingroup\$ 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%). \$\endgroup\$ – Jon Purdy May 23 '17 at 2:48
6
\$\begingroup\$

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.

\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
5
\$\begingroup\$

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
\$\endgroup\$
3
  • 1
    \$\begingroup\$ I really should add a "contains" built-in :P \$\endgroup\$ – ETHproductions May 20 '17 at 11:14
  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – ETHproductions May 20 '17 at 11:16
  • \$\begingroup\$ Fails for 2 becuase o will only give you [0,1]. Here's a fix with a 1 byte saving. \$\endgroup\$ – Shaggy Sep 26 '17 at 14:51
5
\$\begingroup\$

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!

\$\endgroup\$
2
  • 1
    \$\begingroup\$ 50 EDIT: 49, without recursion. \$\endgroup\$ – Grimmy May 3 '19 at 16:31
  • 1
    \$\begingroup\$ Back to recursion for 48. And you probably won’t like this, but 44 by using a global var. \$\endgroup\$ – Grimmy May 3 '19 at 17:25
4
\$\begingroup\$

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.

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

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
}
\$\endgroup\$
1
  • \$\begingroup\$ 17 bytes: {$_∈[\*] 1..$_}. Another interesting approach is 2>*.polymod(1..*).sum. \$\endgroup\$ – nwellnhof Nov 11 '18 at 12:36
4
\$\begingroup\$

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)

\$\endgroup\$
4
\$\begingroup\$

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.

\$\endgroup\$
2
4
\$\begingroup\$

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

\$\endgroup\$
2
  • \$\begingroup\$ You could transform you v>\n<^ into \\n/ ; see here \$\endgroup\$ – Aaron May 22 '17 at 15:53
  • \$\begingroup\$ @Aaron, that's brilliant, thank you! \$\endgroup\$ – Not a tree May 23 '17 at 1:11
4
\$\begingroup\$

R, 28 22 bytes

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

Try it online!

\$\endgroup\$
2
  • \$\begingroup\$ Make it a 22 bytes full program? \$\endgroup\$ – JayCe May 21 '18 at 1:46
  • 1
    \$\begingroup\$ I'm worried I'll start using this stuff in production code. \$\endgroup\$ – ngm May 22 '18 at 17:03
4
\$\begingroup\$

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!

\$\endgroup\$
6
  • 2
    \$\begingroup\$ 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? \$\endgroup\$ – Kevin Cruijssen Jan 22 '19 at 12:40
  • 1
    \$\begingroup\$ 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? \$\endgroup\$ – dana Jan 22 '19 at 12:56
  • \$\begingroup\$ That's really strange how .NET can resolve / and % between ulong and uint, but not ulong and int. Didn't know that :) \$\endgroup\$ – dana Jan 22 '19 at 13:13
  • 1
    \$\begingroup\$ @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 :) \$\endgroup\$ – dana Jan 22 '19 at 19:28
  • 1
    \$\begingroup\$ @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! \$\endgroup\$ – dana Jan 31 '19 at 14:21
4
\$\begingroup\$

APL (Dyalog Unicode), 5 6 7 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?
\$\endgroup\$
8
  • \$\begingroup\$ Cumulative sum? \$\endgroup\$ – Leaky Nun May 20 '17 at 12:32
  • \$\begingroup\$ @LeakyNun Fixed \$\endgroup\$ – user41805 May 20 '17 at 12:32
  • \$\begingroup\$ 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? \$\endgroup\$ – Arc676 May 21 '17 at 2:15
  • 2
    \$\begingroup\$ @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. \$\endgroup\$ – user41805 May 21 '17 at 7:57
  • \$\begingroup\$ Notes: AGL will save you a byte; ⊢∊×\ä⍳. The "correct" (but longer) solution would be 0=1|!⍣¯1; "Is the inverse factorial an integer?" \$\endgroup\$ – Adám May 22 '17 at 6:02
3
\$\begingroup\$

Mathematica, 20 bytes

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

other version to test big numbers (see comments)

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

tests up to 1000!

\$\endgroup\$
11
  • 2
    \$\begingroup\$ As I understand the question, if Mathematica is capable of taking 1001! as an input then this doesn't meet the spec. \$\endgroup\$ – Peter Taylor May 20 '17 at 10:26
  • 2
    \$\begingroup\$ 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@# \$\endgroup\$ – Julien Kluge May 20 '17 at 11:06
  • \$\begingroup\$ @Julien Klugethen searching for 1243234 would take forever... \$\endgroup\$ – ZaMoC May 20 '17 at 12:47
  • 1
    \$\begingroup\$ I think you can save another byte by replacing Range[#] with Range@# :) \$\endgroup\$ – numbermaniac May 21 '17 at 1:45
  • 3
    \$\begingroup\$ Looks like you can save yet another byte with infix syntax: !Range@#!~FreeQ~#&. \$\endgroup\$ – numbermaniac May 21 '17 at 2:06
3
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

Neim, 8 bytes

𝐈Γ𝐈𝐩₁𝔼)𝐠

Explanation:

Example input: 6
𝐈         Inclusive range [1 .. input]
          [1, 2, 3, 4, 5, 6]
 Γ        For each...
  𝐈         Inclusive range [1 .. element]
            [[[1], [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
          [1]

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
      [1]

Try it!

\$\endgroup\$
3
\$\begingroup\$

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!

\$\endgroup\$
3
\$\begingroup\$

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.

\$\endgroup\$
3
\$\begingroup\$

cQuents, 3 bytes

?$!

Try it online!

As I said in another question, cQuents is made for this.

?   # Query (Outputs if in the sequence)
 $! # Factorial
\$\endgroup\$

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.