Olympiad Maths Prep

Track / Stage 6 / 283 of 400 #1283 of 2000

Problem 1283

National olympiad, first round
Number theory Difficulty 6.5 Find the answer european_mathematical_cup

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(km),f(n) = d\left(k_1\right) + d\left(k_2\right)+ \cdots + d\left(k_m\right), where 1=k1<k2<<km=n1 = k_1 < k_2 < \cdots < k_m = n are all divisors of the number nn. We call an integer n>1n > 1 [i]almost perfect[/i] if f(n)=nf(n) = n. Find all almost perfect numbers.

Official solution

To find all almost perfect numbers, we first consider the function f(n) f(n) . For a given positive integer n n , we define f(n) f(n) as:

f(n)=d(k1)+d(k2)++d(km), f(n) = d(k_1) + d(k_2) + \cdots + d(k_m),

where 1=k1<k2<<km=n 1 = k_1 < k_2 < \cdots < k_m = n are all the divisors of the number n n . Here, d(k) d(k) denotes the number of positive divisors of k k .

An integer n>1 n > 1 is called almost perfect if f(n)=n f(n) = n .

We aim to identify all integers n n for which this condition holds.

### Step-by-step Analysis

For small values of n n , we calculate f(n) f(n) directly and check if it equals n n .

1. **n=1 n = 1 :**
- Divisors of 1: {1}\{1\}
- f(1)=d(1)=1 f(1) = d(1) = 1
- n=1 n = 1 is not valid as n>1 n > 1 .

2. **n=3 n = 3 :**
- Divisors of 3: {1,3}\{1, 3\}
- f(3)=d(1)+d(3)=1+2=3 f(3) = d(1) + d(3) = 1 + 2 = 3
- Thus, 3 3 is almost perfect.

3. **n=18 n = 18 :**
- Divisors of 18: {1,2,3,6,9,18}\{1, 2, 3, 6, 9, 18\}
- f(18)=d(1)+d(2)+d(3)+d(6)+d(9)+d(18)=1+2+2+4+3+6=18 f(18) = d(1) + d(2) + d(3) + d(6) + d(9) + d(18) = 1 + 2 + 2 + 4 + 3 + 6 = 18
- Thus, 18 18 is almost perfect.

4. **n=36 n = 36 :**
- Divisors of 36: {1,2,3,4,6,9,12,18,36}\{1, 2, 3, 4, 6, 9, 12, 18, 36\}
- f(36)=d(1)+d(2)+d(3)+d(4)+d(6)+d(9)+d(12)+d(18)+d(36) f(36) = d(1) + d(2) + d(3) + d(4) + d(6) + d(9) + d(12) + d(18) + d(36)
- f(36)=1+2+2+3+4+3+6+6+9=36\phantom{f(36)}= 1 + 2 + 2 + 3 + 4 + 3 + 6 + 6 + 9 = 36
- Thus, 36 36 is almost perfect.

### Conclusion

After manually checking these cases and realizing the specific structure of these numbers, we conclude that the set of almost perfect numbers is:

3,18,36 \boxed{3, 18, 36}

These solutions can be further supported by observing the structure of the divisors and the counting of divisors function, d(n) d(n) , which leads to equality with n n only in these specific cases.

Source: Omni-MATH, licensed Apache-2.0. Statement and solution reproduced as published; topic, difficulty and ordering added by this site.