NT-B2-M05-P018 Когда почти хватает двоек

Используйте формулу \(v_2(n!)=n-s_2(n)\), где \(s_2(n)\) - сумма цифр \(n\) в двоичной записи.

Из формулы Лежандра следует известное тождество \(v_2(n!)=\lfloor n/2\rfloor+\lfloor n/4\rfloor+\cdots=n-s_2(n)\), где \(s_2(n)\) - сумма цифр в двоичной записи \(n\). Условие \(2^{n-1}\mid n!\) равносильно \(v_2(n!)\ge n-1\), то есть \(n-s_2(n)\ge n-1\). Отсюда \(s_2(n)\le1\). Для натурального \(n\) это возможно только тогда, когда в двоичной записи ровно одна единица, то есть \(n\) является степенью двойки. Проверка обратного направления: если \(n=2^r\), то \(s_2(n)=1\), значит \(v_2(n!)=n-1\), и делимость выполнена.

Это сильная задача на связь valuations и двоичной записи.