Question and Answers Forum

All Questions      Topic List

None Questions

Previous in All Question      Next in All Question      

Previous in None      Next in None      

Question Number 127861 by naka3546 last updated on 02/Jan/21

How many natural numbers n ≤ 2020 such that (n + 3)! is divisible by 2^n ?

$${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

2^n ∣(n+3)!⇒k≥n where k is the exponent of 2 in the prime factorization of (n+3)! but we know by legendre formula that k=v_2 ((n+3)!)=Σ_(j=1) ^∞ ⌊((n+3)/2^j )⌋=((n+3−s_2 (n+3))/(2−1)) where s_p (n) is the sum of the digits of n in the base p expansion of n n≤k=n+3−s_2 (n+3) ⇒s_2 (n+3)≤3 ⇒s_2 (n+3)∈{1, 2, 3} I case: s_2 (n+3)=1 ⇒ n+3=2^a ≤1024, 0≤a≤10 n=2^a −3≤1021 ∴ 2≤a≤10 which gives us 9 cases II case: s_2 (n+3)=2 ⇒n+3=2^a +2^b ≤1536, 10≥a>b≥0 n=2^a +2^b −3≤1533 ∴ 10≥a>b≥0 which gives us 10+9+8+...+2=54 cases III case: s_2 (n+3)=3 ⇒n+3=2^a +2^b +2^c ≤1792, 10≥a>b>c≥0 n=2^a +2^b +2^c −3≤1789 and that gives Σ_(n=1) ^9 ((n(n+1))/2)=165 cases So on total we have 165+54+9=228 natural numbers n≤2020 such that (((n+3)!)/2^n )∈Z (if you consider 0 as natural number so the answer 229)

$$\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) \\ $$$$ \\ $$

Terms of Service

Privacy Policy

Contact: info@tinkutara.com