Maths Olympiad Prep

Library / /3 of 101

Number theory Difficulty 4.8 AIME Find the answer Estonia

Call a positive integer nn supereven, if its largest odd factor dd is less than nd\frac{n}{d}. How many positive integers less than 1000 are supereven?

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

Solutions — 2

Solution 1

Let nn be supereven and dd its greatest odd divisor. If nd\frac{n}{d} were divisible by some odd p>1p > 1, then pd>dpd > d would also be a factor of nn, contradiction. Thus nd\frac{n}{d} is a power of 2. Hence supereven numbers are exactly those that can be expressed as a product of a power of two and an odd number less than that power of two.
We will find the supereven numbers less than 1000 by their largest odd factors dd.

* If d=1d = 1, then the power of 2 can be one of 2, 4, 8, 16, 32, 64, 128, 256, 512. We obtain 9 supereven numbers.

* If d=3d = 3, then the power of 2 can be one of 4, 8, 16, 32, 64, 128, 256. We obtain 7 supereven numbers.

* If d=5d = 5 or d=7d = 7, then the power of 2 can be one of 8, 16, 32, 64, 128. We obtain 25=102 \cdot 5 = 10 supereven numbers.

* If dd is one of the numbers 9, 11, 13, 15, then the power of 2 can be one of 16, 32, 64. We obtain 43=124 \cdot 3 = 12 supereven numbers.

* If dd is one of the numbers 17, 19, 21, 23, 25, 27, 29, 31, then the power of 2 can be only 32. We obtain 8 supereven numbers.

Thus there are 9+7+10+12+8=469 + 7 + 10 + 12 + 8 = 46 supereven numbers less than 1000.

Solution 2

Like in Solution 1, we will show that supereven numbers are exactly those that can be expressed as a product of a power of two and an odd number less than that power of 2. We will call this power of 2 the *even part* of a supereven integer. As every other integer is odd, there are 2k2=2k1\frac{2^k}{2} = 2^{k-1} odd positive integers less than 2k2^k. The exponents k=1,2,3,4,5k = 1, 2, 3, 4, 5 thus yield 1, 2, 4, 8, 16 supereven integers with an even part of 2k2^k. Of those, the greatest is 25(251)=992<10002^5 \cdot (2^5 - 1) = 992 < 1000, so all of them are less than 1000. For k=6,7,8,9k = 6, 7, 8, 9, the greatest odd factor keeping the product under 1000 is 15, 7, 3, 1 respectively, yielding 8+4+2+1=158 + 4 + 2 + 1 = 15 more supereven numbers less than 1000. Thus the total number of supereven integers less than 1000 is 1+2+4+8+16+15=461 + 2 + 4 + 8 + 16 + 15 = 46.

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.