Problem
NT-B2-M05-P018 When There Are Almost Enough Twos
#18
★★★★★ Level 5 of 5
Find all positive integers \(n\) such that \(2^{n-1}\mid n!\).
Use the formula \(v_2(n!)=n-s_2(n)\), where \(s_2(n)\) is the sum of binary digits of \(n\).
Legendre's formula implies the identity \(v_2(n!)=\lfloor n/2\rfloor+\lfloor n/4\rfloor+\cdots=n-s_2(n)\), where \(s_2(n)\) is the sum of binary digits of \(n\). The condition \(2^{n-1}\mid n!\) is equivalent to \(v_2(n!)\ge n-1\), that is, \(n-s_2(n)\ge n-1\). Hence \(s_2(n)\le1\). For a positive integer \(n\), this means the binary representation has exactly one \(1\), so \(n\) is a power of two. Conversely, if \(n=2^r\), then \(s_2(n)=1\), hence \(v_2(n!)=n-1\), and the divisibility holds.
A strong problem connecting valuations with binary notation.