Not Twice Again

Basic idea

As in the solution of this problem , we partition all integers $1, \dots, 20$ into groups that differ by factors of two:

$\begin{array}{|r|r|r|r|r|} 20 & 10 & 5 \\ 19 \\ 18 & 9 \\ 17 \\ 16 & 8 & 4 & 2 & 1 \\ 15 \\ 14 & 7 \\ 13 \\ 12 & 6 & 3 \\ 11 \end{array}$

At best, we can take every other element from each row. To maximize the sum, we take the first, third, and fifth column. The required sum is therefore $X_{20} = 20 + 19 + 18 + 17 + 16 + 15 + 14 + 13 + 12 + 11 + 5 + 4 + 3 + 1 = \boxed{168}.$

Quicker count

For a quicker count, let $T_n = \sum_{i=1}^n = \tfrac12n(n+1)$ be the $n$ th triangle number. We realize that the required sum is $\begin{aligned} X_{20} & = (1 + \dots + 20) - (1 + \dots + 10) + (1 + \dots + 5) - (1 + \dots + 2) + 1 \\ & = T_{20} - T_{10} + T_5 - T_2 + T_1 = 210 - 55 + 15 - 3 + 1 = 168.\end{aligned}$

---

General solution

In general, given the number $N$ we see that the solution is $X_N = T_N - T_{\lfloor N/2 \rfloor} + T_{\lfloor N/4 \rfloor} - T_{\lfloor N/8 \rfloor} + \cdots$

Cute little formula

We also have $X_N = \frac{6N^2 + 5N + 3s_N + a_N}{15}.$ Here, $a_N$ and $s_N$ are defined in terms of the binary digits of $N = \overline{\cdots b_4 b_3 b_2 b_1 b_0}_2$ . $a_N$ is the alternating digit sum , $a_N = b_0 - b_1 + b_2 - b_3 +- \cdots = \sum_{j=0}^\infty (-)^j b_j;$ for $s_N$ I have no fancy name, but it is defined as $\begin{aligned} s_N & = b_0N - b_1\left\lfloor \frac N 2 \right\rfloor + b_2\left\lfloor \frac N 4 \right\rfloor - b_3\left\lfloor \frac N 8 \right\rfloor +- \cdots \\ & = b_0(b_0 + 2b_1 + 4b_2 + \cdots) - b_1(b_1 + 2b_2 + 4b_3 + \cdots) + b_2(b_2 + 2b_3 + 4b_4 + \cdots) -+ \cdots \\ & = \sum_{j=0}^\infty (-)^j b_j \sum_{k=0}^\infty 2^k b_{j+k}.\end{aligned}$

In the case of $N = 20 = 10100_2$ , we have $\begin{aligned} a_{20} & = 0 - 0 + 1 - 0 + 1 = 2; \\ s_{20} & = 0\cdot 20 - 0 \cdot 10 + 1\cdot 5 - 0\cdot 2 + 1\cdot 1 = 6; \end{aligned}$ so that $X_{20} = \frac{6\cdot 400 + 5\cdot 20 + 3\cdot 6 + 2}{15} = \frac{2520}{15} = 168.$

Proof of cute little formula

By induction on the binary digits of $N$ . Write $N = 2n + b$ , with $b = 0$ or $1$ . Then we have

$\begin{aligned} X_N & = T_N - X_n; \\ a_N & = b - a_n; \\ s_N & = bN - s_n. \end{aligned}$

Since $X_0 = a_0 = s_0 = 0$ , the formula is obviously true for $X_0 = 0$ (Base Step).

For the Induction Step, suppose the formula applies to $n$ ; we multiply by 30 to get $30X_n = 12n^2 + 10n + 6s_n + 2a_n$ . Then $\begin{aligned} 30X_N & = 30T_N - 30X_n \\ & = 15(2n+b)(2n+b+1) - (12n^2 + 10n + 6s_n + 2a_n) \\ & = 60n^2 + 60bn + 15b^2 + 30n + 15b - 12n^2 - 10n - 6s_n - 2a_n \\ & = 12(4n^2 + 4bn + b^2) + 10(2n + b) + 6(b(2n + b) - s_n) + 2(b - a_n) & \text{note that}\ b^2 = b \\ & = 12N^2 + 10N + 6s_N + 2a_N, \end{aligned}$ as we needed to show.

---

So how did I find this little formula? I realized that $X_N = \tfrac12(N^2 - \lfloor N/2 \rfloor^2 + \lfloor N/4 \rfloor^2 - + \cdots) + \tfrac12(N - \lfloor N/2 \rfloor + \lfloor N/4 \rfloor -+ \cdots) =: \tfrac12Q_N + \tfrac12R_N,$ and since I already calculated $R_n = \tfrac13(2N + a_N)$ in a previous problem, I focused on the quadratic sum $Q_N$ .

I realized that for $N = 2^m$ the sum would become $Q_N = 4^m - 4^{m-1} + -\cdots \pm 1 = \tfrac15(4^{m+1} \pm 1) \approx \tfrac45N^2$ . Therefore I compared side-by-side the values of $5Q_N$ and $4N^2$ and looked at their differences:

$\begin{array}{cccc} N & Q_N & 5Q_N & 4N^2 & \delta_N = 5Q_N - 4N^2 \\ \hline 1 & 1 & 5 & 4 & +1 \\ 2 & 3 & 15 & 16 & -1 \\ 3 & 8 & 40 & 36 & +4 \\ 4 & 13 & 65 & 64 & +1 \\ 5 & 22 & 110 & 100 & +10 \\ 6 & 28 & 140 & 144 & -4 \\ 7 & 41 & 205 & 196 & +9 \\ 8 & 51 & 255 & 256 & -1 \\ 9 & 68 & 340 & 324 & +16 \\ 10 & 78 & 390 & 400 & -10 \\ \hline \end{array}$

The column $\delta_n$ showed some nice regularities, e.g. $\delta_{2n} = -\delta_n$ and $\delta_{2n+1} = 4n+1-\delta_n$ . A little further study shows that for $N = 2n+b$ , $\delta_N = (2N-1)b-\delta_n;$ splitting $\delta_N = 2s_N - a_N$ gave me the recursion definitions above, from which I derived the recipe for calculating $s_N$ .

Finally, putting everything together, $X_N = \tfrac12Q_N + \tfrac12R_N = \frac 12\cdot \frac{4N^2 + \delta_N}5 + \frac12\cdot \frac{2N + a_N}3 = \frac{3(4N^2 + 2s_N - a_N) + 5(2N + a_N)}{30} = \frac{12N^2 + 10N + 6s_N + 2a_N}{30}.$