Maths Olympiad Prep

Library / /386 of 520

Number theory Difficulty 7.2 National olympiad, round 2 Find the answer

The number 11 is special. The number 22 is special because it is relatively prime to 11. The number 33 is not special because it is not relatively prime to the sum of the special numbers less than it, 1+21 + 2. The number 44 is special because it is relatively prime to the sum of the special numbers less than it. So, a number bigger than 11 is special only if it is relatively prime to the sum of the special numbers less than it. Find the twentieth special number.

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

Solution

To find the 20th special number, we need to follow the given rule: a number n n is special if it is relatively prime to the sum of all special numbers less than n n . We will list out the special numbers and their sums step-by-step.

1. 1 1 is special by definition.
- Sum of special numbers: 1 1

2. 2 2 is special because gcd(2,1)=1 \gcd(2, 1) = 1 .
- Sum of special numbers: 1+2=3 1 + 2 = 3

3. 3 3 is not special because gcd(3,3)=3 \gcd(3, 3) = 3 .

4. 4 4 is special because gcd(4,3)=1 \gcd(4, 3) = 1 .
- Sum of special numbers: 1+2+4=7 1 + 2 + 4 = 7

5. 5 5 is special because gcd(5,7)=1 \gcd(5, 7) = 1 .
- Sum of special numbers: 1+2+4+5=12 1 + 2 + 4 + 5 = 12

6. 6 6 is not special because gcd(6,12)=6 \gcd(6, 12) = 6 .

7. 7 7 is special because gcd(7,12)=1 \gcd(7, 12) = 1 .
- Sum of special numbers: 1+2+4+5+7=19 1 + 2 + 4 + 5 + 7 = 19

8. 8 8 is special because gcd(8,19)=1 \gcd(8, 19) = 1 .
- Sum of special numbers: 1+2+4+5+7+8=27 1 + 2 + 4 + 5 + 7 + 8 = 27

9. 9 9 is not special because gcd(9,27)=9 \gcd(9, 27) = 9 .

10. 10 10 is special because gcd(10,27)=1 \gcd(10, 27) = 1 .
- Sum of special numbers: 1+2+4+5+7+8+10=37 1 + 2 + 4 + 5 + 7 + 8 + 10 = 37

11. 11 11 is special because gcd(11,37)=1 \gcd(11, 37) = 1 .
- Sum of special numbers: 1+2+4+5+7+8+10+11=48 1 + 2 + 4 + 5 + 7 + 8 + 10 + 11 = 48

12. 12 12 is not special because gcd(12,48)=12 \gcd(12, 48) = 12 .

13. 13 13 is special because gcd(13,48)=1 \gcd(13, 48) = 1 .
- Sum of special numbers: 1+2+4+5+7+8+10+11+13=61 1 + 2 + 4 + 5 + 7 + 8 + 10 + 11 + 13 = 61

14. 14 14 is special because gcd(14,61)=1 \gcd(14, 61) = 1 .
- Sum of special numbers: 1+2+4+5+7+8+10+11+13+14=75 1 + 2 + 4 + 5 + 7 + 8 + 10 + 11 + 13 + 14 = 75

15. 15 15 is not special because gcd(15,75)=15 \gcd(15, 75) = 15 .

16. 16 16 is special because gcd(16,75)=1 \gcd(16, 75) = 1 .
- Sum of special numbers: 1+2+4+5+7+8+10+11+13+14+16=91 1 + 2 + 4 + 5 + 7 + 8 + 10 + 11 + 13 + 14 + 16 = 91

17. 17 17 is special because gcd(17,91)=1 \gcd(17, 91) = 1 .
- Sum of special numbers: 1+2+4+5+7+8+10+11+13+14+16+17=108 1 + 2 + 4 + 5 + 7 + 8 + 10 + 11 + 13 + 14 + 16 + 17 = 108

18. 18 18 is not special because gcd(18,108)=18 \gcd(18, 108) = 18 .

19. 19 19 is special because gcd(19,108)=1 \gcd(19, 108) = 1 .
- Sum of special numbers: 1+2+4+5+7+8+10+11+13+14+16+17+19=127 1 + 2 + 4 + 5 + 7 + 8 + 10 + 11 + 13 + 14 + 16 + 17 + 19 = 127

20. 20 20 is special because gcd(20,127)=1 \gcd(20, 127) = 1 .
- Sum of special numbers: 1+2+4+5+7+8+10+11+13+14+16+17+19+20=147 1 + 2 + 4 + 5 + 7 + 8 + 10 + 11 + 13 + 14 + 16 + 17 + 19 + 20 = 147

21. 21 21 is not special because gcd(21,147)=21 \gcd(21, 147) = 21 .

22. 22 22 is special because gcd(22,147)=1 \gcd(22, 147) = 1 .
- Sum of special numbers: 1+2+4+5+7+8+10+11+13+14+16+17+19+20+22=169 1 + 2 + 4 + 5 + 7 + 8 + 10 + 11 + 13 + 14 + 16 + 17 + 19 + 20 + 22 = 169

23. 23 23 is special because gcd(23,169)=1 \gcd(23, 169) = 1 .
- Sum of special numbers: 1+2+4+5+7+8+10+11+13+14+16+17+19+20+22+23=192 1 + 2 + 4 + 5 + 7 + 8 + 10 + 11 + 13 + 14 + 16 + 17 + 19 + 20 + 22 + 23 = 192

24. 24 24 is not special because gcd(24,192)=24 \gcd(24, 192) = 24 .

25. 25 25 is special because gcd(25,192)=1 \gcd(25, 192) = 1 .
- Sum of special numbers: 1+2+4+5+7+8+10+11+13+14+16+17+19+20+22+23+25=217 1 + 2 + 4 + 5 + 7 + 8 + 10 + 11 + 13 + 14 + 16 + 17 + 19 + 20 + 22 + 23 + 25 = 217

26. 26 26 is special because gcd(26,217)=1 \gcd(26, 217) = 1 .
- Sum of special numbers: 1+2+4+5+7+8+10+11+13+14+16+17+19+20+22+23+25+26=243 1 + 2 + 4 + 5 + 7 + 8 + 10 + 11 + 13 + 14 + 16 + 17 + 19 + 20 + 22 + 23 + 25 + 26 = 243

27. 27 27 is not special because gcd(27,243)=27 \gcd(27, 243) = 27 .

28. 28 28 is special because gcd(28,243)=1 \gcd(28, 243) = 1 .
- Sum of special numbers: 1+2+4+5+7+8+10+11+13+14+16+17+19+20+22+23+25+26+28=271 1 + 2 + 4 + 5 + 7 + 8 + 10 + 11 + 13 + 14 + 16 + 17 + 19 + 20 + 22 + 23 + 25 + 26 + 28 = 271

Thus, the 20th special number is 28 28 .

The final answer is 28\boxed{28}.

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.