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}+\dots +2^{a_i}.$$ Note that $(2^t,N)=1$ and $i<{\log }_{2}N+1$.

For any $i\le k<N-1$, suppose that $N$ can be expressed as a sum of $k$ powers of $2$, i.e. $N=2^{x_1}+\dots +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}+\dots +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\le k\le N/2$.

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