Maths Olympiad Prep

Library / /175 of 520

Number theory Difficulty 6.7 National olympiad Find the answer

A positive integer nn is defined as a stepstool number\textit{stepstool number} if nn has one less positive divisor than n+1n + 1. For example, 33 is a stepstool number, as 33 has 22 divisors and 44 has 2+1=32 + 1 = 3 divisors. Find the sum of all stepstool numbers less than 300300.

[i]Proposed by [b]Th3Numb3rThr33[/b][/i]

A number or a short expression. Spacing and $ signs are ignored.

Solution

1. Understanding the Problem:
We need to find all positive integers n n less than 300 such that n n has one less positive divisor than n+1 n + 1 . This means:
d(n)=d(n+1)1 d(n) = d(n+1) - 1
where d(x) d(x) denotes the number of positive divisors of x x .

2. Analyzing the Divisors:
For d(n) d(n) to be one less than d(n+1) d(n+1) , either n n or n+1 n+1 must be a perfect square. This is because a perfect square has an odd number of divisors, while a non-perfect square has an even number of divisors.

3. **Case 1: n n is a perfect square:**
Let n=k2 n = k^2 . Then n+1=k2+1 n+1 = k^2 + 1 .
- d(n)=d(k2)=3 d(n) = d(k^2) = 3 (since k2 k^2 has an odd number of divisors).
- d(n+1) d(n+1) must be 4 (since d(n+1)=d(n)+1 d(n+1) = d(n) + 1 ).

4. **Case 2: n+1 n+1 is a perfect square:**
Let n+1=m2 n+1 = m^2 . Then n=m21 n = m^2 - 1 .
- d(n+1)=d(m2)=3 d(n+1) = d(m^2) = 3 (since m2 m^2 has an odd number of divisors).
- d(n) d(n) must be 2 (since d(n)=d(n+1)1 d(n) = d(n+1) - 1 ).

5. Finding Stepstool Numbers:
We need to find all n n such that either n n or n+1 n+1 is a perfect square and n<300 n < 300 .

- For n=k2 n = k^2 :
k2<300    k<30017.32    k17 k^2 < 300 \implies k < \sqrt{300} \approx 17.32 \implies k \leq 17
So, k k ranges from 1 to 17. The corresponding n n values are:
12,22,32,,172=1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289 1^2, 2^2, 3^2, \ldots, 17^2 = 1, 4, 9, 16, 25, 36, 49, 64, 81, 100, 121, 144, 169, 196, 225, 256, 289

- For n+1=m2 n+1 = m^2 :
m21<300    m2<301    m<30117.37    m17 m^2 - 1 < 300 \implies m^2 < 301 \implies m < \sqrt{301} \approx 17.37 \implies m \leq 17
So, m m ranges from 1 to 17. The corresponding n n values are:
121,221,321,,1721=0,3,8,15,24,35,48,63,80,99,120,143,168,195,224,255,288 1^2 - 1, 2^2 - 1, 3^2 - 1, \ldots, 17^2 - 1 = 0, 3, 8, 15, 24, 35, 48, 63, 80, 99, 120, 143, 168, 195, 224, 255, 288

6. Combining and Summing Unique Stepstool Numbers:
Combining the two sets of n n values and removing duplicates, we get:
{0,1,3,4,8,9,15,16,24,25,35,36,48,49,63,64,80,81,99,100,120,121,143,144,168,169,195,196,224,225,255,256,288,289} \{0, 1, 3, 4, 8, 9, 15, 16, 24, 25, 35, 36, 48, 49, 63, 64, 80, 81, 99, 100, 120, 121, 143, 144, 168, 169, 195, 196, 224, 225, 255, 256, 288, 289\}
Summing these values:
0+1+3+4+8+9+15+16+24+25+35+36+48+49+63+64+80+81+99+100+120+121+143+144+168+169+195+196+224+225+255+256+288+289=687 0 + 1 + 3 + 4 + 8 + 9 + 15 + 16 + 24 + 25 + 35 + 36 + 48 + 49 + 63 + 64 + 80 + 81 + 99 + 100 + 120 + 121 + 143 + 144 + 168 + 169 + 195 + 196 + 224 + 225 + 255 + 256 + 288 + 289 = 687

The final answer is 687\boxed{687}.

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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.