Let the function O(n) denote the sum of natural numbers, i, less than or equal to n. However, this function has one trick - if the number to be added, i, is a power of 2, then instead of adding we subtract the number.
Find O(4)+O(5)+O(6)+...+O(10000)
Let P(n) = O(1) + O(2) + ... + O(n). If all the numbers in each O() were simply added then P(n) would be the nth tetrahedral number T(n) = n*(n+1)*(n+2)/6. But to account for the subtraction then twice the sum of the powers of 2 need to be deducted from the tetrahedral calculation.
A tetrahedral number T(n) can also be expressed as sum{k=1 to n} (n+1-k)*k. The negatives in the P(n) calculation are where the value k is a power of two.
Let p be the number of powers of 2 not greater than n which means the largest power of 2 is then 2^(p-1). Then the amount to subtract from T(n) is twice the value sum{k=0 to p-1} (n+1-2^k)*(2^k) = (n+1)*(2^p-1) - (4^p-1)/3.
Then P(n) equals n*(n+1)*(n+2)/6 - 2*(n+1)*(2^p-1) + 2*(4^p-1)/3.
The sum requested O(4)+O(5)+...+O(10000) equals P(10000)-P(3). If n=3 then p=2 which makes P(3) = -4 and if n=10000 then p=14 which makes P(10000) = 166567934204. Then the sum sought is the difference of these two numbers, 166,567,934,208.
Solution
