sidef-scripts/Math/inverse_of_euler_totient.sf

#!/usr/bin/ruby

# Given a positive integer `n`, this algorithm finds all the numbers k such that φ(k) = n.

# Based on Dana Jacobsen's code from Math::Prime::Util,
# which in turn is based on invphi.gp v1.3 by Max Alekseyev.

# See also:
#   https://projecteuler.net/problem=248
#   https://en.wikipedia.org/wiki/Euler%27s_totient_function
#   https://github.com/danaj/Math-Prime-Util/blob/master/examples/inverse_totient.pl

func inverse_euler_phi (n) {

    var r = Hash(
        1 => [1]
    )

    n.divisors.each { |d|

        is_prime(d+1) || next

        var t = Hash()

        for k in (1 .. (n.valuation(d+1) + 1)) {

            var u = (d * (d+1)**(k-1))
            var v = (d+1)**k

            (n/u).divisors.each {|f|
                if (r.contains(f)) {
                    t{ f * u } := [] << r{f}.map{ _ * v }...
                }
            }
        }

        t.each { |i,v|
            r{i} := [] << v...
        }
    }

    return [] if !r.contains(n)
    return r{n}.sort
}

for n in (1..70) {
    var arr = inverse_euler_phi(n) || next
    say "φ−¹(#{n}) = [#{arr.join(', ')}]";
}

__END__
φ−¹(1) = [1, 2]
φ−¹(2) = [3, 4, 6]
φ−¹(4) = [5, 8, 10, 12]
φ−¹(6) = [7, 9, 14, 18]
φ−¹(8) = [15, 16, 20, 24, 30]
φ−¹(10) = [11, 22]
φ−¹(12) = [13, 21, 26, 28, 36, 42]
φ−¹(16) = [17, 32, 34, 40, 48, 60]
φ−¹(18) = [19, 27, 38, 54]
φ−¹(20) = [25, 33, 44, 50, 66]
φ−¹(22) = [23, 46]
φ−¹(24) = [35, 39, 45, 52, 56, 70, 72, 78, 84, 90]
φ−¹(28) = [29, 58]
φ−¹(30) = [31, 62]
φ−¹(32) = [51, 64, 68, 80, 96, 102, 120]
φ−¹(36) = [37, 57, 63, 74, 76, 108, 114, 126]
φ−¹(40) = [41, 55, 75, 82, 88, 100, 110, 132, 150]
φ−¹(42) = [43, 49, 86, 98]
φ−¹(44) = [69, 92, 138]
φ−¹(46) = [47, 94]
φ−¹(48) = [65, 104, 105, 112, 130, 140, 144, 156, 168, 180, 210]