sidef-scripts/Math/inverse_of_factorial.sf

#!/usr/bin/ruby

# Daniel "Trizen" Șuteu
# Date: 29 April 2018
# https://github.com/trizen

# Compute the inverse of n-factorial.
# Returns correct values only for factorial numbers.

func p_adic_inverse (p, k) {

    var n = (k * (p - 1))

    while (factorial_power(n, p) < k) {
        n -= (n % p)
        n += p
    }

    return n
}

func inverse_of_factorial (f) {

    return 1 if (f == 1)

    var t = valuation(f, 2)         # largest power of 2 in f
    var z = p_adic_inverse(2, t)    # smallest number z such that 2^t divides z!
    var d = factor(z + 1)[-1]       # largest prime factor of z+1

    if (valuation(f, d) == factorial_power(z+1, d)) {
        return z+1
    }

    return z
}

for n in (1..30) {

    var f = n!
    var i = inverse_of_factorial(f)

    say "#{i}! = #{f}"

    assert_eq(i, n)
}