Problem 2036

First solution
We shall firstly prove the following lemmas,

Lemma 1. If $x$ is interesting and $y < x$ then $xy$ is also interesting.
Proof. If $n < xy$, by division algorithm we have $n = yq + r$ where $q < x$, $r < y$. Now, we can write $q = \sum d_i$ and $r = \sum d'_i$ where $\{d_i\}$ and $\{d'_i\}$ are distinct divisors of $x$. Now $d_i y$, $d'_i$ are distinct divisors of $xy$ and $n = \sum d_i y + \sum d'_i$.

Lemma 2. For $i \in \mathbb{N}$, $2^i$ is an interesting number.
Proof. It is clear by writing $n < 2^i$ in the basis 2.

Let $P(x) = x^2 + x + 2022$. If $n$ is an interesting number and $n | P(x_0)$, then $n | P(r)$ where $r$ is the remainder of $x_0$ modulo $n$. If $n > 2022$,
$$P(r) \le (x-1)^2 + x - 1 + 2022 < x^2,$$
which implies that $P(r)$ is an interesting number. So, it is enough to find a sequence $n_i$ so that $2^i | P(n_i)$. To do this we use induction, assume that $2^i | P(n_i)$ then
$$P(n_i + k 2^i) = (n + k 2^i)^2 + n_i + k_i + 2022 \equiv P(n_i) + k 2^i \pmod{2^{i+1}}$$
So it is enough to set $k = -\frac{P(n_i)}{2^i}$.

Second solution
Here we provide a slightly different solution. Let $p_1 < p_2 < \dots < p_k$ be distinct prime numbers and let $\alpha_1, \dots, \alpha_k$ be non-negative integers. If $m = p_1^{\alpha_1} \dots p_t^{\alpha_t}$, $m$ is an interesting number if and only if $p_1 = 2$ and $p_j - 1 \le \sigma(p_1^{\alpha_1} \dots p_{j-1}^{\alpha_{j-1}})$ for $1 < j \le k$. Let $N_M$ be the total number of integers $n$ such that can be written in the form $\sum d$ where $d$ are distinct divisors of $M$. It is clear that $N_M \le \sigma(M)$. For a given set $S$ of integers $M$ define $S^*$ to be the subset of $S$ containing integers such that $\sigma(M) - N_M$ is minimal.

Let $M$ be an interesting number and $p$ be a prime number such that $\gcd(p, M) = 1$ then $M_1 = p^k M$ is interesting if and only if $p \le \sigma(M) + 1$.

The smallest divisor of $M_1$ not a divisor of $M$ is $p$. If $p > \sigma(M) + 1$ then $n = 1 + \sigma(M)$ defies the representation with respect to $M_1$. If $p \le \sigma(M) + 1$, we show by induction that $p^k \le \sigma(p^{k-1} M) + 1$. The base, i.e., $k=1$ is true. Using the induction hypothesis on $k$, we have
$$p^{k+1} \le p \sigma(p^{k-1} M) + p \le p \sigma(p^{k-1} M) + \sigma(M) + 1 = \sigma(p^k M) + 1.$$
This shows that $M_1 = p^k M$ is interesting. Considering the intervals from $r p^k$ to $r p^k + \sigma(p^{k-1} M)$, $r = 0, 1, \dots, \sigma(M)$. It follows that no integer in the range $1 \le n \le \sigma(M_1)$ is omitted from all these intervals. For the one hand, because $p^k \le \sigma(p^{k-1} M) + 1$ we have $(r+1) p^k \le r p^k + \sigma(p^{k-1} M) + 1$. Hence, intervals are overlapping or contiguous. On the other hand the intervals include $1$ and $p^k \sigma(M) + \sigma(p^{k-1} M) = \sigma(M_1)$. Thus, such $n$ can be written as
$$n = r p^k + s, \quad 0 \le r \le \sigma(M), \quad 0 \le s \le \sigma(p^{k-1} M).$$
Since $M$, $p^{k-1} M$ are interesting we can write $r = \Sigma d$ where $d$ are distinct divisors of $M$ and we can write $s = \Sigma D$ where $D$ are distinct divisors of $p^{k-1} M$. That is, $n = \Sigma d' + \Sigma D$. Where $d' = p^k d$ are distinct from $D$ because of involving $p^k$. While both $d'$, $D$ dividing $M_1$.

If $m$ is interesting and $1 \le n \le 1 + \sigma(m)$ then $mn$ is interesting. In part, $mn$ is interesting for all $1 \le n \le 2m$. Since $m-1$ is sum of divisors of $m$, we have $m + (m-1) \le \sigma(m)$.

Let $f(n) = n^2 + b n + c$ then $f(n + f(n)) = f(n) f(n + 1)$. Notice that $f(n+1) = f(n) + 2n + b + 1$ and $f(n) - 2n - b - 1 = n(n-2) + b(n-1) + c - 1 \ge 0$. If $n \ge 2$ is an integer with $f(n)$ an interesting number then $f(n + f(n))$ would also be interesting. Because, $f(n+1) \le 2 f(n)$.

Finally, we need to find at least one interesting number. Indeed, since $2024 = 8 \times 11 \times 23$, we find that $8$ and $8 \times 11$ are both interesting. Further, since $2 \times 8 \times 11 \ge 23$ it follows that $2024 = 8 \cdot 11 \cdot 23$ is also interesting. Now, letting $f(n) = n^2 + n + 2023$ take $a_1 = 1$ and $a_{i+1} = a_i + f(a_i)$, $i = 1, 2, \dots$ and according to the above facts, we are done. ■