## mukushla 2 years ago Determine all positive integers $$n\ge 3$$ for which$1+\dbinom{n}{1}+\dbinom{n}{2}+\dbinom{n}{3}$is a divisor of $$2^{2000}$$

1. experimentX

$\binom{n}{0} + \binom{n}{1} = \binom{n+1}{1}$ $\binom{n}{2} + \binom{n}{3} = \binom{n+1}{3}$ $n+1 + {(n + 1 )n (n-1)\over 3} = {(n+1)(3 + n(n-1))\over 3}$

2. mukushla

isn't it 6 instead of 3

3. experimentX

sorry ... forgot it

4. mukushla

so${(n+1)(6 + n(n-1))\over 6}=\frac{(n+1)(n^2-n+6)}{6}$is a divisor of $$2^{2000}$$

5. experimentX

where do you get this problems?

6. mukushla

so it must be in the form$\frac{(n+1)(n^2-n+6)}{6}=2^m \ \ \ \ m\le2000$

7. mukushla

compititions,books,...

8. experimentX

ah man ... i thought engineers don't like number theory.

9. mukushla

lol

10. experimentX

$(n+1)(n^2-n+6) \times k=3 \times 2^{2000+1}$

11. mukushla

or we can state problem like this$(n+1)(n^2-n+6)=3\times2^{m+1} \ \ \ \ m\le2000$

12. experimentX

n = 2 is one solution

13. experimentX

n = 3, 4, 5, 6 <-- these does not work

14. experimentX

let me try some programming solution up to 100

15. mukushla

yeah that will give all solutions

16. mukushla

guys can u find $\gcd(n+1,n^2-n+6)$?

17. experimentX

regarding this problem ... i don't have approach ... matlab collapses after 2^100

18. experimentX

probably i should recursively divide the quotient by 2 after dividing by 3

19. experimentX

between 1 to 999 1 12 2 24 3 48 7 384 23 12288

20. ganeshie8

gcd is 1

21. mukushla

exper those are only solutions gane 1? how

22. experimentX

i started loop from 1 clc; for i=1:999 num = (i+1)*(i^2 - i + 6); if rem(num, 3) == 0 quo = num/3; while true if quo == 2; disp([i, num]); break; end; if rem(quo, 2) ~= 0; break; end; quo = quo/2; end end end

23. ganeshie8

i tried euclid its repeating forever

24. experimentX

probably are the only solutions (3, 48), (7, 384), (23, 12288)

25. mukushla

emm... there is useful formula$\gcd(a,b)=\gcd(a,ak+b) \ \ \ k \in \mathbb{Z}$

26. experimentX

$\gcd(n+1, n(n+1) - 2n + 6) => \gcd(n+1, 2(n -3))$

27. mukushla

$\gcd(n+1,8)= \gcd(n+1, -2(n+1)+2(n -3))$

28. experimentX

let's try elimination here ... this is divisible by 2 all times $(n+1)(n^2-n+6)$ suppose what must be the value of n^2 - n + 6 if n+1 is not divisible by 3

29. mukushla

the point is $\gcd(n+1,n^2-n+6)|8$

30. experimentX

n+1 = 3k +1, 3k +2 => n = 3k, 3k+1 9k^2 - 3k+6 <-- divisible by 3 9k^2 + 6k +1 - 3k - 1 + 6 <-- divisible by 3 <-- bad luck

31. experimentX

this seems to be valid for 3k, 3k+1, 3k+2 let's try for this 3k+2 (3k+3)(9k^2 + 12k + 4 - 3k - 2 + 6) = 3(k+1)(9k^2 + 9 k + 4) (k+1)(9k^2 + 9 k + 4) = 2^x

32. experimentX

implies k should be odd ... (2y+1) .. such that k+1 = 2^p for some p ie, k+1 = 2, 4, 8, 16, ....

33. experimentX

for k = 7, the expression (9k^2 + 9 k + 4) is 512 ... which shows that n = 2*7 + 2 = 23

34. experimentX

it remains to prove that there is no other n for the this type of 3k+2 form ... let k= 2^p - 1 (9(2^p -1) ^2 + 9 (2^9 -1) + 4) = 9*2^(2p) - 18 2^p + 9 + 9 * 2^p - 9 + 4 9*2^(2p) - 9 *2^p + 4 = 2^q for some integer.

35. experimentX

man this is tough .. gotta work on classical + statistical mechanics ... have exam five days later.

36. mukushla

np man...how many exams do u have?

37. experimentX

1 down three more to go ... + 2 practicals

38. mukushla

oh man go back to ur work :)

39. experimentX

yeah ... i'll watch the developments. physicist are not so good with numbers.

40. mukushla

we have lots of times to work on brainwashing problems like this

41. experimentX

sure

42. eliassaab

I wrote a Mathematica Program for $$n \le10^6$$ I found that $\frac{1}{6} (n+1) \left(n^2-n+6\right)$ is a power of 2 for for $n=3, \quad \frac{1}{6} (n+1) \left(n^2-n+6\right)=8\\ n=7, \quad \frac{1}{6} (n+1) \left(n^2-n+6\right)=64\\ n=23, \quad \frac{1}{6} (n+1) \left(n^2-n+6\right)=2048\\$

43. eliassaab

I just did it $$n = 2 (10^6)$$

44. eliassaab

Here is the Mathematica Program Clear[h, n] h[n_] = 1/6 (1 + n) (6 - n + n^2); PowerTwoQ[n_] := Module[{x }, x = n; While[ Divisible[x, 2] && x > 1, x = x/2;]; Return[ x == 1]] Q = {}; For [ n = 2, n < 2000000, n++; If [PowerTwoQ[h[n]], Q = Append[Q, {n, h[n]}]]]; Q The output is {{3, 8}, {7, 64}, {23, 2048}}

45. mukushla

$1+\dbinom{n}{1}+\dbinom{n}{2}+\dbinom{n}{3}=\frac{n^3+5n+6}{6}$ so we must have$\frac{n^3+5n+6}{6}=2^k \ \ \ \ \ \ \ \ k\le2000$or$(n+1)(n^2-n+6)=3\times2^{k+1}$but notice that$\gcd(n+1\ , \ n^2-n+6)=\gcd(n+1\ , \ n^2-n-n^2-n+6)$$\gcd(n+1\ , \ -2n+6)=\gcd(n+1\ , \ -2n+2n+2+6)=\gcd(n+1 \ , \ 8)$$\Rightarrow \gcd(n+1\ , \ n^2-n+6) | 8$since $$n^2-n+6>n+1$$ power of $$2$$ in $$n+1$$ can not be greater than $$4$$ in other words $$n+1=16$$ or $$n+1| 3\times 2^3$$ so we have few cases to check$n=3,5,7,11,15,23$

46. mukushla

checking that numbers gives $$3$$ solution : $$\color\red{n=3,7,23}$$