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.