Bruteforcers will be doomed!

Who needs a computer? I used pen and paper :)

We add all multiples of 3 and all multiples of 11 separately. Then we subtract the multiples of 33.

From the digit sum we see that $10^{20} \equiv 1$ mod 3, and from the alternating digit sum/difference that $10^{20} \equiv 1$ mod 11. It also follows that it is $\equiv 1$ mod 33. Thus we must find $\left(\sum_{k=1}^{(10^{20}-1)/3} 3k\right) + \left(\sum_{k=1}^{(10^{20}-1)/11} 11k\right) - \left(\sum_{k=1}^{(10^{20}-1)/33} 33k\right).$

Since $\sum_{k=1}^n k = n(n+1)/2,$ this expression can be written as $\frac{(10^{20}-1)(10^{20}+2)}6 + \frac{(10^{20}-1)(10^{20}+10)}{22} - \frac{(10^{20}-1)(10^{20}+32)}{66}.$

Time for arithmetic modulo $N = 1\:000\:000\:007 = 10^9+7$ . We use the fact that $10^9 \equiv -7$ mod $N$ . Thus $10^{20}-1 = 100\cdot (10^9)^2 - 1 \equiv 100\cdot (-7)^2 - 1 = 4899\ \text{mod}\ N,$ and $\frac{10^{20}+2}6 \equiv \frac{4902}6 = 817\ \text{mod}\ N.$

Unfortunately, the last two terms are more difficult. We simplify them to $4899\left(\frac{4910}{22} - \frac{4932}{66}\right) = 4899\cdot\frac{1633}{11}\ \text{mod}\ N,$ but we must evaluate the fraction modulo $N$ . The trick is to add multiples of $N$ to the numerator to make it a multiple 11.

Now $1633 \equiv -1+6-3+3 = 5$ mod 11, and $N \equiv -1+7 = 6$ mod 11; therefore $1633 + N \equiv 5 + 6 \equiv 0$ mod 11. Thus we have $\frac{1633}{11} \equiv \frac{1\:000\:001\:640}{11} = 90\:909\:240\ \text{mod}\ N.$

At this point we know that the answer is equal to $4899\cdot (817 + 90\:909\:240) = 4899\cdot 90\:910\:057,$ modulo $N$ . Since I used only pen and paper so far, I do this multiplication by hand as well, as $4900\cdot 90\:910\:057 - 90\:910\:057 = 445\:459\:279\:300 - 90\:910\:057;$ since we work modulo $N = 1\:000\:000\:007$ , I can subtract 445 billions from the first term provided I also subtract 445 sevens, making the answer $\equiv 459\:279\:300 - 7\cdot 445 - 90\:910\:057 =\boxed{368\:366\:128}.$

I used windows scientifc calculator to calc n/66(13n+33) and mod 1000000007

Easy way to solve it is by doing this (pseudocode) -

1
2
3
4

sum = 0
for x = 1 to 10^20
    if x % 3 = 0 or x % 11 = 0
        sum += x 

However, the code cannot be executed in a feasible amount of time due to the size of the search. A much better way would be to use some knowledge of Number Theory and Combinatorics.

Sum of multiples of 3 can be written as

$3+6+9\dots \left( 10^{ 20 }-4 \right) +\left( 10^{ 20 }-1 \right) =3\left( 1+2+3\dots \frac { \left( 10^{ 20 }-4 \right) }{ 3 } +\frac { \left( 10^{ 20 }-1 \right) }{ 3 } \right)$

Similarly, sum of multiples of 11 can be written as

$11+22+33\dots \left( 10^{ 20 }-12 \right) +\left( 10^{ 20 }-1 \right) =11\left( 1+2+3\dots \frac { \left( 10^{ 20 }-12 \right) }{ 11 } +\frac { \left( 10^{ 20 }-1 \right) }{ 11 } \right)$

Using summation formula , we can express the above sums as

$3\times \frac { \left[ \left( \frac { { 10 }^{ 20 }-1 }{ 3 } \right) \left( \frac { { 10 }^{ 20 }-1 }{ 3 } +1 \right) \right] }{ 2 }$ and $11\times \frac { \left[ \left( \frac { { 10 }^{ 20 }-1 }{ 11 } \right) \left( \frac { { 10 }^{ 20 }-1 }{ 11 } +1 \right) \right] }{ 2 }$

We can now add these two.

However, we overcounted. We need to subtract all the multiples of 33 from the sum to obtain the answer, which can be done using the same way as described above. Finally, modulo the answer by 1000000007.

While this may sound incredibly hard to compute, computers can do it well under a second.

Solution -

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

n = 10 ** 20
summ = 0

for x in [3, 11]:
    lar = n / x
    summ += x * (lar * (lar + 1)) / 2

lar = n / 33

summ -= 33 * (lar * (lar + 1)) / 2
print summ % 1000000007