Problem 69 » 履歴 » リビジョン 2
リビジョン 1 (Noppi, 2024/01/30 11:21) → リビジョン 2/3 (Noppi, 2024/01/30 12:39)
[ホーム](https://redmine.noppi.jp) - [[Wiki|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$.
| **$n$** | **Relatively Prime** | **$\phi(n)$** | **$n/\phi(n)$** |
|--|--|--|--|
| 2 | 1 | 1 | 2 |
| 3 | 1,2 | 2 | 1.5 |
| 4 | 1,3 | 2 | 2 |
| 5 | 1,2,3,4 | 4 | 1.25 |
| 6 | 1,5 | 2 | 3 |
| 7 | 1,2,3,4,5,6 | 6 | 1.1666... |
| 8 | 1,3,5,7 | 4 | 2 |
| 9 | 1,2,4,5,7,8 | 6 | 1.5 |
| 10 | 1,3,7,9 | 4 | 2.5 |
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 | 互いに素な数 | φ(n) | n/φ(n) |
|--|--|--|--|
| 2 | 1 | 1 | 2 |
| 3 | 1,2 | 2 | 1.5 |
| 4 | 1,3 | 2 | 2 |
| 5 | 1,2,3,4 | 4 | 1.25 |
| 6 | 1,5 | 2 | 3 |
| 7 | 1,2,3,4,5,6 | 6 | 1.1666... |
| 8 | 1,3,5,7 | 4 | 2 |
| 9 | 1,2,4,5,7,8 | 6 | 1.5 |
| 10 | 1,3,7,9 | 4 | 2.5 |
n ≤ 10 では n/φ(n) の最大値は n=6 であることがわかる.
n ≤ 1,000,000で n/φ(n) が最大となる値を見つけよ.
```scheme
(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)
```