Maths Olympiad Prep

Library / /581 of 740

Number theory Difficulty 5.3 AIME, harder Prove it United States

Problem:
Find the largest integer less than 20122012 all of whose divisors have at most two 11's in their binary representations.

Solution

Solution:
Call a number good if all of its positive divisors have at most two 11's in their binary representations. Then, if pp is an odd prime divisor of a good number, pp must be of the form 2k+12^{k}+1. The only such primes less than 20122012 are 3,5,173, 5, 17, and 257257, so the only possible prime divisors of nn are 2,3,5,172, 3, 5, 17, and 257257.

Next, note that since (2i+1)(2j+1)=2i+j+2i+2j+1(2^{i}+1)(2^{j}+1) = 2^{i+j} + 2^{i} + 2^{j} + 1, if either ii or jj is greater than 11, then there will be at least 33 11's in the binary representation of (2i+1)(2j+1)(2^{i}+1)(2^{j}+1), so (2i+1)(2j+1)(2^{i}+1)(2^{j}+1) cannot divide a good number. On the other hand, if i=j=1i = j = 1, then (21+1)(21+1)=9=23+1(2^{1}+1)(2^{1}+1) = 9 = 2^{3}+1, so 99 is a good number and can divide a good number. Finally, note that since multiplication by 22 in binary just appends additional 00's, if nn is a good number, then 2n2n is also a good number.

It therefore follows that any good number less than 20122012 must be of the form c2kc \cdot 2^{k}, where cc belongs to {1,3,5,9,17,257}\{1, 3, 5, 9, 17, 257\} (and moreover, all such numbers are good). It is then straightforward to check that the largest such number is 1536=3291536 = 3 \cdot 2^{9}.

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 reproduced verbatim; metadata (topic, difficulty) added by this project.