38
\$\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\$
  • 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
  • 11
    \$\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

76 Answers 76

37
\$\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\$
  • 6
    \$\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
  • 6
    \$\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
  • 17
    \$\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
  • 13
    \$\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
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\$
19
\$\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\$
  • 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 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 at 19:07
17
\$\begingroup\$

ECMAScript Regex, 733+ 690+ 158 119 118 (117🐌) bytes

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 at the very least equal in power to molecular lookahead, but the latter tends to make for more straightforward and elegant implementations.)

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, 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 each time. (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.

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!

Edit: I was able to drop 1 byte (119 → 118) using a trick found by Grimy that can futher shorten division in the case that the quotient is guaranteed to be greater than or equal to the divisor.

With no further ado, here's the regex:

True/false version (118 bytes):

^((x*)x*)(?=\1$)(?=(xxx\2)+$)((?=\2\3*(x(?!\3)xx(x*)))\6(?=\5+$)(?=((x*)(?=\5(\8*$))x)\7*$)x\9(?=x\6\3+$))*\2\3$|^xx?$

Try it online!

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

^(?=((x*)x*)(?=\1$)(?=(xxx\2)+$)((?=\2\3*(x(?!\3)xx(x*)))\6(?=\5+$)(?=((x*)(?=\5(\8*$))x)\7*$)x\9(?=x\6\3+$))*\2\3$)\3|^xx?$

Try it online!

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

^((x*)x*)(?=\1$)(?=(xxx\2)+$)((?=\2\3*(x(?!\3)xx(x*)))\6(?=\5+$)(?=((x*)(?=\5(\8*$))x)\7*$)x\9(?=x\6\3+$))*\2\K\3$|^xx?$

And the free-spaced version with comments:

  ^
  (?=                           # Remove this lookahead and the \3 following it, while
                                # preserving its contents unchanged, to get a 119 byte
                                # regex that only returns match / no-match.
    ((x*)x*)(?=\1$)             # Assert that tail is even; \1 = tail / 2;
                                # \2 = (conjectured N for which tail == N!)-3; tail = \1
    (?=(xxx\2)+$)               # \3 = \2+3 == N; Assert that tail is divisible by \3
    # The loop is seeded: X = \1; I = 3; tail = X + I-3
    (
      (?=\2\3*(x(?!\3)xx(x*)))  # \5 = I; \6 = I-3; Assert that \5 <= \3
      \6                        # tail = X
      (?=\5+$)                  # Assert that tail is divisible by \5
      (?=
        (                       # \7 = tail / \5
          (x*)                  # \8 = \7-1
          (?=\5(\8*$))          # \9 = tool for making tail = \5\8
          x
        )
        \7*$
      )
      x\9                       # Prepare the next iteration of the loop: X = \7; I += 1;
                                # tail = X + I-3
      (?=x\6\3+$)               # Assert that \7 is divisible by \3
    )*
    \2\3$
  )
  \3                            # Return N, the inverse factorial, as a match
|
  ^xx?$                         # Match 1 and 2, which the main algorithm can't handle

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)

Note that ((x*)x*) can be changed to ((x*)+), dropping the size by 1 byte (to 117 bytes) with no loss of correct functionality – but the regex exponentially explodes in slowness. However, this trick, while it works in PCRE and .NET, does not work in ECMAScript, due to its behavior when encountering a zero-length match in a loop. ((x+)+) would work in ECMAScript, but this would break the regex, because for \$n=3!\$, \2 needs to capture a value of \$3-3=0\$ (and changing the regex to be 1-indexed would undo the golf benefit of this).

The .NET regex engine does not emulate this behavior in its ECMAScript mode, and thus the 117 byte regex works:

Try it online! (exponential-slowdown version, with .NET regex engine + ECMAScript emulation)

\$\endgroup\$
14
\$\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\$
  • \$\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\$
  • \$\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\$
9
+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\$
  • \$\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\$
  • 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\$
  • \$\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\$
  • 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\$
  • 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
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\$
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\$
  • \$\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\$
4
\$\begingroup\$

R, 28 22 bytes

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

Try it online!

\$\endgroup\$
  • \$\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\$
  • 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 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 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 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 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 at 14:21
4
\$\begingroup\$

C++ (clang), 51 bytes

Recursion wins out as far as golfing goes.

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!

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\$
  • \$\begingroup\$ 50 EDIT: 49, without recursion. \$\endgroup\$ – Grimy May 3 at 16:31
  • \$\begingroup\$ Back to recursion for 48. And you probably won’t like this, but 44 by using a global var. \$\endgroup\$ – Grimy May 3 at 17:25
3
\$\begingroup\$

Mathematica, 20 bytes

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

other version to test big numbers (see comments)

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

tests up to 1000!

\$\endgroup\$
  • 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\$ – J42161217 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\$

><>, 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\$
  • \$\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
3
\$\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\$
  • \$\begingroup\$ Cumulative sum? \$\endgroup\$ – Leaky Nun May 20 '17 at 12:32
  • \$\begingroup\$ @LeakyNun Fixed \$\endgroup\$ – Cows quack 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\$ – Cows quack 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
2
\$\begingroup\$

JavaScript (ES6), 71 bytes

This takes in input as function argument and alerts the output. Outputs 0 for falsey and 1 for truthy.

f=n=>n?n*f(n-1):1;g=(n,r=0,i=0)=>{while(i<=n){r=f(i)==n|r;i++}alert(r)}

Explanation

The program consists of two functions, f and g. f is a recursive factorial-computing function, and g is the main function of the program. g assumes to have a single argument n. It defines a default argument r with a value of 0 and another default argument with a value of 0. It, then, iterates over all the Integers from 0 to n, and, in each iteration, checks whether the function f applied over i (the current index) equals n, i.e. whether n is a factorial of i. If that happens to be the case, r's value is set to 1. At the end of the function, r is alerted.

Test Snippet

(Note: The snippet outputs using console.log() as nobody like too many of those pesky alert()s.)

f=n=>n?n*f(n-1):1;g=(n,r=0,i=0)=>{while(i<=n){r=f(i)==n|r;i++}console.log(r)}

g(1)
g(2)
g(3)
g(4)
g(5)
g(6)
g(7)
g(8)
g(24)
g(120)

\$\endgroup\$
  • \$\begingroup\$ Eval might be shorter than using a code block. \$\endgroup\$ – Downgoat May 20 '17 at 15:29
  • \$\begingroup\$ @Downgoat How should I do that? Sorry if it's too obvious! :P \$\endgroup\$ – Arjun May 21 '17 at 7:54
2
\$\begingroup\$

QBIC, 21 19 bytes

[:|q=q*a~q=b|_x1}?0

Explanation

[:|     Start a FOR loop from 1 to n
q=q*a   q starts as 1 and is multiplied by the FOR loop counter
        consecutively: q=1*1, *2, *3, *4 ... *n
~q=b|   If that product equals n
_x1     Then quit, printing a 1
}       Close the IF and the FOR
?0      If we're here, we didn't quit early and didn't find a factorial, print 0

Previously

[:|q=q*a┘c=c+(q=b)}?c

Explanation:

[:|         Start a FOR loop from 1 to n
q=q*a       q starts as 1 and is multiplied by the FOR loop counter
            consecutively: q=1*1, *2, *3, *4 ... *n
┘           Syntactic line break
c=c+        c starts out at 0 and then keeps track of 
    (q=b)       how often our running total == n
}           Closes the FOR-loop
?c          Print c, which is 0 fir non-factorials and -1 otherwise.
\$\endgroup\$
2
\$\begingroup\$

Java 8, 59 bytes

i->{for(int j=1,c=0;j<=i;j*=++c)if(j==i)return 1;return 0;}

Testcode

import java.util.function.IntFunction;
import java.util.stream.IntStream;

public class IsFactorial
{
    public static IntFunction<Integer> isFactorial = i->
    {
        for(int j=1,c=0;j<=i;j*=++c)
            if(j==i)return 1;return 0;
    };

    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)==1)
            && IntStream.of(falsyCases)
                .allMatch(i->isFactorial.apply(i)==0)
        );
    }
}
\$\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.