Question Number 127861 by naka3546 last updated on 02/Jan/21
$${How}\:\:{many}\:\:{natural}\:\:{numbers}\:\:{n}\:\leqslant\:\mathrm{2020}\:{such}\:\:{that} \\ $$$$\left({n}\:+\:\mathrm{3}\right)!\:\:{is}\:\:{divisible}\:\:{by}\:\:\mathrm{2}^{{n}} \:? \\ $$
Answered by floor(10²Eta[1]) last updated on 03/Jan/21
$$\mathrm{2}^{\mathrm{n}} \mid\left(\mathrm{n}+\mathrm{3}\right)!\Rightarrow\mathrm{k}\geqslant\mathrm{n} \\ $$$$\mathrm{where}\:\mathrm{k}\:\mathrm{is}\:\mathrm{the}\:\mathrm{exponent}\:\mathrm{of}\:\mathrm{2}\:\mathrm{in}\:\mathrm{the}\:\mathrm{prime}\: \\ $$$$\mathrm{factorization}\:\mathrm{of}\:\left(\mathrm{n}+\mathrm{3}\right)! \\ $$$$\mathrm{but}\:\mathrm{we}\:\mathrm{know}\:\mathrm{by}\:\mathrm{legendre}\:\mathrm{formula}\:\mathrm{that} \\ $$$$\mathrm{k}=\mathrm{v}_{\mathrm{2}} \left(\left(\mathrm{n}+\mathrm{3}\right)!\right)=\underset{\mathrm{j}=\mathrm{1}} {\overset{\infty} {\sum}}\lfloor\frac{\mathrm{n}+\mathrm{3}}{\mathrm{2}^{\mathrm{j}} }\rfloor=\frac{\mathrm{n}+\mathrm{3}−\mathrm{s}_{\mathrm{2}} \left(\mathrm{n}+\mathrm{3}\right)}{\mathrm{2}−\mathrm{1}} \\ $$$$\mathrm{where}\:\mathrm{s}_{\mathrm{p}} \left(\mathrm{n}\right)\:\mathrm{is}\:\mathrm{the}\:\mathrm{sum}\:\mathrm{of}\:\mathrm{the}\:\mathrm{digits}\:\mathrm{of}\:\mathrm{n}\:\mathrm{in} \\ $$$$\mathrm{the}\:\mathrm{base}\:\mathrm{p}\:\mathrm{expansion}\:\mathrm{of}\:\mathrm{n} \\ $$$$ \\ $$$$\mathrm{n}\leqslant\mathrm{k}=\mathrm{n}+\mathrm{3}−\mathrm{s}_{\mathrm{2}} \left(\mathrm{n}+\mathrm{3}\right) \\ $$$$\Rightarrow\mathrm{s}_{\mathrm{2}} \left(\mathrm{n}+\mathrm{3}\right)\leqslant\mathrm{3} \\ $$$$\Rightarrow\mathrm{s}_{\mathrm{2}} \left(\mathrm{n}+\mathrm{3}\right)\in\left\{\mathrm{1},\:\mathrm{2},\:\mathrm{3}\right\} \\ $$$$\mathrm{I}\:\mathrm{case}:\:\mathrm{s}_{\mathrm{2}} \left(\mathrm{n}+\mathrm{3}\right)=\mathrm{1} \\ $$$$\Rightarrow\:\mathrm{n}+\mathrm{3}=\mathrm{2}^{\mathrm{a}} \leqslant\mathrm{1024},\:\mathrm{0}\leqslant\mathrm{a}\leqslant\mathrm{10} \\ $$$$\mathrm{n}=\mathrm{2}^{\mathrm{a}} −\mathrm{3}\leqslant\mathrm{1021}\:\therefore\:\mathrm{2}\leqslant\mathrm{a}\leqslant\mathrm{10} \\ $$$$\mathrm{which}\:\mathrm{gives}\:\mathrm{us}\:\mathrm{9}\:\mathrm{cases} \\ $$$$\mathrm{II}\:\mathrm{case}:\:\mathrm{s}_{\mathrm{2}} \left(\mathrm{n}+\mathrm{3}\right)=\mathrm{2} \\ $$$$\Rightarrow\mathrm{n}+\mathrm{3}=\mathrm{2}^{\mathrm{a}} +\mathrm{2}^{\mathrm{b}} \leqslant\mathrm{1536},\:\mathrm{10}\geqslant\mathrm{a}>\mathrm{b}\geqslant\mathrm{0} \\ $$$$\mathrm{n}=\mathrm{2}^{\mathrm{a}} +\mathrm{2}^{\mathrm{b}} −\mathrm{3}\leqslant\mathrm{1533}\:\therefore\:\mathrm{10}\geqslant\mathrm{a}>\mathrm{b}\geqslant\mathrm{0} \\ $$$$\mathrm{which}\:\mathrm{gives}\:\mathrm{us}\: \\ $$$$\mathrm{10}+\mathrm{9}+\mathrm{8}+…+\mathrm{2}=\mathrm{54}\:\mathrm{cases} \\ $$$$\mathrm{III}\:\mathrm{case}:\:\mathrm{s}_{\mathrm{2}} \left(\mathrm{n}+\mathrm{3}\right)=\mathrm{3} \\ $$$$\Rightarrow\mathrm{n}+\mathrm{3}=\mathrm{2}^{\mathrm{a}} +\mathrm{2}^{\mathrm{b}} +\mathrm{2}^{\mathrm{c}} \leqslant\mathrm{1792},\:\mathrm{10}\geqslant\mathrm{a}>\mathrm{b}>\mathrm{c}\geqslant\mathrm{0} \\ $$$$\mathrm{n}=\mathrm{2}^{\mathrm{a}} +\mathrm{2}^{\mathrm{b}} +\mathrm{2}^{\mathrm{c}} −\mathrm{3}\leqslant\mathrm{1789} \\ $$$$\mathrm{and}\:\mathrm{that}\:\mathrm{gives} \\ $$$$\underset{\mathrm{n}=\mathrm{1}} {\overset{\mathrm{9}} {\sum}}\frac{\mathrm{n}\left(\mathrm{n}+\mathrm{1}\right)}{\mathrm{2}}=\mathrm{165}\:\mathrm{cases} \\ $$$$\mathrm{So}\:\mathrm{on}\:\mathrm{total}\:\mathrm{we}\:\mathrm{have}\:\mathrm{165}+\mathrm{54}+\mathrm{9}=\mathrm{228}\: \\ $$$$\mathrm{natural}\:\mathrm{numbers}\:\mathrm{n}\leqslant\mathrm{2020}\:\mathrm{such}\:\mathrm{that} \\ $$$$\frac{\left(\mathrm{n}+\mathrm{3}\right)!}{\mathrm{2}^{\mathrm{n}} }\in\mathbb{Z} \\ $$$$ \\ $$$$\left(\mathrm{if}\:\mathrm{you}\:\mathrm{consider}\:\mathrm{0}\:\mathrm{as}\:\mathrm{natural}\:\mathrm{number}\:\mathrm{so}\right. \\ $$$$\left.\mathrm{the}\:\mathrm{answer}\:\mathrm{229}\right) \\ $$$$ \\ $$