オイラーのトーティエント関数 φ(n) [φ関数と呼ばれることもある] は、n に対して互いに素である、 n より小さい数の数を決定するのに使用される。
例えば、1、2、4、5、7、8はすべて9より小さく、9に対して互いに素であるため、φ(9)=6となる。
| n |
Relatively Prime |
φ(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=6では、n≦10で最大n/φ(n)が得られることがわかる。
n/φ(n)が最大となるn≦1,000,000の値を求めよ。