Tricky sums indeed!

Using the simple mathematical equation for arithmetic progressions:

$S(n)=\frac { n(n+1) }{ 2 }$ , we can create a sum function that adds all natural numbers less than or equal to n.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

long long sum(long long upperbound)
{
         long long sum = upperbound * (upperbound + 1) / 2;
         return sum;
}

long long subtract(long long num)
{
          long long sub_val = 0;
          for (int i = 0; power <= num; i++) {
                 power = pow(2, i);
                 if (power > num)
                    break;
             else
                 sub_val += (2 * power); // notice that we subtract twice the value
           }
           return sub_val;
}

Then in the main function:

1
2
3
4
5
6
7
8

int main()
{
       long long solution = 0;
       for(int i = 4; i <= 10000; i++) {
                solution += add(i) - subtract(i);  
       }
       cout << "The solution is " << solution << endl;
} 

As Brian Riccardi noted, there is a formula for $\Theta(n)$ . This in turn implies a formula for a sum of $\Theta(n)$ . If we define $M(n) = \lfloor \log_2n\rfloor$ , then $\begin{array}{rcl} \Theta(n) & = & \displaystyle \sum_{j=1}^n j - 2\sum_{2^j \le n} 2^j \; =\; \tfrac12n(n+1) - \sum_{2^j \le n}2^{j+1} \\ \displaystyle \sum_{n=1}^N \Theta(n) &= & \displaystyle \tfrac16N(N+1)(N+2) - \sum_{n=1}^N \sum_{2^j \le n} 2^{j+1} \\ &=& \displaystyle \tfrac16N(N+1)(N+2) - \sum_{j=0}^{M(N)}(N+1-2^j)2^{j+1} \\ &=& \displaystyle \tfrac16N(N+1)(N+2) -2(N+1)\big(2^{M(N)+1}-1\big) + \tfrac23\big(4^{M(N)+1}-1\big) \end{array}$ The difference between the value of this expression for $N=10000$ and $N=3$ is $\boxed{166567934208}$ . No programming is necessary, only computation.

\text{\$\theta(n)=(\displaystyle\sum\_{k=1}^{n}k)-2(\displaystyle\sum_{k=1}^{\lfloor log_2(n) \rfloor}2^k)=\frac{n(n+1)}{2} -2(2^{\lfloor log_2(n) \rfloor+1}-1)\$} \\

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

#include <iostream>
using namespace std;

int log2_int(int n)
{
    int k=1;
    while( (1<<(k+1) )<=n ) ++k;
    return k;
}

long long theta(long long n)
{
    return n*(n+1)/2 - 2*( (1<<(log2_int(n)+1)) -1);
}

int main()
{
    long long sum=0;
    for(int i=4; i<=10000; ++i)
        sum+=theta(i);
    cout << sum;

    return 0;
}

The python 3:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12

def theta(n):
    k = 1
    s = 0
    for i in range(n+1):
        if i == k:
            s -= i
            k *= 2
        else:
            s += i
    return s

print(sum(theta(n) for n in range (4,10001)))

Noticing that $N \le 10000$ , it will take less than a minute even with an $O(n^2)$ algorithm. While one could design a more efficient algorithm, it's easiest to just brute force this one

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

def isp2(n)
    (n == 1 or n == 2 or n == 4 or n == 8 or n == 16 or n == 32 or n == 64 or n == 128 or n == 256 or n == 512 or n == 1024 or n == 2048 or n == 4096 or n == 8192)
end

def theta(n)
    sum = 0
    (1..n).each do |x|
        if (isp2(x))
            sum -= x
        else
            sum += x
        end
    end
    sum
end

ans = 0
puts theta(4)
(4..10000).each do |x|
    ans += theta(x)
end

puts ans

A simple DP approach suffices.