Allow me to introduce you to Euler’s Totient function, phi(n). It is the number of numbers less than a number that don’t share any factors with that number. For instance, when n is 6, phi(n) is 2, because there are only 2 numbers less than 6 that are coprime with 6 (1 and 5).

There is a shortcut way of finding the totient function of a number: first list all of the prime factors of the number, then go through them one by one, if you see a prime factor for the first time, subtract 1 from it, but if it’s one you’ve already seen, leave it as is. Then multiply the (some now modified) factors back together. For example, the totient function of 24:

24 = 2x2x2x3, phi(24) = (1)x2x2x(2) = 8.

Now after that crash course it’s going to get even more complicated as we consider doing it in reverse. The inverse totient function lists all of the numbers n for which phi(n) equals a particular value. We have seen that phi(24)=8, but for what other values of n is phi(n)=8?

The full list is 15, 16, 20, 24 and 30. Only one of these numbers is odd (15). This is no accident, and brings us around (finally!) to the question I want to ask you.

To simplify things slightly, I ONLY want to consider cases where n is odd, and phi(n) is a power of 2, for example:

phi(1)=1, phi(3)=2, phi(5)=4, phi(15)=8, phi(17)=16, phi(51)=32, phi(85)=64, etc.

In each case there is exactly one odd value for which phi(n) is equal to a particular power of 2. However this pattern doesn’t last forever, and eventually we will find that some powers of 2 are not the totient function of ANY odd numbers.

What is the first such power of 2?