MathLabs

第4問

k!=(2n−1)(2n−2)(2n−4)⋯(2n−2n−1).k!=(2^n-1)(2^n-2)(2^n-4)\cdots(2^n-2^{n-1}). を満たす正の整数の組 (k,n)(k,n) をすべて求めよ。
ステップ 3/6: ルジャンドルの公式で k の下界を得る
前のステップ次のステップ
v2(k!)=∑j≥1⌊k2j⌋=k−s2(k)<k,n(n−1)2=v2(k!)<kv_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
詳しい解説

k!=Lnk!=L_n なので、それらの付値は等しい。ルジャンドルの公式より v2(k!)=k−s2(k)<kv_2(k!)=k-s_2(k)<k である。ここで s2(k)≥1s_2(k)\ge1 は kk の二進表示の各桁の和である。ステップ2と合わせると、n(n−1)/2=v2(k!)<kn(n-1)/2=v_2(k!)<k を得る。