Problem 1407

Solution:

Suppose $n \in \mathbb{N}$ is faithful. Let $k \in \mathbb{N}$ and consider $k n$. Since $n = a + b + c$, with $a < b < c$, $a \mid b$ and $b \mid c$, we see that $k n = k a + k b + k c$ which shows that $k n$ is faithful.

Let $p > 5$ be a prime. Then $p$ is odd and $p = (p - 3) + 2 + 1$ shows that $p$ is faithful. If $n \in \mathbb{N}$ contains a prime factor $p > 5$, then the above observation shows that $n$ is faithful. This shows that a number which is not faithful must be of the form $2^{\alpha} 3^{\beta} 5^{\gamma}$. We also observe that $2^{4} = 16 = 12 + 3 + 1$, $3^{2} = 9 = 6 + 2 + 1$ and $5^{2} = 25 = 22 + 2 + 1$, so that $2^{4}$, $3^{2}$ and $5^{2}$ are faithful. Hence $n \in \mathbb{N}$ is also faithful if it contains a factor of the form $2^{\alpha}$ where $\alpha \geq 4$; a factor of the form $3^{\beta}$ where $\beta \geq 2$; or a factor of the form $5^{\gamma}$ where $\gamma \geq 2$. Thus the numbers which are not faithful are of the form $2^{\alpha} 3^{\beta} 5^{\gamma}$, where $\alpha \leq 3$, $\beta \leq 1$ and $\gamma \leq 1$. We may enumerate all such numbers:
$$1, 2, 3, 4, 5, 6, 8, 10, 12, 15, 20, 24, 30, 40, 60, 120$$
Among these $120 = 112 + 7 + 1$, $60 = 48 + 8 + 4$, $40 = 36 + 3 + 1$, $30 = 18 + 9 + 3$, $20 = 12 + 6 + 2$, $15 = 12 + 2 + 1$, and $10 = 6 + 3 + 1$. It is easy to check that the other numbers cannot be written in the required form. Hence the only numbers which are not faithful are
$$1, 2, 3, 4, 5, 6, 8, 12, 24$$
Their sum is $65$.

Solution:

If $n = a + b + c$ with $a < b < c$ is faithful, we see that $a \geq 1$, $b \geq 2$ and $c \geq 4$. Hence $n \geq 7$. Thus $1, 2, 3, 4, 5, 6$ are not faithful. As observed earlier, $k n$ is faithful whenever $n$ is. We also notice that for odd $n \geq 7$, we can write $n = 1 + 2 + (n - 3)$ so that all odd $n \geq 7$ are faithful. Consider $2 n, 4 n, 8 n$, where $n \geq 7$ is odd. By observation, they are all faithful. Let us list a few of them:
$$\begin{aligned} 2 n & : \quad 14, 18, 22, 26, 30, 34, 38, 42, 46, 50, 54, 58, 62, \ldots \\ 4 n & : \quad 28, 36, 44, 52, 60, 68, \ldots \\ 8 n & : \quad 56, 72, \ldots \end{aligned}$$
We observe that $16 = 12 + 3 + 1$ and hence it is faithful. Thus all multiples of $16$ are also faithful. Thus we see that $16, 32, 48, 64, \ldots$ are faithful. Any even number which is not a multiple of $16$ must be either an odd multiple of $2$, or that of $4$, or that of $8$. Hence, the only numbers not covered by this process are $8, 10, 12, 20, 24, 40$. Of these, we see that
$$10 = 1 + 3 + 6, \quad 20 = 2 \times 10, \quad 40 = 4 \times 10$$
so that $10, 20, 40$ are faithful. Thus the only numbers which are not faithful are
$$1, 2, 3, 4, 5, 6, 8, 12, 24$$
Their sum is $65$.