Question

求小于2001且与2001互质的所有自然数的和

Answer 1

2001=3×23×29，利用容斥原理，小于2001的数中，
3的倍数有666个，（1+2+3+…+666）×3=333×667×3=666333，
23的倍数有86个，（1+2+3+…+86）×23=43×87×23=86043，
29的倍数有68个，（1+2+3+…+68）×29=34×69×29=68034，
666333+86043+68034=820410，
3和23的公倍数有28个，（1+2+3+…+28）×69=14×29×69=28014，
3和29的公倍数有22个，（1+2+3+…+22）×87=11×23×87=22011，
23和29的公倍数有2个，（1+2）×667=3×667=2001，
28014+22011+2001=52026，
1001到1中间有1000个数字的总和是：
1+2+3+4+5+6…+1999+2000=（1+2000）×2000÷2=2001000，
2001000-820410+52026=1232616，
答：小于2001且与2001互质的所有自然数的和是1232616．

Answer 2

2001=3×23×29