If we break 2004 into its prime factorization, we see 204 = 2² × 3¹ × 167¹. To determine the number of total factors, we increase each of the exponents in the prime factorization by 1 and multiply these new numbers: (2 + 1)(1 + 1)(1 + 1) = 12 total factors.

The first 2004 positive integers are 1, 2, 3, …, 2002, 2003, and 2004. Notice we can pair up the numbers in this list by “folding” the list in half so that the last number matches with the first, the second-to-last matches with the second, the third-to-last matches with the third, and so on until the middle two numbers (1002 and 1003) are paired together. Notice that the sum of each pair of numbers is 2005 and there are 1002 total pairs. We can now calculate that the sum of all of the 2004 integers is 1002(2005) = 2,009,010. Can you find a formula that would work for determining the sum of the first n positive integers?

From the last problem, we know that if all of the integers in the list were positive, the sum would be at least 2, 009,010. Therefore, we are looking for a much smaller sum and there must be quite a few negative integers in the list. We do know, however, that there are more positive integers than negative integers. If we tried to split them down the middle as much as possible, we would have about 1002 positive integers and 1002 negative integers. But don’t forget 0… so we would really have –1001, –1000, –999, …, –1, 0, 1, …, 1000, 1001, 1002. Notice this list has a sum of 1002, which is also the last integer in the list, since every other positive integer has a matching negative integer, bringing the sum of the pair to 0. Notice, too, that even sliding the list “up” one integer increases the sum by over 2000: –1000, –999, –998 …, –1, 0, 1, …, 1001, 1002, 1003. The sum for this new list is 1001 + 1002 + 1003 = 3006. (Notice the sum can be found by adding the positive integers at the end of the list that do not have matching negative integers in the list.) Bumping the list “up” by just one more place will probably get us to our answer: –999, –998, –997 …, –1, 0, 1, …, 1002, 1003, 1004 yields a sum of 1000 + 1001 + 1002 + 1003 + 1004 = 5010 and the smallest integer in the list is –999.