ホーム - 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 (factorize num)
  (assume (exact-integer? num))
  (assume (<= 2 num))
  (let loop ([current 2] [rest num] [result '()])
    (cond
      [(= rest 1) (reverse result)]
      [(and (< num (* current current))
            (null? result))
       '()]
      [(< num (* current current))
       (reverse (cons rest result))]
      [(and (zero? (mod rest current))
            (null? result))
       (loop current
             (div rest current)
             (cons current result))]
      [(and (zero? (mod rest current))
            (= current (car result)))
       (loop current
             (div rest current)
             result)]
      [(zero? (mod rest current))
       (loop current
             (div rest current)
             (cons current result))]
      [else
        (loop (+ current 1) rest result)])))

; https://manabitimes.jp/math/667
(define (totient num)
  (assume (exact-integer? num))
  (assume (<= 2 num))
  (let ([lis (factorize num)])
    (if (null? lis)
      (- num 1)
      (apply * num
             (map (^n (- 1 (/ 1 n)))
                  lis)))))

(define (totient-100_0000-list)
  (map (^n
         (let ([totient-n (totient n)])
           `(,n ,totient-n ,(/ n totient-n))))
       (iota (- #e1e6 1) 2)))

(define answer-69
  (car
    (fold (^[lis current]
            (if (< (caddr current) (caddr lis))
              lis
              current))
          '(0 0 0)
          (totient-100_0000-list))))

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