Number theoryDifficulty 6.7National olympiadFind the answer
A positive integer n is defined as a stepstool number if n has one less positive divisor than n+1. For example, 3 is a stepstool number, as 3 has 2 divisors and 4 has 2+1=3 divisors. Find the sum of all stepstool numbers less than 300.
[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 less than 300 such that n has one less positive divisor than n+1. This means: d(n)=d(n+1)−1 where d(x) denotes the number of positive divisors of x.
2. Analyzing the Divisors: For d(n) to be one less than d(n+1), either n or 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 is a perfect square:** Let n=k2. Then n+1=k2+1. - d(n)=d(k2)=3 (since k2 has an odd number of divisors). - d(n+1) must be 4 (since d(n+1)=d(n)+1).
4. **Case 2: n+1 is a perfect square:** Let n+1=m2. Then n=m2−1. - d(n+1)=d(m2)=3 (since m2 has an odd number of divisors). - d(n) must be 2 (since d(n)=d(n+1)−1).
5. Finding Stepstool Numbers: We need to find all n such that either n or n+1 is a perfect square and n<300.
- For n=k2: k2<300⟹k<300≈17.32⟹k≤17 So, k ranges from 1 to 17. The corresponding n values are: 12,22,32,…,172=1,4,9,16,25,36,49,64,81,100,121,144,169,196,225,256,289
- For n+1=m2: m2−1<300⟹m2<301⟹m<301≈17.37⟹m≤17 So, m ranges from 1 to 17. The corresponding n values are: 12−1,22−1,32−1,…,172−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 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} 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
The final answer is 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.