IMO Hk TST

The answer is $2^{674} + 672$.

We claim that both $(2^r + 1, 2^s + 1)$ and $(2^r + 1, 2^s - 1)$ are of the form $2^a + 1$ or $1$ for any $r, s \in \mathbb{Z}^+$. We prove this by induction on $\min\{r, s\}$. The base case $\min\{r, s\} = 1$ is trivial since the greatest common divisor can only be $1$ or $3$. Assume this holds for all smaller cases and consider the inductive step.

For $(2^r + 1, 2^s + 1)$, WLOG assume $r \le s$. Let $s = qr + b$ where $0 \le b < r$. Then
$$2^s + 1 = 2^b(2^r)^q + 1 \equiv 2^b(-1)^q + 1 = \pm 2^b + 1 \pmod{2^r + 1}.$$
This shows $(2^r + 1, 2^s + 1) = (2^r + 1, 2^b \pm 1)$. As $b < r$, we are done by the inductive hypothesis.

Similarly, for $(2^r + 1, 2^s - 1)$, if $r \le s$, then we write $s = qr + b$ for some $0 \le b < r$ so that $(2^r + 1, 2^s - 1) = (2^r + 1, 2^b \pm 1)$. If $s < r$, then we write $r = qs + b$ for some $0 \le b < s$ so that $(2^r + 1, 2^s - 1) = (2^b + 1, 2^s - 1)$. In any case, we are done by the inductive hypothesis.

So we have proven the claim by induction. Next, note that $2^a + 1 \mid 2^r + 1$ if and only if $r = da$ for some odd integer $d$. (Again, by writing $r = qa + b$ with $0 \le b < a$, we can show that $2^a + 1 \mid 2^b(-1)^q + 1$ and hence $2^a + 1 \le |2^b(-1)^q + 1|$ unless $2^b(-1)^q + 1 = 0$. As $b < a$, the former case is impossible.) Therefore, the greatest common divisor of two terms is $2^a + 1$ only if both are of the form $2^{(2^k-1)a} + 1$. In particular, we cannot have $a > 673$ since otherwise one term is at least $2^{3(674)} + 1 > 2^{2019} + 1$.

On the other hand, $a$ can be one of $1, 2, \dots, 673$ as $(2^a + 1, 2^{3a} + 1) = 2^a + 1$.

Obviously, the greatest common divisor can also be 1. So the answer is
$$1 + (2^1 + 1) + (2^2 + 1) + \cdots + (2^{673} + 1) = 2^{674} + 672.$$