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

• Welcome to Code Golf. Every challenge on this site needs an objective winning criterion. code-golf should fit well here. – Bubbler May 20 at 23:54
• 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. – Bubbler May 20 at 23:54
• I edited in the winning criterion and clarified some parts (guessing it matches your intent). Tell me if something's wrong. – Bubbler May 21 at 5:18
• 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 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. – Bubbler May 22 at 4:33

# 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. – the default. May 21 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 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 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 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. – Unrelated String May 21 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!

# 05AB1E, 4 bytes

Å!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. – Giuseppe May 21 at 14:52
• First of all: thanks for the T as a variable idea! I will immediately incorporate this, and the obvious follow-up... – Dominic van Essen May 21 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/… – Dominic van Essen May 21 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. – Giuseppe May 21 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!. – Dominic van Essen May 22 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. – FryAmTheEggman May 21 at 15:29

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

# 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!

# 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 at 11:46
• @ovs you can use quiet Try it online! – J42161217 May 21 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) – the default. May 21 at 14:32
• @mypronounismonicareinstate it is only for presentation purposes... – J42161217 May 21 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. – Greg Martin May 23 at 8:41

# [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! – Variax May 21 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. – David May 22 at 2:13
• Thanks for the comment, I guess I missed that. I'm using Octave so the result may vary slightly. – Variax May 23 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 – MarcinKonowalczyk Aug 2 at 12:07

# 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.)

# Rust, 57 bytes

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


Try it online!

# COW, 108 bytes

oomMOoMOOMoOMMMOOOmoOMMMmoOMoOmOoMOOmoOMMMmoOMMMMOOMOomOomOoMOomoOmoOmoomOomOomOoMoOmoOmoomOoMOomoomoOmoOOOM


Try it online!

## Explanation

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

: n/(i!)     : n/((i-1)!)     : i     : i_temp

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


# 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...? – Dominic van Essen May 21 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! – Giuseppe May 21 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'... – Dominic van Essen May 21 at 20:41
• I don't know what I was doing wrong; it seems to work ok now – Dominic van Essen May 21 at 20:53
• @DominicvanEssen that's clever! I think the fact that > coerces its arguments' types would be worth adding as a tip! – Giuseppe May 21 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. – Bubbler May 22 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 – Kirill L. May 22 at 9:34
• @Bubbler Thanks for the tips, I'm new to the community and looking forward to contribute. – jling May 22 at 17:59

# 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

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. – Wheat Wizard May 27 at 16:45

# Python 2, 73 bytes

lambda x:[n for n in range(1,x)if reduce(lambda a,b:a*b,range(1,n+1))==x]


Try it online!

# Keg, 10 bytes

&1{:¡⑻≠|1+


Try it online!

# 05AB1E, 5 bytes

∞.Δ!Q


Try it online!

# JavaScript (V8), 29 bytes

f=(n,i=1)=>n/i^1?f(n/i,++i):i


Try it online!

• yes, your are right – Yaroslav Gaponov May 21 at 10:20
• @Arnauld f(1) required to be 1, your function output false. – tsh May 22 at 3:20
• @tsh My bad. Here is another 28 that works for n=1. – Arnauld May 22 at 8:58

# 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