Maths Olympiad Prep

Library / /26 of 27

Number theory Difficulty 7.5 National olympiad, round 2 Prove it North Macedonia

Let d(n)d(n) denote the number of positive divisors of nn. For positive integer nn we define f(n)f(n) as
f(n)=d(k1)+d(k2)+d(k3)++d(km), f(n) = d(k_1) + d(k_2) + d(k_3) + \dots + d(k_m),
where 1=k1<k2<<km=n1 = k_1 < k_2 < \dots < k_m = n are all divisors of the number nn. We call an integer n>1n > 1 almost perfect if f(n)=nf(n) = n. Find all almost perfect numbers.

Solutions — 2

Solution 1

Alternative way to define f(n)f(n) is
f(n)=kn,k1d(k). f(n) = \sum_{k|n, k \ge 1} d(k).
Let n=p1α1p2α2prαrn = p_1^{\alpha_1} p_2^{\alpha_2} \dots p_r^{\alpha_r} be the prime factorization of nn. We have d(n)=i=1r(αi+1)d(n) = \prod_{i=1}^r (\alpha_i + 1).
We prove the function ff is multiplicative, in particular, given coprime n,mn, m we have f(mn)=f(m)f(n)f(mn) = f(m)f(n).
Using n,mn, m are coprime for the second inequality and the fact that function dd is multiplicative we get:
f(mn)=kmd(k)=k1n,k2md(k1k2)=k1nd(k1)d(k2)=(k1nd(k1))(k2md(k2))=f(n)f(m). f(mn) = \sum_{k|m} d(k) = \sum_{k_1|n, k_2|m} d(k_1k_2) = \sum_{k_1|n} d(k_1)d(k_2) = \left(\sum_{k_1|n} d(k_1)\right)\left(\sum_{k_2|m} d(k_2)\right) = f(n)f(m).
If r=1r=1 we have n=p1α1n = p_1^{\alpha_1}. We note that divisors of nn are 1,p1,p12,,p1α11, p_1, p_1^2, \dots, p_1^{\alpha_1}, so
f(n)=i=0α1(i+1)=(α1+1)(α1+2)2. f(n) = \sum_{i=0}^{\alpha_1} (i+1) = \frac{(\alpha_1+1)(\alpha_1+2)}{2}.
Combining this with the multiplicativity result for ff we deduce f(n)=i=1n(αi+1)(αi+2)2f(n) = \prod_{i=1}^n \frac{(\alpha_i+1)(\alpha_i+2)}{2}.
We now prove that for primes p5p \ge 5 and p=3p=3 provided a3a \ge 3 we have f(pa)=(a+1)(a+2)2<23paf(p^a) = \frac{(a+1)(a+2)}{2} < \frac{2}{3}p^a by induction on aa. As a basis 3<2p33 < \frac{2p}{3} for p5p \ge 5 and 6<23336 < \frac{2}{3} \cdot 3^3. For the step it is enough to notice that a+3a+12<p\frac{a+3}{a+1} \le 2 < p in both cases.
Similarly we can prove for p=2p=2 that f(pa)<paf(p^a) < p^a provided a4a \ge 4. By explicitly checking the remaining cases p=2p=2 and a=1,2,3a=1,2,3 and p=3,a=1,2p=3, a=1,2 we conclude f(pa)23paf(p^a) \le \frac{2}{3}p^a for all p,ap, a and f(pa)paf(p^a) \le p^a for all p3p \ge 3 and p=2,a4p=2, a \ge 4.
Assuming f(n)=nf(n)=n we would have i=1kf(piαi)pαi=1\prod_{i=1}^k \frac{f(p_i^{\alpha_i})}{p^{\alpha_i}} = 1 so the above considerations imply that only possible prime divisors are 2,3.
If k=1k=1 the only possible solution is n=3n=3. If k=2k=2 we have p1=2,p2=3p_1=2, p_2=3 and 1a121 \le a_1 \le 2 and 1a221 \le a_2 \le 2 which give 4 cases to check giving the other 2 solutions n=18,36n=18,36.

Solution 2

We hereby present one similar but different solution which does not use a lot of properties of the function ff.
Firstly, we will prove the following lemma:
Lemma. For any positive integer n>1n>1 and prime pp we have
f(pn)3f(n). f(pn) \le 3f(n).
The equality holds if and only if GCD(p,n)=1GCD(p,n)=1.
Proof. For every integer mm we have that the set of divisors of the number pmpm is the union of the following two sets:
* set of divisors of mm
* set of divisors of mm multiplied by pp.
Also those two mentioned sets are disjoint if and only if GCD(p,m)=1GCD(p,m)=1 (if we have that p,mp,m are disjoint, then it is obvious that none of the divisors of pmpm are in both sets; if they are not coprime, then the number pp belongs to both sets).
This is why we have d(pn)2d(m)d(pn) \le 2d(m) and
f(pn)=kpnd(k)knd(k)+knd(pk)f(n)+kn2d(k)=3f(n). f(pn) = \sum_{k|pn} d(k) \le \sum_{k|n} d(k) + \sum_{k|n} d(pk) \le f(n) + \sum_{k|n} 2d(k) = 3f(n).
In both inequalities equality holds if and only if sets from before are disjoint, i.e. when GCD(p,n)=1GCD(p,n)=1.

Also, we simply see that f(2k)=d(1)+d(2)+...+d(2k)=1+2+3+...+(k+1)=(k+1)(k+2)2f(2^k) = d(1) + d(2) + ... + d(2^k) = 1 + 2 + 3 + ... + (k+1) = \frac{(k+1)(k+2)}{2}.
Notice that if for some positive integer nn we have f(n)<nf(n) < n, then for every p3p \ge 3 we have f(pn)3f(n)pf(n)<pnf(pn) \le 3f(n) \le pf(n) < pn. Consequently, if f(n)<nf(n) < n, then for every odd mm we have f(mn)<mnf(mn) < mn.
Because of this, we will introduce new terms. Number nn is *nice multiple* of mm if mnm|n and m/nm/n is odd number. Analogously, we define *nice divisor*. Our statement from above is: if for some nn we have f(n)<nf(n) < n, then neither of its nice multiplies is almost perfect number.
Our strategy will be the following: check the cases of the small numbers and see ratio of numbers nn and f(n)f(n). When we have that n>f(n)n > f(n), conclude that there are not almost perfect numbers among their nice multiplies. With formula for f(2k)f(2^k) conclude that for sufficiently big kk (when f(2k)<2kf(2^k) < 2^k this is enough to conclude that there are no more almost perfect numbers.
By induction, it is simple to prove that f(2k)<2kf(2^k) < 2^k for k4k \ge 4. Thus, there are no almost perfect numbers of the form 2km2^k \cdot m, where k4k \ge 4 and mm is odd, since they all have 2k2^k as their nice divisor. We only have to check the numbers of the form 2km2^k \cdot m, where k3k \le 3 and mm is odd.
**First case: k=0k=0**
For any odd prime pp we have f(p)=d(1)+d(p)=3pf(p) = d(1) + d(p) = 3 \le p. From that we see that n=3n=3 is solution. Moreover, we do not have any more solutions: if some odd number has a prime divisor different from 3, since f(p)<pf(p) < p this number can not be almost perfect number; if it is a power of 3 bigger than 3, since f(9)<3f(3)=9f(9) < 3f(3) = 9, there are no more solutions as well (9 is nice divisor of every power of 3 bigger that 3).
**Second case: k=1k=1**.
For any odd prime we have f(2p)=3f(2)=9f(2p) = 3f(2) = 9. If p>5p > 5 then we have 2p>f(2p)2p > f(2p), so for all almost perfect numbers of the form 21m2^1m number mm has to have prime divisors 3 and/or 5.
We directly see that neither 6 or 10 is almost perfect. SO, in this case, almost perfect number has to be a nice divisor of the form 29,2152 \cdot 9, 2 \cdot 15 or 2252 \cdot 25. For n=18n=18 we have another solution, in other two cases we have inequality f(n)<nf(n) < n. If we want to seek new solution in this case, since they cannot be nice multiplies of 30 and 50, the only possibility is that almost perfect number has nice divisor 2272 \cdot 27. But we have (equality case in lemma) that f(227)<3f(29)=227f(2 \cdot 27) < 3f(2 \cdot 9) = 2 \cdot 27. So, there are no more solutions in this case.
**Third case: k=2k=2**
For any odd prime we have f(4p)=3f(4)=18f(4p) = 3f(4) = 18. If p>5p > 5 then we have 4p>f(4p)4p > f(4p), so for all almost perfect numbers of the form 21m2^1m number mm has to have prime divisors 3 and/or 5.
We directly see that neither 12 or 20 is almost perfect. So, in this case, almost perfect number has to have a nice divisor of the form 49,4154 \cdot 9, 4 \cdot 15 or 4254 \cdot 25. For n=36n=36 we have another solution, in other two cases we have inequality f(n)<nf(n) < n. If we want to seek new solution in this case, since they cannot be nice multiplies of 60 and 100, the only possibility is that almost perfect number has nice divisor 4274 \cdot 27. But we have (equality case in lemma), that f(427)<3f(49)=427f(4 \cdot 27)<3f(4 \cdot 9)=4 \cdot 27.
So, there are no more solutions in this case.
Fourts case: k=3k=3
For any odd prime we have f(8p)=3f(8)=30f(8p)=3f(8)=30. Similarly to other cases, we only observe candidates of the form 83l8\cdot 3^l. Number 8\cdot 3 is not almost perfect, all other candidates have nice divisor 8\cdot 9. But, we have f(72)=60<72f(72)=60<72. As we always concluded, we do not have any new solutions.
So all almost perfect numbers are 3,18,36.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.