Problem 4

Find all pairs

(k,n)

of positive integers such that

k!=(2^n-1)(2^n-2)(2^n-4)\cdots(2^n-2^{n-1}).

Step 3 of 6: Use Legendre's formula to bound k from below

Previous step Next step

v_2(k!)=\sum_{j\ge1}\left\lfloor\frac{k}{2^j}\right\rfloor=k-s_2(k)<k,\qquad \frac{n(n-1)}2=v_2(k!)<k

Detailed analysis

Since $k!=L_n$ , their valuations agree. Legendre's formula gives $v_2(k!)=k-s_2(k)<k$ , where $s_2(k)\ge1$ is the sum of the binary digits of $k$ . Together with Step 2 this yields $n(n-1)/2=v_2(k!)<k$ .