MathJax

SyntaxHighlighter

Highlight

Custom CSS

Thursday, May 30, 2013

Project Euler #70: Totient permutation

Here is problem #70.

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.
Post a Comment