Baltic Way 2023 Shortlist

For both versions of the problem, we begin with a lemma which classifies the good numbers in a more compact way.

Note that the largest integer that can be written as a sum of distinct divisors of $n$ is the sum of all its positive divisors, denoted by $\sigma (n)$. Hence, a positive integer $n$ is good iff all the integers in the interval $[0,\sigma (n)]$ are $n$-expressible.

Lemma: Classification of Good Integers Let the prime factorization of $n$ be $n=\prod p_i^{a_i}$, where $a_i$ is positive and the primes are sorted in ascending order, i.e. $i>j⟹p_i>p_j$. Then $n$ is good iff for all $i\ge 0$, $p_{i+1}\le 1+\sigma ({\prod }_{j\le i}{p}_j^{a_j})$.

Proof. The only if direction may be seen from the fact that if we only consider sums of divisors containing the $i$ first prime divisors of $n$, $i\ge 0$, then we can only create sums which are strictly smaller than $1+\sigma ({\prod }_{j\le i}{p}_j^{a_j})$ and if we use any divisor containing a prime divisor not among the $i$ first, then the smallest possible sum equals $p_{i+1}$, which yields the desired inequality.

To see that these inequalities are in fact sufficient, let $n_i={\prod }_{j\le i}{p}_j^{a_j}$, where $n_0=0$, and let us prove by induction that, for all $i$, $n_i$ is a good number.

The base case $n_0=1$ is easily seen to be good, hence for the induction step, we are given that $n_i$ is good and that $p_{i+1}\le 1+\sigma (n_i)$, and want to prove that $n_{i+1}$ is good, as well.

The sums of distinct positive divisors of $n_{i+1}$ may be broken up into $a_{i+1}+1$ different separate sums, where each divisor $d$ is put into the group corresponding to how many times the prime $p_{i+1}$ divides the divisor $d$. Moreover, if we consider any sum on the form $$d=\sum _{j=0}^{a_{i+1}}{d}_j{p}_{i+1}^j,$$ where $d_j$ can be written as a sum of distinct positive divisors of $n_i$, i.e. $d_j\in [0,\sigma (n_i)]$, then $d$ may be written as a sum of distinct divisors of $n_{i+1}$, since we can split $d_j$ into its corresponding sum of distinct divisors of $n_i$, none of them being divisible by $p_{i+1}$.

this is essentially writing a number in base $p_{i+1}$, except that we may have more coefficients available than those in the interval $[0,p_{i+1}-1]$. However, the inequality $\sigma (n_i)\ge p_{i+1}-1$ guarantees that we have at least these available.

Hence, to express any number $d$ in the interval $[0,\sigma (n_{i+1})]$, we will start by determining the coefficient $d_{a_{i+1}}$, which we will put equal to $$\lfloor \frac{d}{p_{i+1}}\rfloor .$$ Observe that since $\gcd (p_{i+1}^{a_{i+1}},n_i)=1$ and $\sigma$ is multiplicative, $$\sigma (n_{i+1})=\sigma (n_i)\cdot (1+p_{i+1}+\cdots +p_{i+1}^{a_{i+1}}).$$ Hence, $d_{a_{i+1}}\le \sigma (n_i)$ and $$\begin{array}{rl}d-d_{a_{i+1}}{p}_{i+1}^{a_{i+1}}& \le p_{i+1}^{a_{i+1}}-1=(p_{i+1}-1)(1+p_{i+1}+\cdots +p_{i+1}^{a_{i+1}-1})\\ & \le \sigma (n_i)(1+p_{i+1}+\cdots +p_{i+1}^{a_{i+1}-1}).\end{array}$$ Thus, the remaining number to be expressed lies in the interval $[0,\sigma (\frac{n_{i+1}}{p_{i+1}})]$, which we know is expressible as as sum of the form $$d^{\prime }=d-d_{a_{i+1}}{p}_{i+1}^{a_{i+1}}=\sum _{j=0}^{j=a_{i+1}-1}{d}_j{p}_{i+1}^j$$ by induction, since $d^{\prime }\in [0,\sigma (\frac{n_{i+1}}{p_{i+1}})]$.

Thus, any number in the interval $[0,\sigma (n_{i+1})]$ is $n_{i+1}$ expressible, meaning that $n_{i+1}$ is good. $\square$

The rest of the solution is dedicated to utilizing the Classification of Good Integers, to determine whether various integers are good.

For which $n$ is $n!$ good: We will prove that, for all positive integers $n,n!$ is good. Let us write $n!=\prod p_i^{a_i}$. By virtue of being a factorial, the $p_i$-s in this product will be the first $I$ primes for some $I$. Indeed, if $p<q$ are primes and $q|n!$ then $q|m$ for some $m\le n$, which implies $q\le n,p\le n$ and $p|(1\cdot 2\cdot \cdots \cdot p-1\cdot p+1\cdot \cdots \cdot n)\cdot p=n!$.

To prove that $n!$ is good, we thus need to verify the inequalities $p_{i+1}\le \sigma (n_i)+1=(1+\cdots +p_1^{a_1})\cdots (1+\cdots +p_i^{a_i})+1$. Note that the product $(1+\cdots +p_1^{a_1})\cdots (1+\cdots +p_i^{a_i})$ is at least $p_1^{\dots }{p}_i$. Thus, it is sufficient to verify that the next prime $p_{i+1}$ is in the interval $[p_i+1,1+p_1\dots \dots p_i]$. However, this can be done by the classic observation that $\gcd (1+p_1\dots \dots p_i,p_j)=1$ for all $1\le j\le i$,

Therefore, $n!$ is good for all positive integers $n$.

For which $n$ is $n^n$ good: To prove the if direction, we resort to the lemma Classification of Good Integers, and write $n^n$ in the form $n^n=\prod p_i^{a_i}$. Observe that when $n$ is even, $p_1=2$.

We need to prove that, for all $i\ge 0$, the inequality $p_{i+1}\le 1+\sigma (n_i)$ holds. For $i=0$, this is satisfied since $p_1=2$, and for $i\ge 1$, we have $1+\sigma (n_i)\ge 1+\sigma (n_1)=2^{a_i+1}\ge 2^{n+1}$, since $n|a_i$.

Therefore, $p_{i+1}|n⟹p_{i+1}\le n\le 2^{n+1}\le 1+\sigma (n_i)$, meaning that $n^n$ is indeed good for even $n$.