Library / /23 of 63

, 2026

Number theory Difficulty 2.1 Junior Prove it Canada

List $P$ contains all positive integers from $1$ to $2^{53}$ , inclusive. How many numbers in list $P$ can be written as $2^k$ where $k$ is a positive integer? Since $4=2^2$ , every power of $4$ can be written as a power of $2$ . For example, $4^3$ can be written as $4^3=\left(2^2\right)^3=2^{2\times 3}=2^6$ . In general, $\$4^n=\left(2^2\right)^n=2^{2\times n}=2^{2n}$ $. How many numbers in list$ P $can be written as$ $4^\ell$ $where$ $\ell$ is a positive integer? Determine how many numbers in list

Figure for this problem

Figure for this problem P $can be written as$ 4^r $where$ r is a positive integer, but cannot be written as

Figure for this problem

Figure for this problem 8^t $where$ t$ is a positive integer.

Solution

List $P$ contains all positive integers from $1$ to $2^{53}$ inclusive, and so $P$ contains each integer of the form $2^k$ where $k$ is a positive integer from $1$ to $53$ inclusive. Thus, there are $53$ such numbers in the list $P$ . Since $4^\ell=(2^2)^\ell=2^{2\ell}$ , then $4^\ell$ is in list $P$ exactly when $2^{2\ell}\leq2^{53}$ or $2\ell\leq53$ for positive integers $\ell$ . The largest positive integer $\ell$ for which $2\ell\leq53$ is $26$ (since $2\times26=52$ , and $2\times27=54$ ). Thus, for all positive integers $\$\ell \leq$
26 $,$ $4^\ell$ $is in list$ P $, and so there are$ 26 such numbers. We demonstrate this relationship between the powers of

Figure for this problem

Figure for this problem 2 $and$ 4 $in the table below.$ 2^k2^12^22^32^42^52^6 $\cdots$ 2^{51}2^{52}2^{53} $4^{\ell}=2^{2\ell}$ 4^1=2^24^2=2^44^3=2^6 $\cdots$ 4^{26}=2^{52} $From (b), list$ P $contains the$ 26 $numbers$ 4^r=2^{2r} $for positive integers$ $r\leq$ 26 $. That is, each integer power of$ 4 $in$ P $is equal to a power of$ 2 whose exponent is an even positive integer. Since

Figure for this problem

Figure for this problem 8^t=(2^3)^t=2^{3t}, then each integer power of

Figure for this problem

Figure for this problem 8 $in$ P $is equal to a power of$ 2 whose exponent is a positive integer multiple of

Figure for this problem

Figure for this problem 3 $. Thus, any number in$ P $that is an integer power of both$ 4 $and$ 8 $must be equal to a power of$ 2 whose positive integer exponent is both even and a multiple of

Figure for this problem

Figure for this problem 3 $, and therefore a multiple of$ 6 $.$ P $contains all numbers$ 2^k $for positive integers$ $k\leq$ 53 $, and so$ P contains the following powers of

Figure for this problem

Figure for this problem 2 $whose exponent is a multiple of$ 6 $:$ 2^6 $,$ 2^{12} $,$ 2^{18} $,$ 2^{24} $,$ 2^{30} $,$ 2^{36} $,$ 2^{42} $, and$ 2^{48} $. For positive integers$ r $and$ t $, there are$ 8 $numbers in$ P $that can be written as both$ 4^r $and as$ 8^t $, and so there are$ 26-8=18 $numbers in$ P $which can be written as$ 4^r $but cannot be written as$ 8^t. We demonstrate this relationship between the powers of

Figure for this problem

Figure for this problem 2 $,$ 4 $and$ 8 $in the table below.$ 4^r=2^{2r}4^14^24^3=2^64^44^54^6=2^{12} $\cdots$ 4^{24}=2^{48}4^{25}4^{26}8^t=2^{3t}8^2=2^{6}8^4=2^{12} $\cdots$ 8^{16}=2^{48}4^r $not$ 8^t4^14^24^44^5 $\cdots$ 4^{25}4^{26}$

Want a route through all this instead of an archive? The track puts 2,604 problems in a working order, from Junior Challenge level to the IMO shortlist.

Source: CEMC, University of Waterloo, licensed CC-BY-NC-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.