How-many-natural-numbers-n-2020-such-that-n-3-is-divisible-by-2-n-

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)! \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 + \dots + 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)