we know 1+2+3+...+n = n(n+1)/2
1+2+3+...+2000 = 2000 x 2001 / 2 = 2001000
2001000 mod 2000 = 1000, so we need to find out which value(s) lands on the 1000th point.
[n(n+1)/2] mod 2000 = 1000 =>
n(n+1) mod 4000 = 2000 =>
n(n+1) = 2000 + 4000k, k = 0, 1, ..., [n(n+1) - 2000]/4000
in another word, n(n+1) has to end up as an even multiple thousands (2000, 6000, 8000, 12000, etc), while n <= 2000.
Notice n and (n+1) are two consecutive numbers, the only hope is:
999 x 1000 = 999000, not even thousands (999)
1000 x 1001 = 1001000, not even thousands (1001)
No product of any other two consecutive numbers (< 2000) will produce a number with whole thousand (ending 3 zeros),
therefore, the 1000th position has not been landed by any other number before the number 2000,
hence 2000 is the answer.
