22
\$\begingroup\$

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.

\$\endgroup\$
5
  • 7
    \$\begingroup\$ 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. \$\endgroup\$
    – Bubbler
    Commented May 20, 2020 at 23:54
  • \$\begingroup\$ Is there an upper bound on the possible inputs? \$\endgroup\$
    – xnor
    Commented May 21, 2020 at 8:14
  • 3
    \$\begingroup\$ 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) \$\endgroup\$
    – JDL
    Commented May 21, 2020 at 10:29
  • 2
    \$\begingroup\$ @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. \$\endgroup\$
    – Bubbler
    Commented May 22, 2020 at 4:33
  • 1
    \$\begingroup\$ @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 :-) \$\endgroup\$ Commented May 23, 2020 at 18:01

39 Answers 39

1
2
2
\$\begingroup\$

PowerShell, 34 bytes

param($n)for(;++$x-$n;$n/=$x){};$x

Try it online!

\$\endgroup\$
1
  • \$\begingroup\$ nice. PS allows you to skip the ; after the operators for, if, param and etc. Try it online! \$\endgroup\$
    – mazzy
    Commented Apr 1, 2021 at 10:35
1
\$\begingroup\$

Keg, 10 bytes

&1{:¡⑻≠|1+

Try it online!

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

05AB1E, 5 bytes

∞.Δ!Q

Try it online!

\$\endgroup\$
0
1
\$\begingroup\$

JavaScript (V8), 29 bytes

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

Try it online!

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

Prolog (SWI), 62 55 bytes

X-N-N:-A is N/D,A==1,X is D;X-N/D-(D+1).
f(X,N):-X-N-1.

Try it online!

If N equals D, sets X to D, otherwise, it calls itself with N/D and D+1.

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

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!

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

HP‑41C series, 18 B

The \$x\$ in \$x! = n\$ can be determined by repeatedly dividing \$n\$ by an incrementing divisor (first \$1\$, then \$2\$, then \$3\$ and so forth) until the quotient equals the (next) divisor. The program works correctly up to and including \$x = 39\$.

01♦LBL "S"         5 Bytes    global label requires 4 + (length of string) Bytes
   NULL            1 Byte     invisible Null byte before numbers
02 1               1 Byte     place 1 on top of stack; X ≔ 1 ; Y ≔ 𝘯

03 LBL 00          2 Bytes    mark head of this loop with (local) label 00 ──┐
                                                                             │
04 X=Y?            1 Byte     if X = Y ──┐                                   │
05 RTN             1 Byte                └── then return                     │
                                                                             │
06 ∕               1 Byte     lastX ≔ X ;  X ≔ Y ∕ X                         │
                                                                             ↑
07 LASTX           1 Byte     put lastX back on top of stack again           │
   NULL            1 Byte     invisible Null byte before numbers             │
08 1               1 Byte     place 1 on top of stack                        │
09 +               1 Byte     sum X and Y, stack drops by one item           │
                                                                             │
10 GTO 00          2 Bytes    go to (local) label 00  ───────────────────────┘

Since this is pretty abstract, let’s consider a trace of the stack in the case \$n = 6 = 3! = x!\$. The step “sees” data from one row above, the result of a step follows in the same row. Empty cells are not relevant to the program.

step X Y Z T LastX
6
1 1 6
X=Y?
6 1
LASTX 1 6
1 1 1 6
+ 2 6 1
GTO 00
X=Y?
3 2
LASTX 2 3
1 1 2 3
+ 3 3 1
X=Y?
RTN

Note that GTO searches for a local label downward in program memory and wraps to the beginning of the currently executed program. To inhibit local label search, append an END command (3 Bytes). The above program presumes there are no other programs (following) in program memory, so the permanent (= always there) END is sufficient.

\$\endgroup\$
0
\$\begingroup\$

Add++, 23 bytes

D,f,@,R¦*BK=
L,dBkRÞ{f}

Try it online!

This is what happens when there's no "find index" or "first n where" or auto-vectorisation.

Explained

D,f,@,R¦*BK= # Helper function f
      R      #    range 1...n
       ¦*    #    reduce by multiplication
         BK= #    does that equal the global register?
L,dBkRÞ{f}   # main lambda
  dBk        #    place the input into the global register.
     R       #    range 1...input
      Þ{f}   #    filter by helper function f
\$\endgroup\$
0
\$\begingroup\$

Vyxal 3 G, 5 bytes

K!=Þκ

Try it Online!

\$\endgroup\$
1
2

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.