Question

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

Answer 1

\[ \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}\]

Answer 2

isn't it 6 instead of 3

Answer 3

sorry ... forgot it

Answer 4

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

Answer 5

where do you get this problems?

Answer 6

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

Answer 7

compititions,books,...

Answer 8

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

Answer 9

lol

Answer 10

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

Answer 11

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

Answer 12

n = 2 is one solution

Answer 13

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

Answer 14

let me try some programming solution up to 100

Answer 15

yeah that will give all solutions

Answer 16

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

Answer 17

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

Answer 18

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

Answer 19

between 1 to 999
1 12

2 24

3 48

7 384

23 12288

Answer 20

gcd is 1

Answer 21

exper those are only solutions

gane 1? how

Answer 22

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

Answer 23

i tried euclid its repeating forever

Answer 24

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

Answer 25

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

Answer 26

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

Answer 27

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

Answer 28

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

Answer 29

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

Answer 30

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

Answer 31

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

Answer 32

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

Answer 33

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

Answer 34

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.

Answer 35

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

Answer 36

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

Answer 37

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

Answer 38

oh man go back to ur work :)

Answer 39

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

Answer 40

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

Answer 41

sure

Answer 42

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



\]

Answer 43

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

Answer 44

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}}

Answer 45

\[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\]

Answer 46

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