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")
  '[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]."
  (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."
  (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.

Thursday, May 23, 2013

Project Euler #69: Totient maximum

Here is a link to problem #69. Basically this problem serves as a gentle introduction to Euler's totient function. Just by looking at the definition you can get a hint about how to solve this problem.

Note that:

$$\phi(n) = n\prod_{p|n}(1 - \dfrac{1}{p})$$

...a proof of which can be found on the wikipedia page for the totient function.

Armed with that, we can consider maximizing this value:

$$\dfrac{n}{\phi(n)} = \dfrac{1}{\prod_{p|n}(1 - \dfrac{1}{p})}$$

It is plain to see that to maximize that ratio, we have to minimize the denominator. This will happen if there are a lot of $$p_{i}$$'s and each of them are very small, so basically we can hunt for this number by taking the product of the first few primes (a concept known as the primorial) such that the product is under 1000000.

As it turns out,

$$p_{7}\# = 510510 < 1000000$$ and $$p_{8}\# = 9699690 > 1000000$$ the number we want is 510510.