The problem asks to find a value for $$n$$ for which $$\phi(n)$$ is a permutation of the digits of $$n$$, and for which $$n/\phi(n)$$ is at a minimum. A brief refresher of what the totient function is might be helpful here.
Basically (lifted right from Wikipedia):
In number theory, Euler's totient or phi function, $$\phi(n)$$ is an arithmetic function that counts the number of positive integers less than or equal to n that are relatively prime to n. That is, if n is a positive integer, then $$\phi(n)$$ is the number of integers k in the range 1 ≤ k ≤ n for which $$gcd(n, k) = 1$$.
Notably, $$\phi(p) = p - 1$$ if $$p$$ is prime. This is because $$p$$ has no other divisors besides itself and 1, so all positive integers less than $$p$$ are relatively prime to it.
This gives a little insight on how to solve the problem: if $$n$$ happens to be prime, then $$n/\phi(n)$$ = $$n/(n - 1)$$, which is basically the smallest you can get that ratio to be. If it so happened that $$n$$'s digits are a permutation of $$\phi(n)$$ in that case, I'd have the winning number. With this strategy, all I would have to do is find a bunch of primes around the vicinity of $$10^8$$ and check the permutation constraint.
Unfortunately, since $$\phi(p) = p - 1$$, $$p$$ and $$\phi(p)$$ must differ by at least one digit, so that idea is out the window.
However, the ratio $$n/\phi(n)$$ also happens to be small if $$n$$ is a semi-prime (that is, if $$n$$ is the product of two primes). In this case, $$n$$ will have one or two other divisors besides $$n$$ itself (one in the case that the two primes are not distinct), so looking for semi-primes is the next best thing after looking for primes.
Having no idea where to start looking for these primes, I just started by poking around primes near $$\sqrt{10^8}$$, and testing if they had the two properties I was looking for. The following Clojure program eventually happens upon the result in less than a minute's time:
; lib/core.clj contains some general functions for calculating the integer
; square root, and for loading in a big list of pre-calculated primes.
(load-file "lib/core.clj")
(use
'[clojure.math.combinatorics]
'[lib.core :only (isqrt load-primes)])
(def primes
(load-primes "../data/primes.txt"))
(def limit (int 1e7))
; Search around the radius of (sqrt 1e7)
(def ps
(take-while #(<= % (* 2 (inc (isqrt limit)))) primes))
; Create pairs for semi-primes
(def pairs
(combinations ps 2))
(defn permutation?
"Returns true if a's digits are a permutation of b's."
[a b]
(let [digits #(sort (into [] (str %)))]
(= (digits a) (digits b))))
(defn phi
"Calculates the totient of a semi-prime created from p and q."
[p q]
(* (dec p) (dec q)))
(defn f
"Creates a map entry of n/phi(n) -> [p q]."
[pair]
(let [p (first pair)
q (second pair)
n (* p q)]
[(/ n (phi p q)) [p q]]))
(defn g
"Returns true if the totient of the semi-prime generated from [p q] is a
permutation of that semi-prime."
[pair]
(let [p (first pair)
q (second pair)
n (* p q)]
(permutation? n (phi p q))))
; Create a map of n/phi(n) -> [p q], filtering out semi-primes who are
; larger than 1e7
(def h
(filter #(<= (apply * (second %)) 10000000)
(apply merge (cons {} (map f pairs)))))
(let [entry (first (drop-while #(not (g (second %))) (sort h)))
pair (second entry)
p (first pair)
q (second pair)]
(println (* p q)))
You can view the full source here.
