# Reverse factorial function

Given a number n, find x such that x! = n, where both x and n are positive integers. Assume the input n will always be the factorial of a positive integer, so something like n=23 will not be given as input.

Examples: n=1 -> x=1 (0 is not a positive integer), n=24 -> x=4

Shortest code wins.

• Btw, we once had a similar challenge but 1) it's pretty old 2) it's over real numbers, not just positive integers 3) it bans factorial-related built-ins, which isn't quite good for our current standards. So I think the challenge itself is fine and not a dupe. May 20, 2020 at 23:54
• Is there an upper bound on the possible inputs?
– xnor
May 21, 2020 at 8:14
• What are the bounds on the input? Can we assume that it is no more than 19! (largest factorial that can be fully represented in a 53+11 double precision floating point), no more than 23! (largest factorial that can be accurately represented in a double precision 53+11 floating point), or no more than 170! (largest factorial whose magnitude is less than the maximum of a double precision floating point ~= 10^308)
– JDL
May 21, 2020 at 10:29
• @JDL I'm not the challenge author, but I'd say "up to the highest number that your language's number type supports (without loss of precision), but the underlying algorithm should work for higher numbers". Related standard loophole. May 22, 2020 at 4:33
• @Bubbler: the question does not limit the input number in any way except that x and n are positive integers. As such 646077305624121491462330357080396430806673805704796612248389053020040737981389397373513335318926846519441974218777961448245634895440330929720840926954349439434654453860427703550673839109903970520283495061590634864022312082259902655711571689179112428197039756156051147969300077437438615382409042832551650139224687809841080780412598454920634889005911333104355143592477664451230317936640000000000000000000000000000000000000000000000000000000 is a perfectly valid value for n :-) May 23, 2020 at 18:01

# Python 2, 28 bytes (input $$\\leq2^{64}\$$)

lambda n:len(n**8L)**.6//1

Try it online!

This works on inputs up to $$\20! =2432902008176640000 \$$ that fall within 64-bit integers.

This uses an approximate fit inspired by Stirling's approximation. However, the constants were estimated manually and it breaks down for larger values. With Python not having a built-in log, we use the digit-length for $$\n^8\$$ as an approximation for $$\c\cdot\log(n)\$$. Actually, we use the long value 8L so that the string representations uniformly end in L for "long", which adds one to the lengths.

From there, raising the value to the power of $$\0.6\$$ and taking the integer part is apparently sufficient to give the correct output up to $$\20!\$$. It's lucky that the 0.6 is 0.60, since we'd usually need another digit of precision.

• I think you should not have posted this before OP replied as we seem to have a consensus that the algorithm must work for all possible inputs in theory. May 21, 2020 at 9:05
• @mypronounismonicareinstate It's complicated. There's always been a thorny question in Python 2 whether number inputs fall within the integer type (up to 2^64) rather than the (unbounded) long type. Python accepts inputs larger than this and interprets them as longs, where some other languages just fail. Pretty much all golfs that use backticks for string representation (which have a trailing L on longs) fail on large inputs. So, a quite a number of Python 2 answers on the site have been making this assumption. Of course, here I use it for a different reason, of a limited approximation.
– xnor
May 21, 2020 at 9:28

# APL (Dyalog Extended), 2 bytes

¯!

Try it online!

Exactly the same as non-extended APL answer but just with the shorter syntax.

! is factorial function, ¯ prefix gives the inverse function of it.

• It reads: inverse factorial
– user92069
May 21, 2020 at 8:40
• @Λ̸̸ This is a macron (high minus), not a backtick, anyway, TryAPL (which runs a normal Dyalog APL) doesn't support this extension.
– Adám
May 21, 2020 at 10:58

# Python 2, 32 bytes

f=lambda n,k=2:n and-~f(n/k,k+1)

Try it online!

# Jelly, 3 bytes

!€i

Try it online!

i    The first index (from 1) of the input in
!€     the factorials of every integer from 1 to the input.
• My first attempt was Æ!L’, which is just plain silly. May 21, 2020 at 8:32

# Brachylog, 3 bytes

ℕ₁ḟ

Try it online!

A predicate which takes input reversed (i.e., the input is given through the output variable, and the output is given through the input variable). Brachylog more-or-less has a builtin for exactly this, aside from needing to apply the additional constraint of having to output a positive integer, where I say more or less because it's also just the factorial builtin and it works in both directions.

# J, 4 bytes

!inv

Try it online!

Inverse of factorial.

# C (gcc), 33 29 28 bytes

Saved a byte thanks to ceilingcat!!!

x;f(n){for(x=0;++x-n;n/=x);}

Try it online!

# Ruby, 27 bytes

->n,x=0{2>n/=x+=1or redo;x}

Try it online!

Increment the divisor x (initially 0), divide n (initially the input value) by x and store the result as n, repeat until n=1. Then x is the desired output.

# Wolfram Language (Mathematica), 20 bytes

Mathematica has the inverse function of the factorial! It's called InverseFunction@Factorial. I used a pure (Mathematica for "anonymous") function that returns the factorial by using the exclamation mark, as it's shorter.

InverseFunction[#!&]

Try it online!

• the output is a Little messed up, but 13 bytes with Solve: tio.run/…
– ovs
May 21, 2020 at 11:46
• @ovs you can use quiet Try it online! May 21, 2020 at 14:25
• Huh, I didn't know Solve doesn't need a variable. I don't think Quiet is needed, because we normally ignore warnings (and Mathematica errors seem to be only warnings for some reason) May 21, 2020 at 14:32
• @mypronounismonicareinstate it is only for presentation purposes... May 21, 2020 at 14:51
• The iterative (For[x=0,x!<#,++x];x)& is only 22 bytes; I wonder if there's a way to golf it below 20. May 23, 2020 at 8:41

Å!g<

Try it online!

# Retina 0.8.2, 39 bytes

.+
1 $&$*
+^(1+) (1\1)+$1$1 $#2$*
\G1

Try it online! Link includes test cases. Actually calculates the largest factorial that divides n. Explanation:

.+
1 $&$*

Set x to 1 and convert n to unary.

^(1+) (1\1)+$1$1 $#2$*

If x+1 divides n, then increment x and divide n by the incremented x.

+

Repeat the above until x+1 does not divide n (hopefully because n=1 at this point).

\G1

Convert x to decimal.

# R, 29 28 bytes (input ≤170!)

match(scan(),cumprod(1:170))

Try it online!

Input is limited to 170!, which is the largest factorial that can be handled as a floating-point number by R; in any case, at larger values, there is a risk that truncated digits in the internal floating-point encoding will affect the output. Obviously the second issue will be fixed when run on an imaginary 'unlimited-precision' R implementation, but the input limitation will always be there (or, with slight modification, a limitation to ≤999!). So...

# R, 38 34 bytes

n=scan();while(n>(T=T*(F=F+1)))n;F

Try it online!

Edit: -4 bytes thanks to tip from Giuseppe

This version is still subject to the precision limitations of the R implementation, but could (in principle) be run with unlimited input.

Edit: Obviously the large increase in program length to achieve the unimplemented ability to run on unlimited input is rather unsatisfying, so...

# R, 30 29 bytes

match(n<-scan(),cumprod(1:n))

Try it online!

Only one-byte longer than the input-limited attempt. Unfortunately, on all current R implementations, it is rather slow and is likely to crash with anything but small input values, but - in the words of Osgood Fielding III - 'well, nobody's perfect'

• 65 bytes using the gmp package's arbitrary precision integers -- match does something weird with bigz, I'm afraid. May 21, 2020 at 14:52
• First of all: thanks for the T as a variable idea! I will immediately incorporate this, and the obvious follow-up... May 21, 2020 at 17:53
• And secondly: I think you should post the arbitrary-precision gmp solution: I didn't know about this at all until you showed it to me. I think it can be reduced a little, too: tio.run/##dYtLbsJQEAT33MI7O0joTc/nTWOZpU/… May 21, 2020 at 17:56
• You use [link name](link). I think the little "help" at the bottom right of the comment box, below "Save Edits" (on desktop) will expand out some comment formatting tips. May 21, 2020 at 18:19
• @JDL - After running a quick test, it seems that (probably by luck, not skill) the first one actually outputs the correct values all the way up to 170!. May 22, 2020 at 8:30

# dc, 22 bytes

0?[r1+d_3R/d1<F]dsFx/p

Try it online!

Input on stdin, and output on stdout.

Works for arbitrarily large inputs (up to the available memory). The TIO sample run is for 200!.

How it works

The description below presumes that the input is a factorial (so all the divisions have no remainder).

0
?     # Stack is now (top of stack on right):
#    x n
#    where x = 0 and n is the input number.
[     # Define a macro (to be used as a loop).
#    If we write the stack as
#    x n
#    then we assert the following loop invariant at this point in the cycle:
#       n = input / x!
r      # Swap.        Stack: n x
1+     # Increment.          n x+1
d      # Duplicate.          n x+1 x+1
_3R    # Rotate 3 steps clockwise.
#                     x+1 n x+1
/      # Divide.             x+1 n/(x+1)
d1<F   # If n/(x+1) > 1, go back to the beginning of the loop.
#    Note that the loop invariant is once again true,
#    as it should be at the beginning of a new loop iteration.
]dsFx # End macro, call it F, and execute it.
# When we leave the loop, we know the following, where 'x n' is the current stack:
#   (1) the loop termination condition was false, so n <= 1,
#       and we must actually have
#       n = 1
#       because the input was a factorial;
#   and
#   (2) the loop invariant is true, so n = input / x!
#
#   It follows that x! = the input, and the stack is now:
#                              x 1
/     # Divide (to pop the 1).       x
p     # Print top of stack.

# Pyth, 4 bytes

.I*F

Try it online!

### Explanation

.I*F
.I    : Inverse function of
*F  : factorial

# Pyth, 6 5 bytes

fqQ*F

Try it online!

-1 byte thanks to @FryAmTheEggman

### Explanation

fqQ*F
f      : First positive integer value where
Q    : input
q     : is equal to
*F  : factorial of value
• Rearranging can save you a byte: fqQ*F. May 21, 2020 at 15:29

# Clojure, 73 bytes

(defn f[n](loop[x 1](if(= n(reduce *'(range 2(inc x))))x(recur(+ x 1)))))

Ungolfed:

(defn find-fact [n]  ; n = x!. Find x
(loop [x 1]
(if (= n (reduce *' (range 2 (inc x))))
x
(recur (+ x 1)))))

Tested out to 1234!, which is the 3281 digit number 51084981466469576881306176261004598750272741624636207875758364885679783886389114119904367398214909451616865959797190085595957216060201081790863562740711392408402606162284424347926444168293770306459877429620549980121621880068812119922825565603750036793657428476498577316887890689284884464423522469162924654419945496940052746066950867784084753581540148194316888303839694860870357008235525028115281402379270279446743097868896180567901452872031734195056432576568754346528258569883526859826727735838654082246721751819658052692396270611348013013786739320229706009940781025586038809493013992111030432473321532228589636150722621360366978607484692870955691740723349227220367512994355146567475980006373400215826077949494335370591623671142026957923937669224771617167959359650439966392673073180139376563073706562200771241291710828132078928672693377605280698340976512622686207175259108984253979970269330591951400265868944014001740606398220709859461709972092316953639707607509036387468655214963966625322700932867195641466506305265122238332824677892386098873045477946570475614470735681011537762930068333229753461311175690053190276217215938122229254011663319535668562288276814566536254139944327446923749675156838399258655227114181067181300031191298489076680172983118121156086627360397334232174932132686080901569496392129263706595509472541921027039947595787992209537069031379517112985804276412719491334730247762876260753560199012424360211862466047511184797159731714330368251192307852167757615200611669009575630075581632200897019110165738489288234845801413542090086926381756642228872729319587724120647133695447658709466047131787467521648967375146176025775545958018149895570817463048968329692812003996105944812538484291689075721849889797647554854834050132592317503861422078077932841396250772305892378304960421024845815047928229669342818218960243579473180986996883486164613586224677782405363675732940386436560159992961462550218529921214223556288943276860000631422449845365510986932611414112386178573447134236164502410346254516421812825350152383907925299199371093902393126317590337340371199288380603694517035662665827287352023563128756402516081749705325705196477769315311164029733067419282135214232605607889159739038923579732630816548135472123812968829466513428484683760888731900685205308016495533252055718190142644320009683032677163609744614629730631454898167462966265387871725580083514565623719270635683662268663333999029883429331462872848995229714115709023973771126468913873648061531223428749576267079084534656923514931496743842559669386638509884709307166187205161445819828263679270112614012378542273837296427044021252077863706963514486218183806491868791174785424506337810550453063897866281127060200866754011181906809870372032953354528699094096145120997842075109057859226120844176454175393781254004382091350994101959406590175402086698874583611581937347003423449521223245166665792257252160462357733000925232292157683100179557359793926298007588370474068230320921987459976042606283566005158202572800000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

# [MATLAB/Octave], 35 34 26 bytes

f=@(n)nnz(cumprod(1:n)<=n)

Thanks @David for the feedback! I added the f= to have way to call the function for 2 bytes.

• I tried values up to 10^7. It took about 40 seconds but it does work! May 21, 2020 at 17:27
• This doesn't work in Matlab. I think it returns n not x, it calculates factorial(1:24) then finds the last entry less than or equal to n, instead you want the last index where A<=n. It's also not Matlab code. Instead, in Matlab, you could do nnz(factorial(1:n)<=n) (or sum instead of nnz). You can replace factorial(1:n) by cumprod(1:n) to save 2 chars, so nnz(cumprod(1:n)<=n) works for 20 bytes, but convention here is that answers should be programs, you can't use the stored value n. So this should work: @(n)nnz(cumprod(1:n)<=n) in Matlab at least for 24 bytes. May 22, 2020 at 2:13
• Thanks for the comment, I guess I missed that. I'm using Octave so the result may vary slightly. May 23, 2020 at 18:51
• I believe you don't actually need the two bytes for the f= as the result get automatically assigned to the value ans. Hence 24 Aug 2, 2020 at 12:07

SWI-Prolog, 50 bytes

:-[library(clpfd)].
c(F,N):-F#=1,N#=1;c(F//N,N-1).

Try it online!

c(F,N) recursively defines factorials, either F = N = 1, or F/N is (N-1)!. To save bytes we used integer division, so the answer is only valid if F is actually a factorial. Prolog infers the correct value for N if not specified.

Algorithm should work for all inputs, although it isn't particularly fast. Tested up to 128!.

• Welcome to the site! I love seeing prolog. We have a tips page for prolog here which you can read or contribute on. May 27, 2020 at 16:45

# Rust, 41 32 bytes

|mut y|(1..).find(|x|{y/=x;y<2})

Try it online!

The .unwrap() was unnecessary (Meta post), saving 9 bytes

# Husk, 4 bytes

€mΠN

Try it online!

€     the index of implicit input in ...
mΠ   ... map factorial over ...
N  ... the natural numbers

# Erlang (escript), 45 bytes

Quite similar with ovs's Python answer.

f(1.0,Y)->Y;f(X,Y)->f(X/Y,Y+1).
f(X)->f(X,2).

Try it online!

# COW, 108 bytes

oomMOoMOOMoOMMMOOOmoOMMMmoOMoOmOoMOOmoOMMMmoOMMMMOOMOomOomOoMOomoOmoOmoomOomOomOoMoOmoOmoomOoMOomoomoOmoOOOM

Try it online!

## Explanation

moo ]    mOo <    MOo -    OOO *    OOM o
MOO [    moO >    MoO +    MMM =    oom ^

[0]: n/(i!)     [1]: n/((i-1)!)     [2]: i     [3]: i_temp

^-                   ;  Read i in [0] and decrement it
[                    ;  Loop while [0] is non zero ( n/(i!)-1 is checked )
+=*>=            ;      [0] is incremented and cut/copied in [1]
>+<              ;      [2] is incremented
[                ;      Loop while [1] is non zero ( repeated subtraction begins )
>=>=         ;          Copy [2] in [3]
[            ;          Loop while [3] is non zero
-<<->>   ;              [3] and [1] are decremented ( [1] is guaranteed to be divisible by [3] )
]            ;
<<<+>        ;          [0] is incremented
]                ;      [0] is now the product of the biggest x-i factor of n
<-               ;  [0] is decremented so iff [0] = 1 the loop ends
]                    ;
>>o                  ;  Print [2] x

# Excel, 29 bytes

=MATCH(A1,FACT(ROW(1:170)),0)

# Factor + math.factorials, 41 32 bytes

Saved 9 bytes thanks to @Bubbler!

[ dup [1,b] [ n! = ] with find ]

Try it online!

# Factor, 50 34 bytes

Saved 16 bytes thanks to @Bubbler!

[ 1 over [1,b] [ * 2dup = ] find ]

Try it online!

There's probably a better idiom for this, but I can't find it right now.

• If you decide to use math.factorials, n! is a golfier synonym of factorial. Also, using with seems to be slightly shorter here. Mar 23, 2021 at 23:39
• Also, the quotation used in sequence functions can access the items under it, so something like this is possible. Mar 23, 2021 at 23:40
• @Bubbler Thanks, I should have noticed n!. with looks like a pretty interesting function.
– user
Mar 23, 2021 at 23:55

# APL (Dyalog Unicode), 4 bytes

I was just copying Bubbler's solution. I didn't write it, so it's community wiki.

!⍣¯1

Try it online!

## Explanation

⍣¯1 The inverse of this function:
!    Factorial function

# Charcoal, 17 bytes

Ｎθ⊞υ¹Ｗ‹Πυθ⊞υＬυＩ⌈υ

Try it online! Link is to verbose version of code. Actually calculates the lowest factorial not less than n. Explanation:

Ｎθ

Input n.

⊞υ¹

Push 1 to the predefined empty list.

Ｗ‹Πυθ

Repeat while the product of the list is less than n.

⊞υＬυ

Push the length of the list to the list. (This means that the list has an extra 1 in it, but conveniently that doesn't affect the product.)

Ｉ⌈υ

Output the largest element of the list (which is also the last element; either operation works.)

# SimpleTemplate, 72 bytes

Not exactly the smallest, but works.

Uses a naive approach to calculate the factorial up to the chosen number, returning the value if found.

{@setf 1}{@forfrom 1toargv.0}{@set*f f,_}{@iff is equalargv.0}{@return_}

Notice that this is a REAL {@return}! The compiler method will give you this value.
To be used as a function, simply wrap it in {@fn invert_factorial} [...] {@/}.

Ungolfed version

This should be easy to understand

{@set factorial 1}
{@for i from 1 to argv.0}
{@set* factorial factorial, i}
{@if factorial is equal to argv.0}
{@return i}
{@/}
{@/}

The line {@set* factorial factorial, i} simply stores ,in factorial, the result of multiplying the value factorial to i.

You can test this on:
http://sandbox.onlinephpfunctions.com/code/61cc7101a868a71d0a7a85cdde57f946bcb2586e

# Rust, 57 bytes

fn f(mut y:i32)->i32{let mut x=1; while y>1{x+=1;y/=x;}x}

Try it online!

# Burlesque, 17 bytes

b01{+.}{?!.>}w!it

Try it online!

Explanation:

b0                # Parse input as base 10 integer
1               # Push counter to the stack
{+.}      w!   # Increment counter while
{?!.>}     # The input is greater than the factorial of the counter
it # Return just the counter

# R, 56 52 bytes

function(n){while(n>(T=T*(F=F+gmp::as.bigz(1))))1;F}

Try it online!

Thanks to Dominic van Essen for the golfs and bug catch!

Takes input as a string.

• Why do you need the extra ;n at the end? All it seems to do is print back the input...? May 21, 2020 at 18:58
• @DominicvanEssen oops! I was testing my scan() theory to see about double loss of precision and forgot to take it out. Thanks for the catch! May 21, 2020 at 19:10
• On my installation of R3.6.2, the following 52 byte function works function(n){while(n>(T=T*(F=F+gmp::as.bigz(1))))1;F}, and accepts either numeric input or a string for big numbers (factorial(gmp::as.bigz(200))). But for some reason that I don't understand, it won't run on 'Try it online'... May 21, 2020 at 20:41
• I don't know what I was doing wrong; it seems to work ok now May 21, 2020 at 20:53
• @DominicvanEssen that's clever! I think the fact that > coerces its arguments' types would be worth adding as a tip! May 21, 2020 at 21:01

# Try it!

julia> f=n->findfirst(x->factorial(x)==n,1:n)

julia> @benchmark f(121645100408832000)
BenchmarkTools.Trial:
memory estimate:  0 bytes
allocs estimate:  0
--------------
minimum time:     32.801 ns (0.00% GC)
median time:      33.246 ns (0.00% GC)
mean time:        33.661 ns (0.00% GC)
maximum time:     56.452 ns (0.00% GC)
--------------
samples:          10000
evals/sample:     993
• Welcome to Code Golf, and nice first answer. You can use Try it online! to let people try your code online. It also calculates the byte count and generates the SE answer for you. You can use it like this. You can exclude the f= part from the byte count since it works as an anonymous inline function. May 22, 2020 at 4:18
• You can also switch to an older Julia version and save a few bytes by using gamma instead of factorial: 34 bytes May 22, 2020 at 9:34
• @Bubbler Thanks for the tips, I'm new to the community and looking forward to contribute. May 22, 2020 at 17:59