Code Golf Stack Exchange is a question and answer site for programming puzzle enthusiasts and code golfers. It only takes a minute to sign up.
Sign up to join this community
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.
lambda n:len(`n**8L`)**.6//1
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.
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.
\$\endgroup\$
¯!
Exactly the same as non-extended APL answer but just with the shorter syntax.
! is factorial function, ¯ prefix gives the inverse function of it.
inverse factorial
\$\endgroup\$
!€i
i The first index (from 1) of the input in
!€ the factorials of every integer from 1 to the input.
Æ!L’, which is just plain silly.
\$\endgroup\$
May 21, 2020 at 8:32
ℕ₁ḟ
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.
->n,x=0{2>n/=x+=1or redo;x}
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.
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[#!&]
(For[x=0,x!<#,++x];x)& is only 22 bytes; I wonder if there's a way to golf it below 20.
\$\endgroup\$
May 23, 2020 at 8:41
.+
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.
match(scan(),cumprod(1:170))
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...
n=scan();while(n>(T=T*(F=F+1)))n;F
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...
match(n<-scan(),cumprod(1:n))
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'
T as a variable idea! I will immediately incorporate this, and the obvious follow-up...
\$\endgroup\$
May 21, 2020 at 17:53
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/…
\$\endgroup\$
May 21, 2020 at 17:56
[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.
\$\endgroup\$
0?[r1+d_3R/d1<F]dsFx/p
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.
.I*F
.I*F
.I : Inverse function of
*F : factorial
fqQ*F
-1 byte thanks to @FryAmTheEggman
fqQ*F
f : First positive integer value where
Q : input
q : is equal to
*F : factorial of value
fqQ*F.
\$\endgroup\$
May 21, 2020 at 15:29
(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
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.
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.
\$\endgroup\$
f= as the result get automatically assigned to the value ans. Hence 24
\$\endgroup\$
Aug 2, 2020 at 12:07
SWI-Prolog, 50 bytes
:-[library(clpfd)].
c(F,N):-F#=1,N#=1;c(F//N,N-1).
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!.
€mΠN
€ the index of implicit input in ...
mΠ ... map factorial over ...
N ... the natural numbers
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).
oomMOoMOOMoOMMMOOOmoOMMMmoOMoOmOoMOOmoOMMMmoOMMMMOOMOomOomOoMOomoOmoOmoomOomOomOoMoOmoOmoomOoMOomoomoOmoOOOM
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
=MATCH(A1,FACT(ROW(1:170)),0)
math.factorials, Saved 9 bytes thanks to @Bubbler!
[ dup [1,b] [ n! = ] with find ]
Saved 16 bytes thanks to @Bubbler!
[ 1 over [1,b] [ * 2dup = ] find ]
There's probably a better idiom for this, but I can't find it right now.
math.factorials, n! is a golfier synonym of factorial. Also, using with seems to be slightly shorter here.
\$\endgroup\$
n!. with looks like a pretty interesting function.
\$\endgroup\$
I was just copying Bubbler's solution. I didn't write it, so it's community wiki.
!⍣¯1
⍣¯1 The inverse of this function:
! Factorial function
Ｎθ⊞υ¹Ｗ‹Πυθ⊞υＬυＩ⌈υ
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.)
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
b01{+.}{?!.>}w!it
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
function(n){while(n>(T=T*(F=F+gmp::as.bigz(1))))1;F}
Thanks to Dominic van Essen for the golfs and bug catch!
Takes input as a string.
;n at the end? All it seems to do is print back the input...?
\$\endgroup\$
May 21, 2020 at 18:58
scan() theory to see about double loss of precision and forgot to take it out. Thanks for the catch!
\$\endgroup\$
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'...
\$\endgroup\$
May 21, 2020 at 20:41
> coerces its arguments' types would be worth adding as a tip!
\$\endgroup\$
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
f= part from the byte count since it works as an anonymous inline function.
\$\endgroup\$
xandnare positive integers. As such646077305624121491462330357080396430806673805704796612248389053020040737981389397373513335318926846519441974218777961448245634895440330929720840926954349439434654453860427703550673839109903970520283495061590634864022312082259902655711571689179112428197039756156051147969300077437438615382409042832551650139224687809841080780412598454920634889005911333104355143592477664451230317936640000000000000000000000000000000000000000000000000000000is a perfectly valid value for n :-) \$\endgroup\$