Project Euler

[ホーム](https://redmine.noppi.jp) - [[Wiki|Project Euler]]

# [[Problem 70]]

## Totient Permutation

Euler's totient function, $\phi(n)$ [sometimes called the phi function], is used to determine the number of positive numbers less than or equal to $n$ which are relatively prime to $n$. For example, as $1, 2, 4, 5, 7$, and $8$, are all less than nine and relatively prime to nine, $\phi(9)=6$.<br>The number $1$ is considered to be relatively prime to every positive number, so $\phi(1)=1$.

Interestingly, $\phi(87109)=79180$, and it can be seen that $87109$ is a permutation of $79180$.

Find the value of $n$, $1 \lt n \lt 10^7$, for which $\phi(n)$ is a permutation of $n$ and the ratio $n/\phi(n)$ produces a minimum.

## トーティエント関数の置換

オイラーのトーティエント関数 φ(n) (ファイ関数とも呼ばれる) とは, n 未満の正の整数で n と互いに素なものの個数を表す. 例えば, 1, 2, 4, 5, 7, 8 は9未満で9と互いに素であるので, φ(9) = 6 となる.

1 は全ての正の整数と互いに素であるとみなされる. よって φ(1) = 1 である.

面白いことに, φ(87109)=79180 であり, 87109は79180を置換したものとなっている.

$1 \lt n \lt 10^7$ で φ(n) が n を置換したものになっているもののうち, n/φ(n) が最小となる n を求めよ.

```scheme

(import (scheme base)

        (gauche base)

        (scheme list))

(define (prime-generator)

  (let ([current 11]

        [primes '(2 3 5 7)]

        [inc 2]

        [next-inc (^n (if (= n 2) 4 2))])

    (^[]

      (let loop ([rest-primes primes])

        (if (null? rest-primes)

          (begin0

            current

            (set! primes (append primes `(,current)))

            (set! current (+ current inc))

            (set! inc (next-inc inc)))

          (let ([p (car rest-primes)])

            (cond

              [(< current (* p p))

               (begin0

                 current

                 (set! primes (append primes `(,current)))

                 (set! current (+ current inc))

                 (set! inc (next-inc inc)))]

              [(zero? (mod current p))

               (set! current (+ current inc))

               (set! inc (next-inc inc))

               (loop primes)]

              [else

                (loop (cdr rest-primes))])))))))

(define my-primes

  (generator->lseq 2 3 5 7 (prime-generator)))

(define (select-prime-list n1 n2)

  (drop-while

    (^n (< n n1))

    (take-while (^n (<= n n2))

                my-primes)))

(define (number->vector num)

  (assume (exact-integer? num))

  (assume (not (negative? num)))

  (let ([vec (make-vector 10 0)])

    (let loop ([rest num])

      (if (zero? rest)

        vec

        (let ([tail-num (mod rest 10)])

          (vector-set! vec tail-num

                       (+ (vector-ref vec tail-num) 1))

          (loop (div rest 10)))))))

(define (permutate? num1 num2)

  (let ([vec1 (number->vector num1)]

        [vec2 (number->vector num2)])

    (let loop ([index 0])

      (cond

        [(< 9 index) #t]

        [(not (= (vector-ref vec1 index)

                 (vector-ref vec2 index)))

         #f]

        [else

          (loop (+ index 1))]))))

;;; n の素因数が p1, p2, ... , pk の時

;;; φ(n) = n * (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk)

;;; φ(n)/n = (1 - 1/p1) * (1 - 1/p2) * ... * (1 - 1/pk)

;;;        = (p1 - 1)/p1 * (p2 - 1)/p2 * ... * (pk - 1)/pk

;;; ∴ n/φ(n) = p1/(p1 - 1) * p2/(p2 - 1) * ... * pk/(pk - 1)

;;;

;;; この時の n/φ(n) を最小化することを考えると

;;; 1. 各 p は大きい方が良い

;;; 2. 各 p は少ない方が良い

;;; 3. ただし、n が素数(pの数が1)の時は φ(n) = n - 1 なので

;;;     n と φ(n) が置換の数になることはありえない

;;; 以上のことから、p1 * p2 <= 10^7 を満たす

;;; なるべく大きな p1, p2 を求めれば良い

(define (totient p1 p2)

  (* p1 p2 (- 1 (/ 1 p1)) (- 1 (/ 1 p2))))

(define (select-numbers p1 p2 max-num)

  (filter (^c (<= (* (car c) (cdr c)) max-num))

          (fold-right (^[n lis]

                        (append

                          (map (^m (cons n m))

                               (select-prime-list (+ n 2) p2))

                          lis))

                      '()

                      (drop-right (select-prime-list p1 p2) 1))))

;;; 3162 が n^2 <= 10^7 を満たす最大の整数だったので

;;; とりあえず 2003 ～ 3997 の範囲で求めてみる

(define (perm-list)

  (filter (^c (permutate? (car c) (cdr c)))

          (map (^c `(,(* (car c) (cdr c))

                      . ,(totient (car c) (cdr c))))

               (select-numbers 2003 3997 #e1e7))))

(define (answer)

  (fold (^[lis knil]

          (if (< (cdr lis) (cdr knil))

            lis

            knil))

        `(0 . ,(greatest-fixnum))

        (map (^c `(,(car c)

                    . ,(/ (car c) (cdr c))))

             (perm-list))))

(define answer-70 (car (answer)))

(format #t "70: ~d~%" answer-70)

```