2009 AMC 12A Problems/Problem 18

The following problem is from both the 2009 AMC 12A #18 and 2009 AMC 10A #25, so both problems redirect to this page.

Problem

For $k > 0$ , let $I_k = 10\ldots 064$ , where there are $k$ zeros between the $1$ and the $6$ . Let $N(k)$ be the number of factors of $2$ in the prime factorization of $I_k$ . What is the maximum value of $N(k)$ ?

For $k\in\{1,2,3\}$ we have $I_k = 2^{k+2} \left( 5^{k+2} + 2^{4-k} \right)$ . The first value in the parentheses is odd, the second one is even, hence their sum is odd and we have $N(k)=k+2\leq 5$ .

This leaves the case $k=4$ . We have $I_4 = 2^6 \left( 5^6 + 1 \right)$ . The value $5^6 + 1$ is obviously even. And as $5\equiv 1 \pmod 4$ , we have $5^6 \equiv 1 \pmod 4$ , and therefore $5^6 + 1 \equiv 2 \pmod 4$ . Hence the largest power of $2$ that divides $5^6+1$ is $2^1$ , and this gives us the desired maximum of the function $N$ : $N(4) = \boxed{7}$ .