12345678910111213141516171819202122232425262728293031323334353637383940414243444546474849505152535455565758596061626364656667686970717273 |
- #!/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]
|