Maths Olympiad Prep

Library / /9 of 16

Number theory Difficulty 6.3 National olympiad Prove it Argentina

Ana writes lists of numbers, according to the following rules. The first number of the list must be an integer greater than 1. To compute the next number, Ana finds the least prime number that divides the last written number, and divides this number by that prime. Ana repeats this procedure many times until she writes the number 1.

For example, if the first number on the list is 864864, since the least prime that divides 864864 is 22, the next number on the list is 864÷2=432864 \div 2 = 432. The complete list will be: 864864, 432432, 216216, 108108, 5454, 2727, 99, 33, 11.

Instead, if the first number of the list is 20222022, the list will be 20222022, 10111011, 337337, 11. If on the list that begins with number NN there is at least one perfect cube greater than 11, we say that NN is cuboso. For example, 864864 is cuboso, because the number 216=63216 = 6^3 is on the list. Instead, 20222022 is not cuboso, because none of the numbers 20222022, 10111011, 337337, 11 is a perfect cube greater than 11.

Determine how many positive integers less than 20222022 are cuboso.

Solution

We claim that, if the exponent of the greatest prime divisor pp of nn is greater than or equal to 33, then nn is cuboso. In fact, at some step of the process, we will get p3p^3 on the board, after we divide by every smaller prime divisor and the remaining factors pp.

Conversely, if a number is cuboso, then the exponent of its greatest prime divisor is at least 33. In order to see that, first note that every number written on the list is always divisible by the greatest prime divisor of the first one. Also, at some step of the process we will get a perfect cube and, in particular, each of its prime divisors has an exponent greater than or equal to 33.

It remains to count how many numbers n<2022n < 2022 have its greatest prime divisor with an exponent at least 33. We split the problem into cases according to the value of this prime pp.

**Case p13p \ge 13:** We would have n133=2197>2022n \ge 13^3 = 2197 > 2022, which is not possible.

**Case p=11p = 11:** We have n=113m=1331mn = 11^3 m = 1331m, the only solution is m=1m = 1.

**Case p=7p = 7:** We have n=73mn = 7^3 m and so m<6m < 6. There are 55 possibilities.

**Case p=5p = 5:** We have n=53mn = 5^3 m, so m<17m < 17 and mm must have only 22, 33 or 55 as prime factors. Every integer between 11 and 1616 except for 77, 1111, 1313, 1414 works, so there are 1212 possibilities.

**Case p=3p = 3:** We have n=33mn = 3^3 m and so m<75m < 75. The only possible prime factors of mm are 22 or 33. We split into cases according to the exponent xx of 33 in the prime factorization of mm.

* If x=3x = 3, m=27m = 27, 5454
* If x=2x = 2, m=9m = 9, 1818, 3636, 7272
* If x=1x = 1, m=3m = 3, 66, 1212, 2424, 4848
* If x=0x = 0, m=1m = 1, 22, 44, 88, 1616, 3232, 6464

So there are 2+4+5+7=182 + 4 + 5 + 7 = 18 possibilities.

**Case p=2p = 2:** Here n=23mn = 2^3 m and mm must have only 22 as prime factor. The possibilities for nn are 88: all the powers of 22 from 232^3 to 2102^{10}.

In conclusion, there exist 1+5+12+18+8=441 + 5 + 12 + 18 + 8 = 44 cuboso numbers that are strictly less than 20222022.

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.