8. Find all monotonically increasing sequences $a_{1}, a_{2}, a_{3}, \ldots$ of natural numbers such that $i+j$ and $a_{i}+a_{j}$ have the same number of divisors for all $i, j \in \mathbb{N}$.
Solution: First, we show that the sequence is strictly monotonically increasing, then that it contains infinitely many fixed points. For a natural number $n$, let $d(n)$ be the number of positive divisors of $n$.

- Strictly monotonically increasing: Assume there are natural numbers $i < j$ such that $a_i \geq a_j$. Let $k$ be a natural number such that $i+k$ is prime. Then we have

$$
2 = d(i+k) = d(a_i + a_k) = d(a_{i+1} + a_k) = d(i+1+k)
$$

Since $i+k > 2$ and is prime, $i+1+k > 2$ and is even, hence not prime, and thus $d(i+1+k) > 2$, a contradiction. Alternative: Using strong induction and Bertrand's postulate, one can show that $a_i \equiv i \pmod{2}$ for all natural $i$, which also leads to strict monotonicity.

- Infinitely many fixed points: Let $p$ be a prime number, then we have

$$
p = d(2^{p-1}) = d(2^{p-2} + 2^{p-2}) = d(a_{2^{p-2}} + a_{2^{p-2}}) = d(2a_{2^{p-2}})
$$

Considering the prime factorization $2a_{2^{p-2}} = \prod_{i=1}^{r} p_i^{\alpha_i}$ with $\alpha_1, \ldots, \alpha_i > 0$, we have $p = \prod_{i=1}^{r}(1 + \alpha_i)$, which, due to $p$ being prime, leads to $r = 1$ and $\alpha_1 = p-1$. Since 2 is a divisor of $2a_{2^{p-2}}$, we also have $p_1 = 2$ and thus $2a_{2^{p-2}} = 2^{p-1} \Longrightarrow a_{2^{p-2}} = 2^{p-2}$.

- Conclusion: Due to strict monotonicity, we have $a_{i+d} \geq d + a_i$, in particular $a_i \geq i$, for all $i, d \in \mathbb{N}$. Assume there is an $i \in \mathbb{N}$ such that $a_i > i$. Then we choose a prime $p$ such that $2^{p-2} > i$, and we obtain

$$
2^{p-2} = a_{2^{p-2}} \geq 2^{p-2} - i + a_i > 2^{p-2}
$$

Contradiction. Therefore, $a_i = i$ for all natural $i$, and it is easy to see that this sequence satisfies the conditions.