ホーム - Project Euler

Problem 69¶

Totient Maximum¶

Euler's totient function, $\phi(n)$ [sometimes called the phi function], is defined as the number of positive integers not exceeding $n$ which are relatively prime to $n$. For example, as $1$, $2$, $4$, $5$, $7$, and $8$, are all less than or equal to nine and relatively prime to nine, $\phi(9)=6$.

It can be seen that $n = 6$ produces a maximum $n/\phi(n)$ for $n\leq 10$.

Find the value of $n\leq 1,000,000$ for which $n/\phi(n)$ is a maximum.

トーティエント関数の最大値¶

オイラーのトーティエント関数, φ(n) [時々ファイ関数とも呼ばれる]は, n と互いに素な n 未満の数の数を定める. たとえば, 1, 2, 4, 5, 7, そして8はみな9未満で9と互いに素であり, φ(9)=6.

n ≤ 10 では n/φ(n) の最大値は n=6 であることがわかる.

n ≤ 1,000,000で n/φ(n) が最大となる値を見つけよ.

(import (scheme base)
        (gauche base))

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

;;; 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 はたくさんあった方が良い
;;; 以上のことから、小さな素数をかけていって10^6を超えないところ
;;; までを求めれば良い

(define (answer max-num)
  (let loop ([product 1] [rest-primes my-primes])
    (let ([next-product (* product (car rest-primes))])
      (if (< max-num next-product)
        product
        (loop next-product (cdr rest-primes))))))

(define answer-69 (answer #e1e6))

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