Saudi Arabian Mathematical Competitions

We claim that all odd numbers are special, and the only special even number is $2$. For any even $N > 2$, the number relatively to $N$ must be odd, and $N$ cannot be expressed as a sum of $3$ positive odd numbers.

Now, suppose that $N$ is odd. We consider the binary decomposition of $N$
$$N = 2^{a_{1}} + 2^{a_{2}} + \ldots + 2^{a_{i}}.$$
Note that $(2^{t}, N) = 1$ and $i < \log_{2} N + 1$.

For any $i \leq k < N-1$, suppose that $N$ can be expressed as a sum of $k$ powers of $2$, i.e. $N = 2^{x_{1}} + \ldots + 2^{x_{k}}$. Then at least one of $x_{j} > 0$ (otherwise, $k = N$). Suppose that $x_{1} > 0$ then
$$N = 2^{x_{1}-1} + 2^{x_{1}-1} + 2^{x_{2}} + \ldots + 2^{x_{k}}.$$
So $N$ can be expressed as a sum of $k+1$ powers of $2$. This implies that, for any $k < \log_{2} N + 1$, $N$ can be expressed as a sum of $k$ positive integers that are relatively prime to $N$.

Now, start from $k = 2$. Let $2^{a}$ be the largest power of $2$ such that $2^{a} < N$. Then $N = 2^{a} + (N - 2^{a})$. Using the above argument, we can write $2^{a}$ as the sum of $k$ powers of $2$ for any $1 < k < 2^{a}$. Since $2^{a} > N / 2$, we have $N$ can be expressed as a sum of $k$ positive integers that are relatively prime to $N$ for any $2 \leq k \leq N / 2$.

Since $N / 2 + 1 > \log_{2} N$ for all $N \geq 3$, we conclude that all $N > 3$ odd are special.