## mukushla Group Title 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}$$ one year ago one year ago

1. experimentX Group Title

$\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 Group Title

isn't it 6 instead of 3

3. experimentX Group Title

sorry ... forgot it

4. mukushla Group Title

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 Group Title

where do you get this problems?

6. mukushla Group Title

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

7. mukushla Group Title

compititions,books,...

8. experimentX Group Title

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

9. mukushla Group Title

lol

10. experimentX Group Title

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

11. mukushla Group Title

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

12. experimentX Group Title

n = 2 is one solution

13. experimentX Group Title

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

14. experimentX Group Title

let me try some programming solution up to 100

15. mukushla Group Title

yeah that will give all solutions

16. mukushla Group Title

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

17. experimentX Group Title

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

18. experimentX Group Title

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

19. experimentX Group Title

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

20. ganeshie8 Group Title

gcd is 1

21. mukushla Group Title

exper those are only solutions gane 1? how

22. experimentX Group Title

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 Group Title

i tried euclid its repeating forever

24. experimentX Group Title

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

25. mukushla Group Title

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

26. experimentX Group Title

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

27. mukushla Group Title

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

28. experimentX Group Title

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 Group Title

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

30. experimentX Group Title

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 Group Title

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 Group Title

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 Group Title

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

34. experimentX Group Title

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 Group Title

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

36. mukushla Group Title

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

37. experimentX Group Title

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

38. mukushla Group Title

oh man go back to ur work :)

39. experimentX Group Title

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

40. mukushla Group Title

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

41. experimentX Group Title

sure

42. eliassaab Group Title

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 Group Title

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

44. eliassaab Group Title

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 Group Title

$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 Group Title

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