ホーム - 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$.
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 を求めよ.

(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)