互質加排列

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=&page=1

2015-07-07 00:21:36 補充：
104高雄市聯招 第12題

2015-07-07 00:22:31 補充：
http://math.pro/db/attachment.php?aid=2971&k=da1b864a3c96ed81456f4ae1045c387e&t=1436199716&noupdate=yes