SAT1000 - P915

$173 \equiv 1 \pmod{2}$ so $x_{173}$ is in the front half of $P_1$ .

$173 \equiv 1 \pmod{4}$ so $x_{173}$ is in the front quarter of $P_2$ .

$173 \equiv 5 \pmod{8}$ so $x_{173}$ is in the second half of the front quarter (in other words, the second eighth) of $P_3$ .

$173 \equiv 13 \pmod{16}$ so $x_{173}$ is in the second half of the second eighth (in other words, the fourth sixteenth) of $P_4$ .

$173 = 16 \cdot 10 + 13$ , so $x_{173}$ is the $10 + 1 = 11^{\text{th}}$ term in the fourth sixteenth of $P_4$ . The first three sixteenths have $\frac{2^{32}}{16} = 2^{28}$ terms each.

Therefore, $x_{173}$ is in position $M = 3 \cdot 2^{28} + 11 = \boxed{805306379}$ of $P_4$ .

For given $n$ , we have $N = 2^n$ distinct numbers $x_1\,,\,x_2\,,\,x_3\,,\,\cdots\,,\,x_N$ labeled at position $1\,,\,2\,,\,3\,,\,\cdots\,,\,N$ to form a permutation

$P_0 = x_1x_2x_3\cdots x_N$

For $n = 32$ we have $N = 2^{32}$ . On applying transformation $C$ to $P_0$ we get,

$P_1 = x_1x_3x_5x_7\cdots x_{2^{32}-1}x_2x_4x_6\cdots x_{2^{32}}$

Since $173$ is an odd number we conclude that $x_{173}$ must be in the first half of $P_1$ . Let $x_{173}$ be at $n$ th position from left. Then

$2n - 1 = 173\newline\Rightarrow n = 87$

So, $x_{173}$ is at $87th$ position of $P_1$ .

Dividing $P_1$ into $2^1 = 2$ segments and then again applying $C$ to each segment of $P_1$ we get,

Since $87$ is again an odd number we get that $x_{173}$ occurs at odd position in first segment of $P_1$ . So it occurs at left part of first segment in $P_2$ formed by transformation $C$ to $P_1$ . Position of $x_{173}$ in $P_2$ is determined by

$2n - 1 - 87\newline\Rightarrow n = 44$

So, $x_{173}$ is at $44th$ position of $P_2$ .

Dividing $P_2$ into $2^2 = 4$ segments each of length $2^{30}$ and then again applying $C$ to each segment of $P_2$ we get,

Since $44$ is an even number and less than $2^{30}$ length of each segment of $P_2$ we get that $x_{173}$ occurs at even position in first segment of $P_2$ . So it occurs at right part of first segment in $P_3$ formed by transformation $C$ to $P_2$ . Left part of first segment of $P_3$ consists of (half of the length of segment) numbers. So number of numbers in left part of first segment of $P_3$ is $\displaystyle\frac{2^{30}}{2} = 2^{29}$ . Position of $x_{173}$ in right part of first segment of $P_3$ is determined by

$2n = 44\newline\Rightarrow n = 22$ .

So, $x_{173}$ is at $(2^{29} + 22)th$ position of $P_3$ .

Dividing $P_3$ into $2^3 = 8$ segments each of length $2^{29}$ and then again applying $C$ to each segment of $P_3$ we get,

We see that $x_{173}$ is at $(2^{29} + 22)th$ position of $P_3$ . So, it means that $x_{173}$ occurs in the second segment of $P_3$ because each segment is of length $2^{29}$ . Now in the second segment $x_{173}$ is at $22nd$ position from left.

Since $22$ is again an even number we get that $x_{173}$ occurs at even position in the second segment of $P_3$ . So it occurs at the right part of second segment of $P_4$ formed by transformation $C$ to $P_3$ . Left part of second segment of $P_4$ consists of (half of the length of segment) numbers. So number of numbers in left part of second segment of $P_4$ is $\displaystyle\frac{2^{29}}{2} = 2^{28}$ . Position of $x_{173}$ in right part of second segment of $P_4$ is determined by

$2n = 22\newline \Rightarrow n = 11$

So, $x_{173}$ is at $(2^{29} + 2^{28} + 11)th = 805306379th$ position of $P_4$ .