Mixing
Find the smallest positive integer $m$ such that $ 2015choosem $ is an even number
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Find the smallest positive integer $m$ such that $$
2015choosem$$ is an even number.
Since $$
2015choosem = frac20151 cdot frac20142 cdots frac2016-mm = prod_k=1^m frac2016-kk, $$
we only need to find the smallest $m$ such that $$ m = 2^a_m cdot p_m, , 2016-m = 2^b_m cdot q_m, , 2 not mid p_m, , 2 not mid q_m, , a_m < b_m.$$
In this problem, it turns out that when $m=32$, we have $$ 32=2^5, , 2016-32=1984=2^6 cdot 31. $$
However, we will need to try $m=2,4,6,ldots,32$, the answer will not come out easily.
Is there any easier way to solve this problem?
combinatorics number-theory
asked 2 days ago
Star Chou
3349
add a comment |Â
up vote
2
down vote
favorite
Find the smallest positive integer $m$ such that $$
2015choosem$$ is an even number.
Since $$
2015choosem = frac20151 cdot frac20142 cdots frac2016-mm = prod_k=1^m frac2016-kk, $$
we only need to find the smallest $m$ such that $$ m = 2^a_m cdot p_m, , 2016-m = 2^b_m cdot q_m, , 2 not mid p_m, , 2 not mid q_m, , a_m < b_m.$$
In this problem, it turns out that when $m=32$, we have $$ 32=2^5, , 2016-32=1984=2^6 cdot 31. $$
However, we will need to try $m=2,4,6,ldots,32$, the answer will not come out easily.
Is there any easier way to solve this problem?
combinatorics number-theory
asked 2 days ago
Star Chou
3349
Possibly helpful, possible duplicate: math.stackexchange.com/questions/233269/…
– Ethan Bolker
2 days ago
That's the way I would use, you already have an approach that is optimal in many ways.
– Arnaud Mortier
2 days ago
add a comment |Â
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Find the smallest positive integer $m$ such that $$
2015choosem$$ is an even number.
Since $$
2015choosem = frac20151 cdot frac20142 cdots frac2016-mm = prod_k=1^m frac2016-kk, $$
we only need to find the smallest $m$ such that $$ m = 2^a_m cdot p_m, , 2016-m = 2^b_m cdot q_m, , 2 not mid p_m, , 2 not mid q_m, , a_m < b_m.$$
In this problem, it turns out that when $m=32$, we have $$ 32=2^5, , 2016-32=1984=2^6 cdot 31. $$
However, we will need to try $m=2,4,6,ldots,32$, the answer will not come out easily.
Is there any easier way to solve this problem?
combinatorics number-theory
asked 2 days ago
Star Chou
3349
Find the smallest positive integer $m$ such that $$
2015choosem$$ is an even number.
Since $$
2015choosem = frac20151 cdot frac20142 cdots frac2016-mm = prod_k=1^m frac2016-kk, $$
we only need to find the smallest $m$ such that $$ m = 2^a_m cdot p_m, , 2016-m = 2^b_m cdot q_m, , 2 not mid p_m, , 2 not mid q_m, , a_m < b_m.$$
In this problem, it turns out that when $m=32$, we have $$ 32=2^5, , 2016-32=1984=2^6 cdot 31. $$
However, we will need to try $m=2,4,6,ldots,32$, the answer will not come out easily.
Is there any easier way to solve this problem?
combinatorics number-theory
asked 2 days ago
Star Chou
3349
asked 2 days ago
Star Chou
3349
asked 2 days ago
Star Chou
3349
asked 2 days ago
Star Chou
3349
3349
Possibly helpful, possible duplicate: math.stackexchange.com/questions/233269/…
– Ethan Bolker
2 days ago
That's the way I would use, you already have an approach that is optimal in many ways.
– Arnaud Mortier
2 days ago
add a comment |Â
Possibly helpful, possible duplicate: math.stackexchange.com/questions/233269/…
– Ethan Bolker
2 days ago
That's the way I would use, you already have an approach that is optimal in many ways.
– Arnaud Mortier
2 days ago
Possibly helpful, possible duplicate: math.stackexchange.com/questions/233269/…
– Ethan Bolker
2 days ago
Possibly helpful, possible duplicate: math.stackexchange.com/questions/233269/…
– Ethan Bolker
2 days ago
That's the way I would use, you already have an approach that is optimal in many ways.
– Arnaud Mortier
2 days ago
That's the way I would use, you already have an approach that is optimal in many ways.
– Arnaud Mortier
2 days ago
add a comment |Â
6 Answers
6
active
oldest
votes
up vote
5
down vote
accepted
Kummer's theorem:
for given integers $n ge m ge 0$ and a prime number $p$, the $p$-adic valuation $nu _pleft(tbinom nmright)$ is equal to the number of carries when $m$ is added to $n - m$ in base $p$
Since $2015_10 = 11111011111_2$ it's clear that for any $m < 32$ there will be no carries, and so $binom2015m$ will be odd. However, to subtract $32_10 = 100000_2$ we need to borrow, and therefore adding $32$ and $2015-32$ will require a carry. QED.
answered 2 days ago
Peter Taylor
7,66512139
add a comment |Â
up vote
2
down vote
for any natural number $n$, let $v_2(n)$ denote the order to which $2$ divides $n$.
It is not difficult to show that $$v_2(n!)=sum_i=1^inftyBig lfloor frac n2^i Big rfloorimplies v_2(2015!)=2005$$
It follows that we are asking for the least $k$ such that $$v_2(k!)+v_2((2015-k)!)<2005$$
In searching for such a $k$ it is helpful to note that $2^6,|,1984$ and that this is the closest integer less than $2015$ which is divisible by a large power of $2$. Thus it is reasonable to imagine that we want $k$ such that $2015-k=1983$, so $k=32$.
Note: This isn't a complete proof, just a strong heuristic to suggest that $32$ is correct. Given the above, $32$ is the first number I would try...though there is still some work involved in proving that it is minimal. The inequality shows an easy way to perform the necessary check without heavy computations.
answered 2 days ago
lulu
34.7k13971
add a comment |Â
up vote
1
down vote
$2016 = 2^5*63$
So $2016 - j_odd*2^k= 63*2^5- j_odd*2^k$ will be divisible by $2^k$ for all $k <5$ and the terms $frac 2016-j_odd*2^k2^k=63*2^5-k - j_odd$ will all be odd.
So for any $m < 32$ then $2015 m =frac 2015*2014*2013*2012*.....(2016-m)1*2*3*4*.....*m$ will have to be odd because all the even terms $2014, 2012, 2010, .......$ (which are divisible by $2, 2^2, 2, 2^3, 2, 2^2, 2,2^4, 2, 2^2,2,2^3,2, 2^2, 2....$) are "matched up to be divided" by the even terms, $2,4,6,8,10,12,14,16,...$ which are also divisible by $2, 2^2, 2, 2^3, 2, 2^2, 2,2^4, 2, 2^2,2,2^3,2, 2^2, 2...$. So each term in the numerator divisible by a power of $2$ is in "lockstep" with a matching power of $2$ is the denominator.
$2016 -32 = 1984$ which is divisible by $32$ but because $2016 = 63*32$ that means $2016-32 = 62*32$ and as $62$ is even we have broken the lockstep and $2016-32$ is divisble not just be $32$ but by $64$.
So $2015 32 = frac 2015*2014*2013*2012*2011....... *1983*19841*2*3*4*5......*31 *32 = frac 2015*1007*2013*503*2011......*1983*621*1*3*1*5*.....*31*1$ is even.
In general if $2^k|M+1$ and $2^k+1not mid M$ then $m = 2^k$ will be the least $m$ so that $M choose m$ is even.
Because $M+1 = odd*2^k$ so $M+1 - even_k$ will be "matched" numerator to denominator to $even_k$ up to $M+1 - 2^k = (odd-1)*2^k$ which will be matched to $2^k$. $frac (odd-1)*2^k2^k = odd -1$ is even so the product is even.
=====
Okay, a more formal proof.
If $nin mathbb n$ and $n = a*2^k$ where $a$ is $odd$ and $kge 0$ then define $f(n) =a$ and $g(n) = 2^k$.
$2015 choose m =frac prod_i=1^m (2016-i)prod_i=1^m i=$
$frac prod_i=1;itext odd^m (2016-m)prod_i=1;itext even^m (2016-i)prod_i=1;itext odd^m iprod_i=1;itext even^m i=$
$frac prod_i=1;itext odd^m (2016-i)prod_i=1;itext even^m (2016-i)prod_i=1;itext odd^m iprod_i=1;itext even^m f(i)prod_i=1;itext even^m g(i)=$
$frac prod_i=1;itext odd^m (2016-i)prod_i=1;itext even^m (2016-m)prod_i=1;itext odd^m iprod_i=1;itext even^m f(i)*frac prod_i=1;itext even^m (2016-f(i)g(i))prod_i=1;itext even^m g(i)=$
$frac prod_i=1;itext odd^m (2016-i)prod_i=1;itext even^m (2016-m)prod_i=1;itext odd^m iprod_i=1;itext even^m f(i)* prod_i=1;itext even^m (63*frac32min(32,g(i))-f(i)$
Which will be odd if and only if all the $(63*frac32min(32,g(i))-f(i))$ terms are odd for all even $i$.
If $g(i) < 32$ then $(63*frac32min(32,g(i))-f(i))= 63frac 32g(i) - f(i)$ is odd. If $g(i) ge 32$ then $(63*frac32min(32,g(i))-f(i))= 63 - f(i)$ is even.
So $2015 choose m$ is odd if and only if $g(i) < 32$ for all $i le m$ if and only if $m < 32$.
answered 2 days ago
fleablood
60k22575
add a comment |Â
up vote
1
down vote
for the curious, 32 is correct. Wrote a command for Legendre's rule. Now that I think about it, this leads to a method for doing this by hand, based on a proof of Legendre by induction that I once posted: http://math.stackexchange.com/questions/141196/highest-power-of-a-prime-p-dividing-n/228351#228351 Give me a few minutes. In brief,
$$ nu_p((n+1)!) = nu_p(n!) + nu_p(n+1) ; . $$
Yes. As some of the other answers have already indicated, we are searching for integer $j$ with
$$ nu_2(j+1) < nu_2(2015-j) ; , $$
after which the answer is $m=j+1.$ Then
$$ 5 = nu_2(31+1) < nu_2(2015 - 31) = nu_2(1984) = nu_2 (64 cdot 31)=6 $$
========================================================
Sat Aug 4 11:40:24 PDT 2018
1 j+1 2 2 order: 1 2015 - j 2014 order: 1
2 j+1 3 2 order: 0 2015 - j 2013 order: 0
3 j+1 4 2 order: 2 2015 - j 2012 order: 2
4 j+1 5 2 order: 0 2015 - j 2011 order: 0
5 j+1 6 2 order: 1 2015 - j 2010 order: 1
6 j+1 7 2 order: 0 2015 - j 2009 order: 0
7 j+1 8 2 order: 3 2015 - j 2008 order: 3
8 j+1 9 2 order: 0 2015 - j 2007 order: 0
9 j+1 10 2 order: 1 2015 - j 2006 order: 1
10 j+1 11 2 order: 0 2015 - j 2005 order: 0
11 j+1 12 2 order: 2 2015 - j 2004 order: 2
12 j+1 13 2 order: 0 2015 - j 2003 order: 0
13 j+1 14 2 order: 1 2015 - j 2002 order: 1
14 j+1 15 2 order: 0 2015 - j 2001 order: 0
15 j+1 16 2 order: 4 2015 - j 2000 order: 4
16 j+1 17 2 order: 0 2015 - j 1999 order: 0
17 j+1 18 2 order: 1 2015 - j 1998 order: 1
18 j+1 19 2 order: 0 2015 - j 1997 order: 0
19 j+1 20 2 order: 2 2015 - j 1996 order: 2
20 j+1 21 2 order: 0 2015 - j 1995 order: 0
21 j+1 22 2 order: 1 2015 - j 1994 order: 1
22 j+1 23 2 order: 0 2015 - j 1993 order: 0
23 j+1 24 2 order: 3 2015 - j 1992 order: 3
24 j+1 25 2 order: 0 2015 - j 1991 order: 0
25 j+1 26 2 order: 1 2015 - j 1990 order: 1
26 j+1 27 2 order: 0 2015 - j 1989 order: 0
27 j+1 28 2 order: 2 2015 - j 1988 order: 2
28 j+1 29 2 order: 0 2015 - j 1987 order: 0
29 j+1 30 2 order: 1 2015 - j 1986 order: 1
30 j+1 31 2 order: 0 2015 - j 1985 order: 0
31 j+1 32 2 order: 5 2015 - j 1984 order: 6 WOW
32 j+1 33 2 order: 0 2015 - j 1983 order: 0
33 j+1 34 2 order: 1 2015 - j 1982 order: 1
34 j+1 35 2 order: 0 2015 - j 1981 order: 0
35 j+1 36 2 order: 2 2015 - j 1980 order: 2
Sat Aug 4 11:40:24 PDT 2018
=============================================================
Sat Aug 4 10:57:09 PDT 2018
2015 two order: 2005
1 order: 0 2014 order: 2005 sum 2005
2 order: 1 2013 order: 2004 sum 2005
3 order: 1 2012 order: 2004 sum 2005
4 order: 3 2011 order: 2002 sum 2005
5 order: 3 2010 order: 2002 sum 2005
6 order: 4 2009 order: 2001 sum 2005
7 order: 4 2008 order: 2001 sum 2005
8 order: 7 2007 order: 1998 sum 2005
9 order: 7 2006 order: 1998 sum 2005
10 order: 8 2005 order: 1997 sum 2005
11 order: 8 2004 order: 1997 sum 2005
12 order: 10 2003 order: 1995 sum 2005
13 order: 10 2002 order: 1995 sum 2005
14 order: 11 2001 order: 1994 sum 2005
15 order: 11 2000 order: 1994 sum 2005
16 order: 15 1999 order: 1990 sum 2005
17 order: 15 1998 order: 1990 sum 2005
18 order: 16 1997 order: 1989 sum 2005
19 order: 16 1996 order: 1989 sum 2005
20 order: 18 1995 order: 1987 sum 2005
21 order: 18 1994 order: 1987 sum 2005
22 order: 19 1993 order: 1986 sum 2005
23 order: 19 1992 order: 1986 sum 2005
24 order: 22 1991 order: 1983 sum 2005
25 order: 22 1990 order: 1983 sum 2005
26 order: 23 1989 order: 1982 sum 2005
27 order: 23 1988 order: 1982 sum 2005
28 order: 25 1987 order: 1980 sum 2005
29 order: 25 1986 order: 1980 sum 2005
30 order: 26 1985 order: 1979 sum 2005
31 order: 26 1984 order: 1979 sum 2005
32 order: 31 1983 order: 1973 sum 2004 WOW
33 order: 31 1982 order: 1973 sum 2004 WOW
34 order: 32 1981 order: 1972 sum 2004 WOW
35 order: 32 1980 order: 1972 sum 2004 WOW
Sat Aug 4 10:57:09 PDT 2018
answered 2 days ago
Will Jagy
96.7k594195
add a comment |Â
up vote
0
down vote
We want to find the smallest positive integer $m$ such that $2015 choose m$ is an even number.
As you show, $2015 choose m = frac20151cdot frac20142cdotdots cdotfrac2016-mm$.
The question then becomes finding the smallest positive integer $m$ such that $frac2016-mm$ is even. However we see that $frac2016-mm = frac2016m - 1$, so we want $frac2016m$ to be odd.
Since $32$ is the largest power of $2$ dividing 2016, we must divide out $32$ for this to be odd.
Hence, $m=32$.
answered 2 days ago
Sodium Or
192
1
(-1) Why should $frac2016-mm$ be an integer?
– Arnaud Mortier
2 days ago
$2015choose 4 = frac 20151frac 20142 frac 20133frac 20124 = frac 20151*1007*frac 20133*503 = 2015*1007*671*503$ is odd.
– fleablood
2 days ago
@fleablood ?? When did I say m=4?
– Sodium Or
2 days ago
2
Are you seriously going to play it like that when the history of your edits is available for everyone to see? ..... "When did I say m=4?" ..... At 9:48 Aug 4, 2018 PDT.
– fleablood
2 days ago
@fleablood that edit was made 20 minutes before your comment...
– Sodium Or
2 days ago
 |Â
show 2 more comments
up vote
0
down vote
$n = 2015_10 = 11111011111_2$ and from Luca's theorem:
$$2015 choose m = prod_i=0^10 n_i choose m_i pmod 2$$
where all factors are always $1$ except for $0 choose m_5$ which is $0$ if and only if $m_5 = 1$.
The smallest number having $m_5 = 1$ is $32$.
Generally speaking $n choose m$ is odd if and only if $m land n = m$, and even otherwise, where $land$ is meant here as a bitwise operation on binary digits. In other words $n choose m$ is odd if and only if all $1$s in $m$ are $1$ also in $n$.
answered 10 hours ago
mbjoe
135
add a comment |Â
6 Answers
6
active
oldest
votes
6 Answers
6
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
5
down vote
accepted
Kummer's theorem:
for given integers $n ge m ge 0$ and a prime number $p$, the $p$-adic valuation $nu _pleft(tbinom nmright)$ is equal to the number of carries when $m$ is added to $n - m$ in base $p$
Since $2015_10 = 11111011111_2$ it's clear that for any $m < 32$ there will be no carries, and so $binom2015m$ will be odd. However, to subtract $32_10 = 100000_2$ we need to borrow, and therefore adding $32$ and $2015-32$ will require a carry. QED.
answered 2 days ago
Peter Taylor
7,66512139
add a comment |Â
up vote
5
down vote
accepted
Kummer's theorem:
for given integers $n ge m ge 0$ and a prime number $p$, the $p$-adic valuation $nu _pleft(tbinom nmright)$ is equal to the number of carries when $m$ is added to $n - m$ in base $p$
Since $2015_10 = 11111011111_2$ it's clear that for any $m < 32$ there will be no carries, and so $binom2015m$ will be odd. However, to subtract $32_10 = 100000_2$ we need to borrow, and therefore adding $32$ and $2015-32$ will require a carry. QED.
answered 2 days ago
Peter Taylor
7,66512139
add a comment |Â
up vote
5
down vote
accepted
up vote
5
down vote
accepted
Kummer's theorem:
for given integers $n ge m ge 0$ and a prime number $p$, the $p$-adic valuation $nu _pleft(tbinom nmright)$ is equal to the number of carries when $m$ is added to $n - m$ in base $p$
Since $2015_10 = 11111011111_2$ it's clear that for any $m < 32$ there will be no carries, and so $binom2015m$ will be odd. However, to subtract $32_10 = 100000_2$ we need to borrow, and therefore adding $32$ and $2015-32$ will require a carry. QED.
answered 2 days ago
Peter Taylor
7,66512139
Kummer's theorem:
for given integers $n ge m ge 0$ and a prime number $p$, the $p$-adic valuation $nu _pleft(tbinom nmright)$ is equal to the number of carries when $m$ is added to $n - m$ in base $p$
Since $2015_10 = 11111011111_2$ it's clear that for any $m < 32$ there will be no carries, and so $binom2015m$ will be odd. However, to subtract $32_10 = 100000_2$ we need to borrow, and therefore adding $32$ and $2015-32$ will require a carry. QED.
answered 2 days ago
Peter Taylor
7,66512139
answered 2 days ago
Peter Taylor
7,66512139
answered 2 days ago
Peter Taylor
7,66512139
answered 2 days ago
Peter Taylor
7,66512139
7,66512139
add a comment |Â
add a comment |Â
up vote
2
down vote
for any natural number $n$, let $v_2(n)$ denote the order to which $2$ divides $n$.
It is not difficult to show that $$v_2(n!)=sum_i=1^inftyBig lfloor frac n2^i Big rfloorimplies v_2(2015!)=2005$$
It follows that we are asking for the least $k$ such that $$v_2(k!)+v_2((2015-k)!)<2005$$
In searching for such a $k$ it is helpful to note that $2^6,|,1984$ and that this is the closest integer less than $2015$ which is divisible by a large power of $2$. Thus it is reasonable to imagine that we want $k$ such that $2015-k=1983$, so $k=32$.
Note: This isn't a complete proof, just a strong heuristic to suggest that $32$ is correct. Given the above, $32$ is the first number I would try...though there is still some work involved in proving that it is minimal. The inequality shows an easy way to perform the necessary check without heavy computations.
answered 2 days ago
lulu
34.7k13971
add a comment |Â
up vote
2
down vote
for any natural number $n$, let $v_2(n)$ denote the order to which $2$ divides $n$.
It is not difficult to show that $$v_2(n!)=sum_i=1^inftyBig lfloor frac n2^i Big rfloorimplies v_2(2015!)=2005$$
It follows that we are asking for the least $k$ such that $$v_2(k!)+v_2((2015-k)!)<2005$$
In searching for such a $k$ it is helpful to note that $2^6,|,1984$ and that this is the closest integer less than $2015$ which is divisible by a large power of $2$. Thus it is reasonable to imagine that we want $k$ such that $2015-k=1983$, so $k=32$.
Note: This isn't a complete proof, just a strong heuristic to suggest that $32$ is correct. Given the above, $32$ is the first number I would try...though there is still some work involved in proving that it is minimal. The inequality shows an easy way to perform the necessary check without heavy computations.
answered 2 days ago
lulu
34.7k13971
add a comment |Â
up vote
2
down vote
up vote
2
down vote
for any natural number $n$, let $v_2(n)$ denote the order to which $2$ divides $n$.
It is not difficult to show that $$v_2(n!)=sum_i=1^inftyBig lfloor frac n2^i Big rfloorimplies v_2(2015!)=2005$$
It follows that we are asking for the least $k$ such that $$v_2(k!)+v_2((2015-k)!)<2005$$
In searching for such a $k$ it is helpful to note that $2^6,|,1984$ and that this is the closest integer less than $2015$ which is divisible by a large power of $2$. Thus it is reasonable to imagine that we want $k$ such that $2015-k=1983$, so $k=32$.
Note: This isn't a complete proof, just a strong heuristic to suggest that $32$ is correct. Given the above, $32$ is the first number I would try...though there is still some work involved in proving that it is minimal. The inequality shows an easy way to perform the necessary check without heavy computations.
answered 2 days ago
lulu
34.7k13971
for any natural number $n$, let $v_2(n)$ denote the order to which $2$ divides $n$.
It is not difficult to show that $$v_2(n!)=sum_i=1^inftyBig lfloor frac n2^i Big rfloorimplies v_2(2015!)=2005$$
It follows that we are asking for the least $k$ such that $$v_2(k!)+v_2((2015-k)!)<2005$$
In searching for such a $k$ it is helpful to note that $2^6,|,1984$ and that this is the closest integer less than $2015$ which is divisible by a large power of $2$. Thus it is reasonable to imagine that we want $k$ such that $2015-k=1983$, so $k=32$.
Note: This isn't a complete proof, just a strong heuristic to suggest that $32$ is correct. Given the above, $32$ is the first number I would try...though there is still some work involved in proving that it is minimal. The inequality shows an easy way to perform the necessary check without heavy computations.
answered 2 days ago
lulu
34.7k13971
answered 2 days ago
lulu
34.7k13971
answered 2 days ago
lulu
34.7k13971
answered 2 days ago
lulu
34.7k13971
34.7k13971
add a comment |Â
add a comment |Â
up vote
1
down vote
$2016 = 2^5*63$
So $2016 - j_odd*2^k= 63*2^5- j_odd*2^k$ will be divisible by $2^k$ for all $k <5$ and the terms $frac 2016-j_odd*2^k2^k=63*2^5-k - j_odd$ will all be odd.
So for any $m < 32$ then $2015 m =frac 2015*2014*2013*2012*.....(2016-m)1*2*3*4*.....*m$ will have to be odd because all the even terms $2014, 2012, 2010, .......$ (which are divisible by $2, 2^2, 2, 2^3, 2, 2^2, 2,2^4, 2, 2^2,2,2^3,2, 2^2, 2....$) are "matched up to be divided" by the even terms, $2,4,6,8,10,12,14,16,...$ which are also divisible by $2, 2^2, 2, 2^3, 2, 2^2, 2,2^4, 2, 2^2,2,2^3,2, 2^2, 2...$. So each term in the numerator divisible by a power of $2$ is in "lockstep" with a matching power of $2$ is the denominator.
$2016 -32 = 1984$ which is divisible by $32$ but because $2016 = 63*32$ that means $2016-32 = 62*32$ and as $62$ is even we have broken the lockstep and $2016-32$ is divisble not just be $32$ but by $64$.
So $2015 32 = frac 2015*2014*2013*2012*2011....... *1983*19841*2*3*4*5......*31 *32 = frac 2015*1007*2013*503*2011......*1983*621*1*3*1*5*.....*31*1$ is even.
In general if $2^k|M+1$ and $2^k+1not mid M$ then $m = 2^k$ will be the least $m$ so that $M choose m$ is even.
Because $M+1 = odd*2^k$ so $M+1 - even_k$ will be "matched" numerator to denominator to $even_k$ up to $M+1 - 2^k = (odd-1)*2^k$ which will be matched to $2^k$. $frac (odd-1)*2^k2^k = odd -1$ is even so the product is even.
=====
Okay, a more formal proof.
If $nin mathbb n$ and $n = a*2^k$ where $a$ is $odd$ and $kge 0$ then define $f(n) =a$ and $g(n) = 2^k$.
$2015 choose m =frac prod_i=1^m (2016-i)prod_i=1^m i=$
$frac prod_i=1;itext odd^m (2016-m)prod_i=1;itext even^m (2016-i)prod_i=1;itext odd^m iprod_i=1;itext even^m i=$
$frac prod_i=1;itext odd^m (2016-i)prod_i=1;itext even^m (2016-i)prod_i=1;itext odd^m iprod_i=1;itext even^m f(i)prod_i=1;itext even^m g(i)=$
$frac prod_i=1;itext odd^m (2016-i)prod_i=1;itext even^m (2016-m)prod_i=1;itext odd^m iprod_i=1;itext even^m f(i)*frac prod_i=1;itext even^m (2016-f(i)g(i))prod_i=1;itext even^m g(i)=$
$frac prod_i=1;itext odd^m (2016-i)prod_i=1;itext even^m (2016-m)prod_i=1;itext odd^m iprod_i=1;itext even^m f(i)* prod_i=1;itext even^m (63*frac32min(32,g(i))-f(i)$
Which will be odd if and only if all the $(63*frac32min(32,g(i))-f(i))$ terms are odd for all even $i$.
If $g(i) < 32$ then $(63*frac32min(32,g(i))-f(i))= 63frac 32g(i) - f(i)$ is odd. If $g(i) ge 32$ then $(63*frac32min(32,g(i))-f(i))= 63 - f(i)$ is even.
So $2015 choose m$ is odd if and only if $g(i) < 32$ for all $i le m$ if and only if $m < 32$.
answered 2 days ago
fleablood
60k22575
add a comment |Â
up vote
1
down vote
$2016 = 2^5*63$
So $2016 - j_odd*2^k= 63*2^5- j_odd*2^k$ will be divisible by $2^k$ for all $k <5$ and the terms $frac 2016-j_odd*2^k2^k=63*2^5-k - j_odd$ will all be odd.
So for any $m < 32$ then $2015 m =frac 2015*2014*2013*2012*.....(2016-m)1*2*3*4*.....*m$ will have to be odd because all the even terms $2014, 2012, 2010, .......$ (which are divisible by $2, 2^2, 2, 2^3, 2, 2^2, 2,2^4, 2, 2^2,2,2^3,2, 2^2, 2....$) are "matched up to be divided" by the even terms, $2,4,6,8,10,12,14,16,...$ which are also divisible by $2, 2^2, 2, 2^3, 2, 2^2, 2,2^4, 2, 2^2,2,2^3,2, 2^2, 2...$. So each term in the numerator divisible by a power of $2$ is in "lockstep" with a matching power of $2$ is the denominator.
$2016 -32 = 1984$ which is divisible by $32$ but because $2016 = 63*32$ that means $2016-32 = 62*32$ and as $62$ is even we have broken the lockstep and $2016-32$ is divisble not just be $32$ but by $64$.
So $2015 32 = frac 2015*2014*2013*2012*2011....... *1983*19841*2*3*4*5......*31 *32 = frac 2015*1007*2013*503*2011......*1983*621*1*3*1*5*.....*31*1$ is even.
In general if $2^k|M+1$ and $2^k+1not mid M$ then $m = 2^k$ will be the least $m$ so that $M choose m$ is even.
Because $M+1 = odd*2^k$ so $M+1 - even_k$ will be "matched" numerator to denominator to $even_k$ up to $M+1 - 2^k = (odd-1)*2^k$ which will be matched to $2^k$. $frac (odd-1)*2^k2^k = odd -1$ is even so the product is even.
=====
Okay, a more formal proof.
If $nin mathbb n$ and $n = a*2^k$ where $a$ is $odd$ and $kge 0$ then define $f(n) =a$ and $g(n) = 2^k$.
$2015 choose m =frac prod_i=1^m (2016-i)prod_i=1^m i=$
$frac prod_i=1;itext odd^m (2016-m)prod_i=1;itext even^m (2016-i)prod_i=1;itext odd^m iprod_i=1;itext even^m i=$
$frac prod_i=1;itext odd^m (2016-i)prod_i=1;itext even^m (2016-i)prod_i=1;itext odd^m iprod_i=1;itext even^m f(i)prod_i=1;itext even^m g(i)=$
$frac prod_i=1;itext odd^m (2016-i)prod_i=1;itext even^m (2016-m)prod_i=1;itext odd^m iprod_i=1;itext even^m f(i)*frac prod_i=1;itext even^m (2016-f(i)g(i))prod_i=1;itext even^m g(i)=$
$frac prod_i=1;itext odd^m (2016-i)prod_i=1;itext even^m (2016-m)prod_i=1;itext odd^m iprod_i=1;itext even^m f(i)* prod_i=1;itext even^m (63*frac32min(32,g(i))-f(i)$
Which will be odd if and only if all the $(63*frac32min(32,g(i))-f(i))$ terms are odd for all even $i$.
If $g(i) < 32$ then $(63*frac32min(32,g(i))-f(i))= 63frac 32g(i) - f(i)$ is odd. If $g(i) ge 32$ then $(63*frac32min(32,g(i))-f(i))= 63 - f(i)$ is even.
So $2015 choose m$ is odd if and only if $g(i) < 32$ for all $i le m$ if and only if $m < 32$.
answered 2 days ago
fleablood
60k22575
add a comment |Â
up vote
1
down vote
up vote
1
down vote
$2016 = 2^5*63$
So $2016 - j_odd*2^k= 63*2^5- j_odd*2^k$ will be divisible by $2^k$ for all $k <5$ and the terms $frac 2016-j_odd*2^k2^k=63*2^5-k - j_odd$ will all be odd.
So for any $m < 32$ then $2015 m =frac 2015*2014*2013*2012*.....(2016-m)1*2*3*4*.....*m$ will have to be odd because all the even terms $2014, 2012, 2010, .......$ (which are divisible by $2, 2^2, 2, 2^3, 2, 2^2, 2,2^4, 2, 2^2,2,2^3,2, 2^2, 2....$) are "matched up to be divided" by the even terms, $2,4,6,8,10,12,14,16,...$ which are also divisible by $2, 2^2, 2, 2^3, 2, 2^2, 2,2^4, 2, 2^2,2,2^3,2, 2^2, 2...$. So each term in the numerator divisible by a power of $2$ is in "lockstep" with a matching power of $2$ is the denominator.
$2016 -32 = 1984$ which is divisible by $32$ but because $2016 = 63*32$ that means $2016-32 = 62*32$ and as $62$ is even we have broken the lockstep and $2016-32$ is divisble not just be $32$ but by $64$.
So $2015 32 = frac 2015*2014*2013*2012*2011....... *1983*19841*2*3*4*5......*31 *32 = frac 2015*1007*2013*503*2011......*1983*621*1*3*1*5*.....*31*1$ is even.
In general if $2^k|M+1$ and $2^k+1not mid M$ then $m = 2^k$ will be the least $m$ so that $M choose m$ is even.
Because $M+1 = odd*2^k$ so $M+1 - even_k$ will be "matched" numerator to denominator to $even_k$ up to $M+1 - 2^k = (odd-1)*2^k$ which will be matched to $2^k$. $frac (odd-1)*2^k2^k = odd -1$ is even so the product is even.
=====
Okay, a more formal proof.
If $nin mathbb n$ and $n = a*2^k$ where $a$ is $odd$ and $kge 0$ then define $f(n) =a$ and $g(n) = 2^k$.
$2015 choose m =frac prod_i=1^m (2016-i)prod_i=1^m i=$
$frac prod_i=1;itext odd^m (2016-m)prod_i=1;itext even^m (2016-i)prod_i=1;itext odd^m iprod_i=1;itext even^m i=$
$frac prod_i=1;itext odd^m (2016-i)prod_i=1;itext even^m (2016-i)prod_i=1;itext odd^m iprod_i=1;itext even^m f(i)prod_i=1;itext even^m g(i)=$
$frac prod_i=1;itext odd^m (2016-i)prod_i=1;itext even^m (2016-m)prod_i=1;itext odd^m iprod_i=1;itext even^m f(i)*frac prod_i=1;itext even^m (2016-f(i)g(i))prod_i=1;itext even^m g(i)=$
$frac prod_i=1;itext odd^m (2016-i)prod_i=1;itext even^m (2016-m)prod_i=1;itext odd^m iprod_i=1;itext even^m f(i)* prod_i=1;itext even^m (63*frac32min(32,g(i))-f(i)$
Which will be odd if and only if all the $(63*frac32min(32,g(i))-f(i))$ terms are odd for all even $i$.
If $g(i) < 32$ then $(63*frac32min(32,g(i))-f(i))= 63frac 32g(i) - f(i)$ is odd. If $g(i) ge 32$ then $(63*frac32min(32,g(i))-f(i))= 63 - f(i)$ is even.
So $2015 choose m$ is odd if and only if $g(i) < 32$ for all $i le m$ if and only if $m < 32$.
answered 2 days ago
fleablood
60k22575
$2016 = 2^5*63$
So $2016 - j_odd*2^k= 63*2^5- j_odd*2^k$ will be divisible by $2^k$ for all $k <5$ and the terms $frac 2016-j_odd*2^k2^k=63*2^5-k - j_odd$ will all be odd.
So for any $m < 32$ then $2015 m =frac 2015*2014*2013*2012*.....(2016-m)1*2*3*4*.....*m$ will have to be odd because all the even terms $2014, 2012, 2010, .......$ (which are divisible by $2, 2^2, 2, 2^3, 2, 2^2, 2,2^4, 2, 2^2,2,2^3,2, 2^2, 2....$) are "matched up to be divided" by the even terms, $2,4,6,8,10,12,14,16,...$ which are also divisible by $2, 2^2, 2, 2^3, 2, 2^2, 2,2^4, 2, 2^2,2,2^3,2, 2^2, 2...$. So each term in the numerator divisible by a power of $2$ is in "lockstep" with a matching power of $2$ is the denominator.
$2016 -32 = 1984$ which is divisible by $32$ but because $2016 = 63*32$ that means $2016-32 = 62*32$ and as $62$ is even we have broken the lockstep and $2016-32$ is divisble not just be $32$ but by $64$.
So $2015 32 = frac 2015*2014*2013*2012*2011....... *1983*19841*2*3*4*5......*31 *32 = frac 2015*1007*2013*503*2011......*1983*621*1*3*1*5*.....*31*1$ is even.
In general if $2^k|M+1$ and $2^k+1not mid M$ then $m = 2^k$ will be the least $m$ so that $M choose m$ is even.
Because $M+1 = odd*2^k$ so $M+1 - even_k$ will be "matched" numerator to denominator to $even_k$ up to $M+1 - 2^k = (odd-1)*2^k$ which will be matched to $2^k$. $frac (odd-1)*2^k2^k = odd -1$ is even so the product is even.
=====
Okay, a more formal proof.
If $nin mathbb n$ and $n = a*2^k$ where $a$ is $odd$ and $kge 0$ then define $f(n) =a$ and $g(n) = 2^k$.
$2015 choose m =frac prod_i=1^m (2016-i)prod_i=1^m i=$
$frac prod_i=1;itext odd^m (2016-m)prod_i=1;itext even^m (2016-i)prod_i=1;itext odd^m iprod_i=1;itext even^m i=$
$frac prod_i=1;itext odd^m (2016-i)prod_i=1;itext even^m (2016-i)prod_i=1;itext odd^m iprod_i=1;itext even^m f(i)prod_i=1;itext even^m g(i)=$
$frac prod_i=1;itext odd^m (2016-i)prod_i=1;itext even^m (2016-m)prod_i=1;itext odd^m iprod_i=1;itext even^m f(i)*frac prod_i=1;itext even^m (2016-f(i)g(i))prod_i=1;itext even^m g(i)=$
$frac prod_i=1;itext odd^m (2016-i)prod_i=1;itext even^m (2016-m)prod_i=1;itext odd^m iprod_i=1;itext even^m f(i)* prod_i=1;itext even^m (63*frac32min(32,g(i))-f(i)$
Which will be odd if and only if all the $(63*frac32min(32,g(i))-f(i))$ terms are odd for all even $i$.
If $g(i) < 32$ then $(63*frac32min(32,g(i))-f(i))= 63frac 32g(i) - f(i)$ is odd. If $g(i) ge 32$ then $(63*frac32min(32,g(i))-f(i))= 63 - f(i)$ is even.
So $2015 choose m$ is odd if and only if $g(i) < 32$ for all $i le m$ if and only if $m < 32$.
answered 2 days ago
fleablood
60k22575
edited 2 days ago
answered 2 days ago
fleablood
60k22575
answered 2 days ago
fleablood
60k22575
answered 2 days ago
fleablood
60k22575
60k22575
add a comment |Â
add a comment |Â
up vote
1
down vote
for the curious, 32 is correct. Wrote a command for Legendre's rule. Now that I think about it, this leads to a method for doing this by hand, based on a proof of Legendre by induction that I once posted: http://math.stackexchange.com/questions/141196/highest-power-of-a-prime-p-dividing-n/228351#228351 Give me a few minutes. In brief,
$$ nu_p((n+1)!) = nu_p(n!) + nu_p(n+1) ; . $$
Yes. As some of the other answers have already indicated, we are searching for integer $j$ with
$$ nu_2(j+1) < nu_2(2015-j) ; , $$
after which the answer is $m=j+1.$ Then
$$ 5 = nu_2(31+1) < nu_2(2015 - 31) = nu_2(1984) = nu_2 (64 cdot 31)=6 $$
========================================================
Sat Aug 4 11:40:24 PDT 2018
1 j+1 2 2 order: 1 2015 - j 2014 order: 1
2 j+1 3 2 order: 0 2015 - j 2013 order: 0
3 j+1 4 2 order: 2 2015 - j 2012 order: 2
4 j+1 5 2 order: 0 2015 - j 2011 order: 0
5 j+1 6 2 order: 1 2015 - j 2010 order: 1
6 j+1 7 2 order: 0 2015 - j 2009 order: 0
7 j+1 8 2 order: 3 2015 - j 2008 order: 3
8 j+1 9 2 order: 0 2015 - j 2007 order: 0
9 j+1 10 2 order: 1 2015 - j 2006 order: 1
10 j+1 11 2 order: 0 2015 - j 2005 order: 0
11 j+1 12 2 order: 2 2015 - j 2004 order: 2
12 j+1 13 2 order: 0 2015 - j 2003 order: 0
13 j+1 14 2 order: 1 2015 - j 2002 order: 1
14 j+1 15 2 order: 0 2015 - j 2001 order: 0
15 j+1 16 2 order: 4 2015 - j 2000 order: 4
16 j+1 17 2 order: 0 2015 - j 1999 order: 0
17 j+1 18 2 order: 1 2015 - j 1998 order: 1
18 j+1 19 2 order: 0 2015 - j 1997 order: 0
19 j+1 20 2 order: 2 2015 - j 1996 order: 2
20 j+1 21 2 order: 0 2015 - j 1995 order: 0
21 j+1 22 2 order: 1 2015 - j 1994 order: 1
22 j+1 23 2 order: 0 2015 - j 1993 order: 0
23 j+1 24 2 order: 3 2015 - j 1992 order: 3
24 j+1 25 2 order: 0 2015 - j 1991 order: 0
25 j+1 26 2 order: 1 2015 - j 1990 order: 1
26 j+1 27 2 order: 0 2015 - j 1989 order: 0
27 j+1 28 2 order: 2 2015 - j 1988 order: 2
28 j+1 29 2 order: 0 2015 - j 1987 order: 0
29 j+1 30 2 order: 1 2015 - j 1986 order: 1
30 j+1 31 2 order: 0 2015 - j 1985 order: 0
31 j+1 32 2 order: 5 2015 - j 1984 order: 6 WOW
32 j+1 33 2 order: 0 2015 - j 1983 order: 0
33 j+1 34 2 order: 1 2015 - j 1982 order: 1
34 j+1 35 2 order: 0 2015 - j 1981 order: 0
35 j+1 36 2 order: 2 2015 - j 1980 order: 2
Sat Aug 4 11:40:24 PDT 2018
=============================================================
Sat Aug 4 10:57:09 PDT 2018
2015 two order: 2005
1 order: 0 2014 order: 2005 sum 2005
2 order: 1 2013 order: 2004 sum 2005
3 order: 1 2012 order: 2004 sum 2005
4 order: 3 2011 order: 2002 sum 2005
5 order: 3 2010 order: 2002 sum 2005
6 order: 4 2009 order: 2001 sum 2005
7 order: 4 2008 order: 2001 sum 2005
8 order: 7 2007 order: 1998 sum 2005
9 order: 7 2006 order: 1998 sum 2005
10 order: 8 2005 order: 1997 sum 2005
11 order: 8 2004 order: 1997 sum 2005
12 order: 10 2003 order: 1995 sum 2005
13 order: 10 2002 order: 1995 sum 2005
14 order: 11 2001 order: 1994 sum 2005
15 order: 11 2000 order: 1994 sum 2005
16 order: 15 1999 order: 1990 sum 2005
17 order: 15 1998 order: 1990 sum 2005
18 order: 16 1997 order: 1989 sum 2005
19 order: 16 1996 order: 1989 sum 2005
20 order: 18 1995 order: 1987 sum 2005
21 order: 18 1994 order: 1987 sum 2005
22 order: 19 1993 order: 1986 sum 2005
23 order: 19 1992 order: 1986 sum 2005
24 order: 22 1991 order: 1983 sum 2005
25 order: 22 1990 order: 1983 sum 2005
26 order: 23 1989 order: 1982 sum 2005
27 order: 23 1988 order: 1982 sum 2005
28 order: 25 1987 order: 1980 sum 2005
29 order: 25 1986 order: 1980 sum 2005
30 order: 26 1985 order: 1979 sum 2005
31 order: 26 1984 order: 1979 sum 2005
32 order: 31 1983 order: 1973 sum 2004 WOW
33 order: 31 1982 order: 1973 sum 2004 WOW
34 order: 32 1981 order: 1972 sum 2004 WOW
35 order: 32 1980 order: 1972 sum 2004 WOW
Sat Aug 4 10:57:09 PDT 2018
answered 2 days ago
Will Jagy
96.7k594195
add a comment |Â
up vote
1
down vote
for the curious, 32 is correct. Wrote a command for Legendre's rule. Now that I think about it, this leads to a method for doing this by hand, based on a proof of Legendre by induction that I once posted: http://math.stackexchange.com/questions/141196/highest-power-of-a-prime-p-dividing-n/228351#228351 Give me a few minutes. In brief,
$$ nu_p((n+1)!) = nu_p(n!) + nu_p(n+1) ; . $$
Yes. As some of the other answers have already indicated, we are searching for integer $j$ with
$$ nu_2(j+1) < nu_2(2015-j) ; , $$
after which the answer is $m=j+1.$ Then
$$ 5 = nu_2(31+1) < nu_2(2015 - 31) = nu_2(1984) = nu_2 (64 cdot 31)=6 $$
========================================================
Sat Aug 4 11:40:24 PDT 2018
1 j+1 2 2 order: 1 2015 - j 2014 order: 1
2 j+1 3 2 order: 0 2015 - j 2013 order: 0
3 j+1 4 2 order: 2 2015 - j 2012 order: 2
4 j+1 5 2 order: 0 2015 - j 2011 order: 0
5 j+1 6 2 order: 1 2015 - j 2010 order: 1
6 j+1 7 2 order: 0 2015 - j 2009 order: 0
7 j+1 8 2 order: 3 2015 - j 2008 order: 3
8 j+1 9 2 order: 0 2015 - j 2007 order: 0
9 j+1 10 2 order: 1 2015 - j 2006 order: 1
10 j+1 11 2 order: 0 2015 - j 2005 order: 0
11 j+1 12 2 order: 2 2015 - j 2004 order: 2
12 j+1 13 2 order: 0 2015 - j 2003 order: 0
13 j+1 14 2 order: 1 2015 - j 2002 order: 1
14 j+1 15 2 order: 0 2015 - j 2001 order: 0
15 j+1 16 2 order: 4 2015 - j 2000 order: 4
16 j+1 17 2 order: 0 2015 - j 1999 order: 0
17 j+1 18 2 order: 1 2015 - j 1998 order: 1
18 j+1 19 2 order: 0 2015 - j 1997 order: 0
19 j+1 20 2 order: 2 2015 - j 1996 order: 2
20 j+1 21 2 order: 0 2015 - j 1995 order: 0
21 j+1 22 2 order: 1 2015 - j 1994 order: 1
22 j+1 23 2 order: 0 2015 - j 1993 order: 0
23 j+1 24 2 order: 3 2015 - j 1992 order: 3
24 j+1 25 2 order: 0 2015 - j 1991 order: 0
25 j+1 26 2 order: 1 2015 - j 1990 order: 1
26 j+1 27 2 order: 0 2015 - j 1989 order: 0
27 j+1 28 2 order: 2 2015 - j 1988 order: 2
28 j+1 29 2 order: 0 2015 - j 1987 order: 0
29 j+1 30 2 order: 1 2015 - j 1986 order: 1
30 j+1 31 2 order: 0 2015 - j 1985 order: 0
31 j+1 32 2 order: 5 2015 - j 1984 order: 6 WOW
32 j+1 33 2 order: 0 2015 - j 1983 order: 0
33 j+1 34 2 order: 1 2015 - j 1982 order: 1
34 j+1 35 2 order: 0 2015 - j 1981 order: 0
35 j+1 36 2 order: 2 2015 - j 1980 order: 2
Sat Aug 4 11:40:24 PDT 2018
=============================================================
Sat Aug 4 10:57:09 PDT 2018
2015 two order: 2005
1 order: 0 2014 order: 2005 sum 2005
2 order: 1 2013 order: 2004 sum 2005
3 order: 1 2012 order: 2004 sum 2005
4 order: 3 2011 order: 2002 sum 2005
5 order: 3 2010 order: 2002 sum 2005
6 order: 4 2009 order: 2001 sum 2005
7 order: 4 2008 order: 2001 sum 2005
8 order: 7 2007 order: 1998 sum 2005
9 order: 7 2006 order: 1998 sum 2005
10 order: 8 2005 order: 1997 sum 2005
11 order: 8 2004 order: 1997 sum 2005
12 order: 10 2003 order: 1995 sum 2005
13 order: 10 2002 order: 1995 sum 2005
14 order: 11 2001 order: 1994 sum 2005
15 order: 11 2000 order: 1994 sum 2005
16 order: 15 1999 order: 1990 sum 2005
17 order: 15 1998 order: 1990 sum 2005
18 order: 16 1997 order: 1989 sum 2005
19 order: 16 1996 order: 1989 sum 2005
20 order: 18 1995 order: 1987 sum 2005
21 order: 18 1994 order: 1987 sum 2005
22 order: 19 1993 order: 1986 sum 2005
23 order: 19 1992 order: 1986 sum 2005
24 order: 22 1991 order: 1983 sum 2005
25 order: 22 1990 order: 1983 sum 2005
26 order: 23 1989 order: 1982 sum 2005
27 order: 23 1988 order: 1982 sum 2005
28 order: 25 1987 order: 1980 sum 2005
29 order: 25 1986 order: 1980 sum 2005
30 order: 26 1985 order: 1979 sum 2005
31 order: 26 1984 order: 1979 sum 2005
32 order: 31 1983 order: 1973 sum 2004 WOW
33 order: 31 1982 order: 1973 sum 2004 WOW
34 order: 32 1981 order: 1972 sum 2004 WOW
35 order: 32 1980 order: 1972 sum 2004 WOW
Sat Aug 4 10:57:09 PDT 2018
answered 2 days ago
Will Jagy
96.7k594195
add a comment |Â
up vote
1
down vote
up vote
1
down vote
for the curious, 32 is correct. Wrote a command for Legendre's rule. Now that I think about it, this leads to a method for doing this by hand, based on a proof of Legendre by induction that I once posted: http://math.stackexchange.com/questions/141196/highest-power-of-a-prime-p-dividing-n/228351#228351 Give me a few minutes. In brief,
$$ nu_p((n+1)!) = nu_p(n!) + nu_p(n+1) ; . $$
Yes. As some of the other answers have already indicated, we are searching for integer $j$ with
$$ nu_2(j+1) < nu_2(2015-j) ; , $$
after which the answer is $m=j+1.$ Then
$$ 5 = nu_2(31+1) < nu_2(2015 - 31) = nu_2(1984) = nu_2 (64 cdot 31)=6 $$
========================================================
Sat Aug 4 11:40:24 PDT 2018
1 j+1 2 2 order: 1 2015 - j 2014 order: 1
2 j+1 3 2 order: 0 2015 - j 2013 order: 0
3 j+1 4 2 order: 2 2015 - j 2012 order: 2
4 j+1 5 2 order: 0 2015 - j 2011 order: 0
5 j+1 6 2 order: 1 2015 - j 2010 order: 1
6 j+1 7 2 order: 0 2015 - j 2009 order: 0
7 j+1 8 2 order: 3 2015 - j 2008 order: 3
8 j+1 9 2 order: 0 2015 - j 2007 order: 0
9 j+1 10 2 order: 1 2015 - j 2006 order: 1
10 j+1 11 2 order: 0 2015 - j 2005 order: 0
11 j+1 12 2 order: 2 2015 - j 2004 order: 2
12 j+1 13 2 order: 0 2015 - j 2003 order: 0
13 j+1 14 2 order: 1 2015 - j 2002 order: 1
14 j+1 15 2 order: 0 2015 - j 2001 order: 0
15 j+1 16 2 order: 4 2015 - j 2000 order: 4
16 j+1 17 2 order: 0 2015 - j 1999 order: 0
17 j+1 18 2 order: 1 2015 - j 1998 order: 1
18 j+1 19 2 order: 0 2015 - j 1997 order: 0
19 j+1 20 2 order: 2 2015 - j 1996 order: 2
20 j+1 21 2 order: 0 2015 - j 1995 order: 0
21 j+1 22 2 order: 1 2015 - j 1994 order: 1
22 j+1 23 2 order: 0 2015 - j 1993 order: 0
23 j+1 24 2 order: 3 2015 - j 1992 order: 3
24 j+1 25 2 order: 0 2015 - j 1991 order: 0
25 j+1 26 2 order: 1 2015 - j 1990 order: 1
26 j+1 27 2 order: 0 2015 - j 1989 order: 0
27 j+1 28 2 order: 2 2015 - j 1988 order: 2
28 j+1 29 2 order: 0 2015 - j 1987 order: 0
29 j+1 30 2 order: 1 2015 - j 1986 order: 1
30 j+1 31 2 order: 0 2015 - j 1985 order: 0
31 j+1 32 2 order: 5 2015 - j 1984 order: 6 WOW
32 j+1 33 2 order: 0 2015 - j 1983 order: 0
33 j+1 34 2 order: 1 2015 - j 1982 order: 1
34 j+1 35 2 order: 0 2015 - j 1981 order: 0
35 j+1 36 2 order: 2 2015 - j 1980 order: 2
Sat Aug 4 11:40:24 PDT 2018
=============================================================
Sat Aug 4 10:57:09 PDT 2018
2015 two order: 2005
1 order: 0 2014 order: 2005 sum 2005
2 order: 1 2013 order: 2004 sum 2005
3 order: 1 2012 order: 2004 sum 2005
4 order: 3 2011 order: 2002 sum 2005
5 order: 3 2010 order: 2002 sum 2005
6 order: 4 2009 order: 2001 sum 2005
7 order: 4 2008 order: 2001 sum 2005
8 order: 7 2007 order: 1998 sum 2005
9 order: 7 2006 order: 1998 sum 2005
10 order: 8 2005 order: 1997 sum 2005
11 order: 8 2004 order: 1997 sum 2005
12 order: 10 2003 order: 1995 sum 2005
13 order: 10 2002 order: 1995 sum 2005
14 order: 11 2001 order: 1994 sum 2005
15 order: 11 2000 order: 1994 sum 2005
16 order: 15 1999 order: 1990 sum 2005
17 order: 15 1998 order: 1990 sum 2005
18 order: 16 1997 order: 1989 sum 2005
19 order: 16 1996 order: 1989 sum 2005
20 order: 18 1995 order: 1987 sum 2005
21 order: 18 1994 order: 1987 sum 2005
22 order: 19 1993 order: 1986 sum 2005
23 order: 19 1992 order: 1986 sum 2005
24 order: 22 1991 order: 1983 sum 2005
25 order: 22 1990 order: 1983 sum 2005
26 order: 23 1989 order: 1982 sum 2005
27 order: 23 1988 order: 1982 sum 2005
28 order: 25 1987 order: 1980 sum 2005
29 order: 25 1986 order: 1980 sum 2005
30 order: 26 1985 order: 1979 sum 2005
31 order: 26 1984 order: 1979 sum 2005
32 order: 31 1983 order: 1973 sum 2004 WOW
33 order: 31 1982 order: 1973 sum 2004 WOW
34 order: 32 1981 order: 1972 sum 2004 WOW
35 order: 32 1980 order: 1972 sum 2004 WOW
Sat Aug 4 10:57:09 PDT 2018
answered 2 days ago
Will Jagy
96.7k594195
for the curious, 32 is correct. Wrote a command for Legendre's rule. Now that I think about it, this leads to a method for doing this by hand, based on a proof of Legendre by induction that I once posted: http://math.stackexchange.com/questions/141196/highest-power-of-a-prime-p-dividing-n/228351#228351 Give me a few minutes. In brief,
$$ nu_p((n+1)!) = nu_p(n!) + nu_p(n+1) ; . $$
Yes. As some of the other answers have already indicated, we are searching for integer $j$ with
$$ nu_2(j+1) < nu_2(2015-j) ; , $$
after which the answer is $m=j+1.$ Then
$$ 5 = nu_2(31+1) < nu_2(2015 - 31) = nu_2(1984) = nu_2 (64 cdot 31)=6 $$
========================================================
Sat Aug 4 11:40:24 PDT 2018
1 j+1 2 2 order: 1 2015 - j 2014 order: 1
2 j+1 3 2 order: 0 2015 - j 2013 order: 0
3 j+1 4 2 order: 2 2015 - j 2012 order: 2
4 j+1 5 2 order: 0 2015 - j 2011 order: 0
5 j+1 6 2 order: 1 2015 - j 2010 order: 1
6 j+1 7 2 order: 0 2015 - j 2009 order: 0
7 j+1 8 2 order: 3 2015 - j 2008 order: 3
8 j+1 9 2 order: 0 2015 - j 2007 order: 0
9 j+1 10 2 order: 1 2015 - j 2006 order: 1
10 j+1 11 2 order: 0 2015 - j 2005 order: 0
11 j+1 12 2 order: 2 2015 - j 2004 order: 2
12 j+1 13 2 order: 0 2015 - j 2003 order: 0
13 j+1 14 2 order: 1 2015 - j 2002 order: 1
14 j+1 15 2 order: 0 2015 - j 2001 order: 0
15 j+1 16 2 order: 4 2015 - j 2000 order: 4
16 j+1 17 2 order: 0 2015 - j 1999 order: 0
17 j+1 18 2 order: 1 2015 - j 1998 order: 1
18 j+1 19 2 order: 0 2015 - j 1997 order: 0
19 j+1 20 2 order: 2 2015 - j 1996 order: 2
20 j+1 21 2 order: 0 2015 - j 1995 order: 0
21 j+1 22 2 order: 1 2015 - j 1994 order: 1
22 j+1 23 2 order: 0 2015 - j 1993 order: 0
23 j+1 24 2 order: 3 2015 - j 1992 order: 3
24 j+1 25 2 order: 0 2015 - j 1991 order: 0
25 j+1 26 2 order: 1 2015 - j 1990 order: 1
26 j+1 27 2 order: 0 2015 - j 1989 order: 0
27 j+1 28 2 order: 2 2015 - j 1988 order: 2
28 j+1 29 2 order: 0 2015 - j 1987 order: 0
29 j+1 30 2 order: 1 2015 - j 1986 order: 1
30 j+1 31 2 order: 0 2015 - j 1985 order: 0
31 j+1 32 2 order: 5 2015 - j 1984 order: 6 WOW
32 j+1 33 2 order: 0 2015 - j 1983 order: 0
33 j+1 34 2 order: 1 2015 - j 1982 order: 1
34 j+1 35 2 order: 0 2015 - j 1981 order: 0
35 j+1 36 2 order: 2 2015 - j 1980 order: 2
Sat Aug 4 11:40:24 PDT 2018
=============================================================
Sat Aug 4 10:57:09 PDT 2018
2015 two order: 2005
1 order: 0 2014 order: 2005 sum 2005
2 order: 1 2013 order: 2004 sum 2005
3 order: 1 2012 order: 2004 sum 2005
4 order: 3 2011 order: 2002 sum 2005
5 order: 3 2010 order: 2002 sum 2005
6 order: 4 2009 order: 2001 sum 2005
7 order: 4 2008 order: 2001 sum 2005
8 order: 7 2007 order: 1998 sum 2005
9 order: 7 2006 order: 1998 sum 2005
10 order: 8 2005 order: 1997 sum 2005
11 order: 8 2004 order: 1997 sum 2005
12 order: 10 2003 order: 1995 sum 2005
13 order: 10 2002 order: 1995 sum 2005
14 order: 11 2001 order: 1994 sum 2005
15 order: 11 2000 order: 1994 sum 2005
16 order: 15 1999 order: 1990 sum 2005
17 order: 15 1998 order: 1990 sum 2005
18 order: 16 1997 order: 1989 sum 2005
19 order: 16 1996 order: 1989 sum 2005
20 order: 18 1995 order: 1987 sum 2005
21 order: 18 1994 order: 1987 sum 2005
22 order: 19 1993 order: 1986 sum 2005
23 order: 19 1992 order: 1986 sum 2005
24 order: 22 1991 order: 1983 sum 2005
25 order: 22 1990 order: 1983 sum 2005
26 order: 23 1989 order: 1982 sum 2005
27 order: 23 1988 order: 1982 sum 2005
28 order: 25 1987 order: 1980 sum 2005
29 order: 25 1986 order: 1980 sum 2005
30 order: 26 1985 order: 1979 sum 2005
31 order: 26 1984 order: 1979 sum 2005
32 order: 31 1983 order: 1973 sum 2004 WOW
33 order: 31 1982 order: 1973 sum 2004 WOW
34 order: 32 1981 order: 1972 sum 2004 WOW
35 order: 32 1980 order: 1972 sum 2004 WOW
Sat Aug 4 10:57:09 PDT 2018
answered 2 days ago
Will Jagy
96.7k594195
edited yesterday
answered 2 days ago
Will Jagy
96.7k594195
answered 2 days ago
Will Jagy
96.7k594195
answered 2 days ago
Will Jagy
96.7k594195
96.7k594195
add a comment |Â
add a comment |Â
up vote
0
down vote
We want to find the smallest positive integer $m$ such that $2015 choose m$ is an even number.
As you show, $2015 choose m = frac20151cdot frac20142cdotdots cdotfrac2016-mm$.
The question then becomes finding the smallest positive integer $m$ such that $frac2016-mm$ is even. However we see that $frac2016-mm = frac2016m - 1$, so we want $frac2016m$ to be odd.
Since $32$ is the largest power of $2$ dividing 2016, we must divide out $32$ for this to be odd.
Hence, $m=32$.
answered 2 days ago
Sodium Or
192
1
(-1) Why should $frac2016-mm$ be an integer?
– Arnaud Mortier
2 days ago
$2015choose 4 = frac 20151frac 20142 frac 20133frac 20124 = frac 20151*1007*frac 20133*503 = 2015*1007*671*503$ is odd.
– fleablood
2 days ago
@fleablood ?? When did I say m=4?
– Sodium Or
2 days ago
2
Are you seriously going to play it like that when the history of your edits is available for everyone to see? ..... "When did I say m=4?" ..... At 9:48 Aug 4, 2018 PDT.
– fleablood
2 days ago
@fleablood that edit was made 20 minutes before your comment...
– Sodium Or
2 days ago
 |Â
show 2 more comments
up vote
0
down vote
We want to find the smallest positive integer $m$ such that $2015 choose m$ is an even number.
As you show, $2015 choose m = frac20151cdot frac20142cdotdots cdotfrac2016-mm$.
The question then becomes finding the smallest positive integer $m$ such that $frac2016-mm$ is even. However we see that $frac2016-mm = frac2016m - 1$, so we want $frac2016m$ to be odd.
Since $32$ is the largest power of $2$ dividing 2016, we must divide out $32$ for this to be odd.
Hence, $m=32$.
answered 2 days ago
Sodium Or
192
1
(-1) Why should $frac2016-mm$ be an integer?
– Arnaud Mortier
2 days ago
$2015choose 4 = frac 20151frac 20142 frac 20133frac 20124 = frac 20151*1007*frac 20133*503 = 2015*1007*671*503$ is odd.
– fleablood
2 days ago
@fleablood ?? When did I say m=4?
– Sodium Or
2 days ago
2
Are you seriously going to play it like that when the history of your edits is available for everyone to see? ..... "When did I say m=4?" ..... At 9:48 Aug 4, 2018 PDT.
– fleablood
2 days ago
@fleablood that edit was made 20 minutes before your comment...
– Sodium Or
2 days ago
 |Â
show 2 more comments
up vote
0
down vote
up vote
0
down vote
We want to find the smallest positive integer $m$ such that $2015 choose m$ is an even number.
As you show, $2015 choose m = frac20151cdot frac20142cdotdots cdotfrac2016-mm$.
The question then becomes finding the smallest positive integer $m$ such that $frac2016-mm$ is even. However we see that $frac2016-mm = frac2016m - 1$, so we want $frac2016m$ to be odd.
Since $32$ is the largest power of $2$ dividing 2016, we must divide out $32$ for this to be odd.
Hence, $m=32$.
answered 2 days ago
Sodium Or
192
We want to find the smallest positive integer $m$ such that $2015 choose m$ is an even number.
As you show, $2015 choose m = frac20151cdot frac20142cdotdots cdotfrac2016-mm$.
The question then becomes finding the smallest positive integer $m$ such that $frac2016-mm$ is even. However we see that $frac2016-mm = frac2016m - 1$, so we want $frac2016m$ to be odd.
Since $32$ is the largest power of $2$ dividing 2016, we must divide out $32$ for this to be odd.
Hence, $m=32$.
answered 2 days ago
Sodium Or
192
edited 2 days ago
answered 2 days ago
Sodium Or
192
answered 2 days ago
Sodium Or
192
answered 2 days ago
Sodium Or
192
192
1
(-1) Why should $frac2016-mm$ be an integer?
– Arnaud Mortier
2 days ago
$2015choose 4 = frac 20151frac 20142 frac 20133frac 20124 = frac 20151*1007*frac 20133*503 = 2015*1007*671*503$ is odd.
– fleablood
2 days ago
@fleablood ?? When did I say m=4?
– Sodium Or
2 days ago
2
Are you seriously going to play it like that when the history of your edits is available for everyone to see? ..... "When did I say m=4?" ..... At 9:48 Aug 4, 2018 PDT.
– fleablood
2 days ago
@fleablood that edit was made 20 minutes before your comment...
– Sodium Or
2 days ago
 |Â
show 2 more comments
1
(-1) Why should $frac2016-mm$ be an integer?
– Arnaud Mortier
2 days ago
$2015choose 4 = frac 20151frac 20142 frac 20133frac 20124 = frac 20151*1007*frac 20133*503 = 2015*1007*671*503$ is odd.
– fleablood
2 days ago
@fleablood ?? When did I say m=4?
– Sodium Or
2 days ago
2
Are you seriously going to play it like that when the history of your edits is available for everyone to see? ..... "When did I say m=4?" ..... At 9:48 Aug 4, 2018 PDT.
– fleablood
2 days ago
@fleablood that edit was made 20 minutes before your comment...
– Sodium Or
2 days ago
1
1
(-1) Why should $frac2016-mm$ be an integer?
– Arnaud Mortier
2 days ago
(-1) Why should $frac2016-mm$ be an integer?
– Arnaud Mortier
2 days ago
$2015choose 4 = frac 20151frac 20142 frac 20133frac 20124 = frac 20151*1007*frac 20133*503 = 2015*1007*671*503$ is odd.
– fleablood
2 days ago
$2015choose 4 = frac 20151frac 20142 frac 20133frac 20124 = frac 20151*1007*frac 20133*503 = 2015*1007*671*503$ is odd.
– fleablood
2 days ago
@fleablood ?? When did I say m=4?
– Sodium Or
2 days ago
@fleablood ?? When did I say m=4?
– Sodium Or
2 days ago
2
2
Are you seriously going to play it like that when the history of your edits is available for everyone to see? ..... "When did I say m=4?" ..... At 9:48 Aug 4, 2018 PDT.
– fleablood
2 days ago
Are you seriously going to play it like that when the history of your edits is available for everyone to see? ..... "When did I say m=4?" ..... At 9:48 Aug 4, 2018 PDT.
– fleablood
2 days ago
@fleablood that edit was made 20 minutes before your comment...
– Sodium Or
2 days ago
@fleablood that edit was made 20 minutes before your comment...
– Sodium Or
2 days ago
 |Â
show 2 more comments
up vote
0
down vote
$n = 2015_10 = 11111011111_2$ and from Luca's theorem:
$$2015 choose m = prod_i=0^10 n_i choose m_i pmod 2$$
where all factors are always $1$ except for $0 choose m_5$ which is $0$ if and only if $m_5 = 1$.
The smallest number having $m_5 = 1$ is $32$.
Generally speaking $n choose m$ is odd if and only if $m land n = m$, and even otherwise, where $land$ is meant here as a bitwise operation on binary digits. In other words $n choose m$ is odd if and only if all $1$s in $m$ are $1$ also in $n$.
answered 10 hours ago
mbjoe
135
add a comment |Â
up vote
0
down vote
$n = 2015_10 = 11111011111_2$ and from Luca's theorem:
$$2015 choose m = prod_i=0^10 n_i choose m_i pmod 2$$
where all factors are always $1$ except for $0 choose m_5$ which is $0$ if and only if $m_5 = 1$.
The smallest number having $m_5 = 1$ is $32$.
Generally speaking $n choose m$ is odd if and only if $m land n = m$, and even otherwise, where $land$ is meant here as a bitwise operation on binary digits. In other words $n choose m$ is odd if and only if all $1$s in $m$ are $1$ also in $n$.
answered 10 hours ago
mbjoe
135
add a comment |Â
up vote
0
down vote
up vote
0
down vote
$n = 2015_10 = 11111011111_2$ and from Luca's theorem:
$$2015 choose m = prod_i=0^10 n_i choose m_i pmod 2$$
where all factors are always $1$ except for $0 choose m_5$ which is $0$ if and only if $m_5 = 1$.
The smallest number having $m_5 = 1$ is $32$.
Generally speaking $n choose m$ is odd if and only if $m land n = m$, and even otherwise, where $land$ is meant here as a bitwise operation on binary digits. In other words $n choose m$ is odd if and only if all $1$s in $m$ are $1$ also in $n$.
answered 10 hours ago
mbjoe
135
$n = 2015_10 = 11111011111_2$ and from Luca's theorem:
$$2015 choose m = prod_i=0^10 n_i choose m_i pmod 2$$
where all factors are always $1$ except for $0 choose m_5$ which is $0$ if and only if $m_5 = 1$.
The smallest number having $m_5 = 1$ is $32$.
Generally speaking $n choose m$ is odd if and only if $m land n = m$, and even otherwise, where $land$ is meant here as a bitwise operation on binary digits. In other words $n choose m$ is odd if and only if all $1$s in $m$ are $1$ also in $n$.
answered 10 hours ago
mbjoe
135
answered 10 hours ago
mbjoe
135
answered 10 hours ago
mbjoe
135
answered 10 hours ago
mbjoe
135
135
add a comment |Â
add a comment |Â
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fmath.stackexchange.com%2fquestions%2f2872183%2ffind-the-smallest-positive-integer-m-such-that-2015-choosem-is-an-even%23new-answer', 'question_page');
);
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Post as a guest
Sign up or log in
StackExchange.ready(function ()
StackExchange.helpers.onClickDraftSave('#login-link');
);
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Sign up using Google
Sign up using Facebook
Sign up using Email and Password
Possibly helpful, possible duplicate: math.stackexchange.com/questions/233269/…
– Ethan Bolker
2 days ago
That's the way I would use, you already have an approach that is optimal in many ways.
– Arnaud Mortier
2 days ago