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


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

$H o w m a n y n a t u r a l n u m b e r s n ⩽ 2020 s u c h t h a t$ $(n + 3)! i s d i v i s i b l e b y 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)$
	$2^{n} ∣ (n + 3)! \Rightarrow 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)!) = \underset{j = 1}{\sum^{\infty}} ⌊ \frac{n + 3}{2^{j}} ⌋ = \frac{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)$ $\Rightarrow s_{2} (n + 3) ⩽ 3$ $\Rightarrow s_{2} (n + 3) \in {1, 2, 3}$ $I case : s_{2} (n + 3) = 1$ $\Rightarrow 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$ $\Rightarrow 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$ $\Rightarrow 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$ $\underset{n = 1}{\sum^{9}} \frac{n (n + 1)}{2} = 165 cases$ $So on total we have 165 + 54 + 9 = 228$ $natural numbers n ⩽ 2020 such that$ $\frac{(n + 3)!}{2^{n}} \in Z$ $(if you consider 0 as natural number so$ $the answer 229)$
Terms of Service
Privacy Policy
Contact: info@tinkutara.com

Question and Answers Forum