互質加排列

2015 = 5 × 13 × 31

由容斥原理, 不大於 2015 且與之互質的正整數有

2015 - (2015/5 + 2015/13 + 2015/31)

+ 2015/(5 × 13) + 2015/(5 × 31) + 2015/(13 × 31) - 2015/(5 × 13 × 31)

= 2015 - (13 × 31 + 5 × 31 + 5 × 13) + 31 + 13 + 5 - 1 = 1440 個。明顯 2014 為第 1440 個。而2015 - 1440 = 575,

設不大於 n 且與 2015 互質的正整數有 575 個, 則 n (1 - 1/5) (1 - 1/13) (1 - 1/31) ≈ 575 ,

n ≈ 805。 [805/5] = 161 , [805/13] = 61 , [805/31] = 25 ,

[805/(5 × 13)] = 12 , [805/(5 × 31)] = 5 , [805/(13 × 31)] = 1 ,

[805/(5 × 13 × 31)] = 0 ,

故不大於 805 且與 2015 互質的正整數有 805 - (161 + 61 + 25) + 12 + 5 + 1 - 0 = 576 個, 則 804 為第 576 個, 803 為第 575 個,

故第 2015 個與 2015 互質的正整數是 2015 + 803 = 2818 。

答案：

http://math.pro/db/viewthread.php?tid=2290&extra=&...

2015-07-07 00:21:36 補充：

104高雄市聯招 第12題

2015-07-07 00:22:31 補充：

http://math.pro/db/attachment.php?aid=2971&k=da1b8...