Mixing
sum of integers using order of integers and primitive roots
Clash Royale CLAN TAG#URR8PPP
up vote
2
down vote
favorite
Sorry for my interruption, I am looking for a solution to this question: Calculate
$$sum_k=0^2001left lfloor frac2^k2003right rfloor$$ without using computational engines, with $lfloor x rfloor$ denoting the largest integer that does not succeed x. I hope you can answer this question. And sorry for my mistakes, English is my second language.
number-theory elementary-number-theory
edited Jul 22 at 14:23
Botond
3,8432632
asked Jul 22 at 13:45
Mathwriter
265
 |Â
show 3 more comments
up vote
2
down vote
favorite
Sorry for my interruption, I am looking for a solution to this question: Calculate
$$sum_k=0^2001left lfloor frac2^k2003right rfloor$$ without using computational engines, with $lfloor x rfloor$ denoting the largest integer that does not succeed x. I hope you can answer this question. And sorry for my mistakes, English is my second language.
number-theory elementary-number-theory
edited Jul 22 at 14:23
Botond
3,8432632
asked Jul 22 at 13:45
Mathwriter
265
Note: I changed your notation for the floor function. These days, I think it is more common to write $lfloor x rfloor$ for the floor, and $lceil x rceil$ for the ceiling (the least integer which is not less than $x$). If you prefer the other notation, please change it back.
– lulu
Jul 22 at 13:51
For what it's worth: a (forbidden) computer calculation yields a formidable answer which this comment section is too small to allow me to reprint. This leads me to doubt that there is a terribly quick method, but who knows?
– lulu
Jul 22 at 13:54
Dear lulu, thank you for correcting my mistakes. I am not familiar with LaTex codes, so I appreciated your help. Sincerely.
– Mathwriter
Jul 22 at 13:55
No problem, and I wouldn't really call it a mistake. The notation you used was entirely standard not all that long ago, but I think the newer notation is better (as it lets us get at both floors and ceilings.
– lulu
Jul 22 at 13:56
Entertainingly, the computed result is exactly the maximum number of characters the comments will allow...I can't even add the usual dollar signs to get the typeface right. I'll post the computed solution in the next comment. I think you'll agree that, at least in that form, it's hard to imagine an easy argument. Of course it may be that this mess admits a nice interpretation, as a sum or difference of simply described exponents or such.
– lulu
Jul 22 at 13:57
 |Â
show 3 more comments
up vote
2
down vote
favorite
up vote
2
down vote
favorite
Sorry for my interruption, I am looking for a solution to this question: Calculate
$$sum_k=0^2001left lfloor frac2^k2003right rfloor$$ without using computational engines, with $lfloor x rfloor$ denoting the largest integer that does not succeed x. I hope you can answer this question. And sorry for my mistakes, English is my second language.
number-theory elementary-number-theory
edited Jul 22 at 14:23
Botond
3,8432632
asked Jul 22 at 13:45
Mathwriter
265
Sorry for my interruption, I am looking for a solution to this question: Calculate
$$sum_k=0^2001left lfloor frac2^k2003right rfloor$$ without using computational engines, with $lfloor x rfloor$ denoting the largest integer that does not succeed x. I hope you can answer this question. And sorry for my mistakes, English is my second language.
number-theory elementary-number-theory
edited Jul 22 at 14:23
Botond
3,8432632
asked Jul 22 at 13:45
Mathwriter
265
edited Jul 22 at 14:23
Botond
3,8432632
edited Jul 22 at 14:23
Botond
3,8432632
edited Jul 22 at 14:23
Botond
3,8432632
3,8432632
asked Jul 22 at 13:45
Mathwriter
265
asked Jul 22 at 13:45
Mathwriter
265
asked Jul 22 at 13:45
Mathwriter
265
265
Note: I changed your notation for the floor function. These days, I think it is more common to write $lfloor x rfloor$ for the floor, and $lceil x rceil$ for the ceiling (the least integer which is not less than $x$). If you prefer the other notation, please change it back.
– lulu
Jul 22 at 13:51
For what it's worth: a (forbidden) computer calculation yields a formidable answer which this comment section is too small to allow me to reprint. This leads me to doubt that there is a terribly quick method, but who knows?
– lulu
Jul 22 at 13:54
Dear lulu, thank you for correcting my mistakes. I am not familiar with LaTex codes, so I appreciated your help. Sincerely.
– Mathwriter
Jul 22 at 13:55
No problem, and I wouldn't really call it a mistake. The notation you used was entirely standard not all that long ago, but I think the newer notation is better (as it lets us get at both floors and ceilings.
– lulu
Jul 22 at 13:56
Entertainingly, the computed result is exactly the maximum number of characters the comments will allow...I can't even add the usual dollar signs to get the typeface right. I'll post the computed solution in the next comment. I think you'll agree that, at least in that form, it's hard to imagine an easy argument. Of course it may be that this mess admits a nice interpretation, as a sum or difference of simply described exponents or such.
– lulu
Jul 22 at 13:57
 |Â
show 3 more comments
Note: I changed your notation for the floor function. These days, I think it is more common to write $lfloor x rfloor$ for the floor, and $lceil x rceil$ for the ceiling (the least integer which is not less than $x$). If you prefer the other notation, please change it back.
– lulu
Jul 22 at 13:51
For what it's worth: a (forbidden) computer calculation yields a formidable answer which this comment section is too small to allow me to reprint. This leads me to doubt that there is a terribly quick method, but who knows?
– lulu
Jul 22 at 13:54
Dear lulu, thank you for correcting my mistakes. I am not familiar with LaTex codes, so I appreciated your help. Sincerely.
– Mathwriter
Jul 22 at 13:55
No problem, and I wouldn't really call it a mistake. The notation you used was entirely standard not all that long ago, but I think the newer notation is better (as it lets us get at both floors and ceilings.
– lulu
Jul 22 at 13:56
Entertainingly, the computed result is exactly the maximum number of characters the comments will allow...I can't even add the usual dollar signs to get the typeface right. I'll post the computed solution in the next comment. I think you'll agree that, at least in that form, it's hard to imagine an easy argument. Of course it may be that this mess admits a nice interpretation, as a sum or difference of simply described exponents or such.
– lulu
Jul 22 at 13:57
Note: I changed your notation for the floor function. These days, I think it is more common to write $lfloor x rfloor$ for the floor, and $lceil x rceil$ for the ceiling (the least integer which is not less than $x$). If you prefer the other notation, please change it back.
– lulu
Jul 22 at 13:51
Note: I changed your notation for the floor function. These days, I think it is more common to write $lfloor x rfloor$ for the floor, and $lceil x rceil$ for the ceiling (the least integer which is not less than $x$). If you prefer the other notation, please change it back.
– lulu
Jul 22 at 13:51
For what it's worth: a (forbidden) computer calculation yields a formidable answer which this comment section is too small to allow me to reprint. This leads me to doubt that there is a terribly quick method, but who knows?
– lulu
Jul 22 at 13:54
For what it's worth: a (forbidden) computer calculation yields a formidable answer which this comment section is too small to allow me to reprint. This leads me to doubt that there is a terribly quick method, but who knows?
– lulu
Jul 22 at 13:54
Dear lulu, thank you for correcting my mistakes. I am not familiar with LaTex codes, so I appreciated your help. Sincerely.
– Mathwriter
Jul 22 at 13:55
Dear lulu, thank you for correcting my mistakes. I am not familiar with LaTex codes, so I appreciated your help. Sincerely.
– Mathwriter
Jul 22 at 13:55
No problem, and I wouldn't really call it a mistake. The notation you used was entirely standard not all that long ago, but I think the newer notation is better (as it lets us get at both floors and ceilings.
– lulu
Jul 22 at 13:56
No problem, and I wouldn't really call it a mistake. The notation you used was entirely standard not all that long ago, but I think the newer notation is better (as it lets us get at both floors and ceilings.
– lulu
Jul 22 at 13:56
Entertainingly, the computed result is exactly the maximum number of characters the comments will allow...I can't even add the usual dollar signs to get the typeface right. I'll post the computed solution in the next comment. I think you'll agree that, at least in that form, it's hard to imagine an easy argument. Of course it may be that this mess admits a nice interpretation, as a sum or difference of simply described exponents or such.
– lulu
Jul 22 at 13:57
Entertainingly, the computed result is exactly the maximum number of characters the comments will allow...I can't even add the usual dollar signs to get the typeface right. I'll post the computed solution in the next comment. I think you'll agree that, at least in that form, it's hard to imagine an easy argument. Of course it may be that this mess admits a nice interpretation, as a sum or difference of simply described exponents or such.
– lulu
Jul 22 at 13:57
 |Â
show 3 more comments
2 Answers
2
active
oldest
votes
up vote
4
down vote
accepted
If we write $2^k=2003q_k+r_k$ you are looking for the sum of the $q_k$. Assume for the moment that we know that $2$ is a primitive root $bmod 2003$. In that case the $r_k$ run through all the numbers from $1$ through $2002$ and we can write
$$sum_k=0^2001Big lfloor frac2^k2003Big rfloor=sum_k=0^2001 frac 2^k-r_k2003=frac 2^2002-12003-frac 2002cdot 20032cdot 2003=frac 2^2002-12003-1001$$
This gives an explicit expression without summation or floor functions, but actually computing it is beyond most of our patience as it will have about $600$ digits.
I don't have an easy way to show $2$ is a primitive root. The order of $2$ must divide $2002=2cdot7cdot 11 cdot 13$ so we can just check whether $2$ to any of $14$ powers is equivalent to $1 bmod 2003$. You can generate $2^2^n$ by repeated squaring and then multiply them, but it will be tedious.
I realized that all that is needed for this argument to work is to show $2^1001equiv -1 pmod 2003$, which will be true if $2$ is a primitive root but might be otherwise. With repeated squaring that is more within the range of hand computation, but still tedious.
answered Jul 22 at 14:18
Ross Millikan
276k21186352
Dear Ross Millikan. Thank you for your answer! However 2 is not a primitive root of 2003. In fact order of 2 mod 2003 is actualy 286?. But I understand your idea and I appreciated your help. Sincerely.
– Mathwriter
Jul 22 at 15:58
@Mathwriter: when I see a problem like this I try to find ways to bring the calculation into a range of what is reasonable. Probably knowing that $2$ is not a primitive root $bmod 7$ should have tipped me off. The fact that it is not primitive may change the $1001$ that is subtracted a bit.
– Ross Millikan
Jul 22 at 17:00
@Mathwriter: the fact that $2$ is not a primitive root can change the $1001$ term in my expression, but not by much. Most of the digits of the answer will be correct.
– Ross Millikan
Jul 23 at 14:51
Thanks, but can you give the explicit expression?
– Mathwriter
Jul 23 at 15:11
It is just six times the sum of all the powers of $2$ $pmod 2003$divided by $2003$. Six comes from $2003/286=6$ so you go around six times.
– Ross Millikan
Jul 23 at 15:26
 |Â
show 4 more comments
up vote
0
down vote
Solution from a friend of mine: Since $$2^1001=-1(mod 2003) $$ then $$ 2^1001 + i + 2^i = 0 (mod 2003),$$ thus $$ left lfloorfrac2^1001 + i2003right rfloor + left lfloorfrac2^i2003right rfloor = frac2^1001 + i + 2^i2003 - 1,$$ therefore $$sum_k=0^2001Big lfloor frac2^k2003Big rfloor=frac 2^2002-12003-1001$$
answered Jul 24 at 11:11
Mathwriter
265
I had said that $2^1001equiv -1 bmod 2003$ was enough to show the subtraction was $1001$. I just realized that if you know the order of $2$ is $286$ the fact that $2002/286=7$ it is enough to show this. I don't know how to prove that without direct computation.
– Ross Millikan
Jul 24 at 13:55
add a comment |Â
2 Answers
2
active
oldest
votes
2 Answers
2
active
oldest
votes
active
oldest
votes
active
oldest
votes
up vote
4
down vote
accepted
If we write $2^k=2003q_k+r_k$ you are looking for the sum of the $q_k$. Assume for the moment that we know that $2$ is a primitive root $bmod 2003$. In that case the $r_k$ run through all the numbers from $1$ through $2002$ and we can write
$$sum_k=0^2001Big lfloor frac2^k2003Big rfloor=sum_k=0^2001 frac 2^k-r_k2003=frac 2^2002-12003-frac 2002cdot 20032cdot 2003=frac 2^2002-12003-1001$$
This gives an explicit expression without summation or floor functions, but actually computing it is beyond most of our patience as it will have about $600$ digits.
I don't have an easy way to show $2$ is a primitive root. The order of $2$ must divide $2002=2cdot7cdot 11 cdot 13$ so we can just check whether $2$ to any of $14$ powers is equivalent to $1 bmod 2003$. You can generate $2^2^n$ by repeated squaring and then multiply them, but it will be tedious.
I realized that all that is needed for this argument to work is to show $2^1001equiv -1 pmod 2003$, which will be true if $2$ is a primitive root but might be otherwise. With repeated squaring that is more within the range of hand computation, but still tedious.
answered Jul 22 at 14:18
Ross Millikan
276k21186352
Dear Ross Millikan. Thank you for your answer! However 2 is not a primitive root of 2003. In fact order of 2 mod 2003 is actualy 286?. But I understand your idea and I appreciated your help. Sincerely.
– Mathwriter
Jul 22 at 15:58
@Mathwriter: when I see a problem like this I try to find ways to bring the calculation into a range of what is reasonable. Probably knowing that $2$ is not a primitive root $bmod 7$ should have tipped me off. The fact that it is not primitive may change the $1001$ that is subtracted a bit.
– Ross Millikan
Jul 22 at 17:00
@Mathwriter: the fact that $2$ is not a primitive root can change the $1001$ term in my expression, but not by much. Most of the digits of the answer will be correct.
– Ross Millikan
Jul 23 at 14:51
Thanks, but can you give the explicit expression?
– Mathwriter
Jul 23 at 15:11
It is just six times the sum of all the powers of $2$ $pmod 2003$divided by $2003$. Six comes from $2003/286=6$ so you go around six times.
– Ross Millikan
Jul 23 at 15:26
 |Â
show 4 more comments
up vote
4
down vote
accepted
If we write $2^k=2003q_k+r_k$ you are looking for the sum of the $q_k$. Assume for the moment that we know that $2$ is a primitive root $bmod 2003$. In that case the $r_k$ run through all the numbers from $1$ through $2002$ and we can write
$$sum_k=0^2001Big lfloor frac2^k2003Big rfloor=sum_k=0^2001 frac 2^k-r_k2003=frac 2^2002-12003-frac 2002cdot 20032cdot 2003=frac 2^2002-12003-1001$$
This gives an explicit expression without summation or floor functions, but actually computing it is beyond most of our patience as it will have about $600$ digits.
I don't have an easy way to show $2$ is a primitive root. The order of $2$ must divide $2002=2cdot7cdot 11 cdot 13$ so we can just check whether $2$ to any of $14$ powers is equivalent to $1 bmod 2003$. You can generate $2^2^n$ by repeated squaring and then multiply them, but it will be tedious.
I realized that all that is needed for this argument to work is to show $2^1001equiv -1 pmod 2003$, which will be true if $2$ is a primitive root but might be otherwise. With repeated squaring that is more within the range of hand computation, but still tedious.
answered Jul 22 at 14:18
Ross Millikan
276k21186352
Dear Ross Millikan. Thank you for your answer! However 2 is not a primitive root of 2003. In fact order of 2 mod 2003 is actualy 286?. But I understand your idea and I appreciated your help. Sincerely.
– Mathwriter
Jul 22 at 15:58
@Mathwriter: when I see a problem like this I try to find ways to bring the calculation into a range of what is reasonable. Probably knowing that $2$ is not a primitive root $bmod 7$ should have tipped me off. The fact that it is not primitive may change the $1001$ that is subtracted a bit.
– Ross Millikan
Jul 22 at 17:00
@Mathwriter: the fact that $2$ is not a primitive root can change the $1001$ term in my expression, but not by much. Most of the digits of the answer will be correct.
– Ross Millikan
Jul 23 at 14:51
Thanks, but can you give the explicit expression?
– Mathwriter
Jul 23 at 15:11
It is just six times the sum of all the powers of $2$ $pmod 2003$divided by $2003$. Six comes from $2003/286=6$ so you go around six times.
– Ross Millikan
Jul 23 at 15:26
 |Â
show 4 more comments
up vote
4
down vote
accepted
up vote
4
down vote
accepted
If we write $2^k=2003q_k+r_k$ you are looking for the sum of the $q_k$. Assume for the moment that we know that $2$ is a primitive root $bmod 2003$. In that case the $r_k$ run through all the numbers from $1$ through $2002$ and we can write
$$sum_k=0^2001Big lfloor frac2^k2003Big rfloor=sum_k=0^2001 frac 2^k-r_k2003=frac 2^2002-12003-frac 2002cdot 20032cdot 2003=frac 2^2002-12003-1001$$
This gives an explicit expression without summation or floor functions, but actually computing it is beyond most of our patience as it will have about $600$ digits.
I don't have an easy way to show $2$ is a primitive root. The order of $2$ must divide $2002=2cdot7cdot 11 cdot 13$ so we can just check whether $2$ to any of $14$ powers is equivalent to $1 bmod 2003$. You can generate $2^2^n$ by repeated squaring and then multiply them, but it will be tedious.
I realized that all that is needed for this argument to work is to show $2^1001equiv -1 pmod 2003$, which will be true if $2$ is a primitive root but might be otherwise. With repeated squaring that is more within the range of hand computation, but still tedious.
answered Jul 22 at 14:18
Ross Millikan
276k21186352
If we write $2^k=2003q_k+r_k$ you are looking for the sum of the $q_k$. Assume for the moment that we know that $2$ is a primitive root $bmod 2003$. In that case the $r_k$ run through all the numbers from $1$ through $2002$ and we can write
$$sum_k=0^2001Big lfloor frac2^k2003Big rfloor=sum_k=0^2001 frac 2^k-r_k2003=frac 2^2002-12003-frac 2002cdot 20032cdot 2003=frac 2^2002-12003-1001$$
This gives an explicit expression without summation or floor functions, but actually computing it is beyond most of our patience as it will have about $600$ digits.
I don't have an easy way to show $2$ is a primitive root. The order of $2$ must divide $2002=2cdot7cdot 11 cdot 13$ so we can just check whether $2$ to any of $14$ powers is equivalent to $1 bmod 2003$. You can generate $2^2^n$ by repeated squaring and then multiply them, but it will be tedious.
I realized that all that is needed for this argument to work is to show $2^1001equiv -1 pmod 2003$, which will be true if $2$ is a primitive root but might be otherwise. With repeated squaring that is more within the range of hand computation, but still tedious.
answered Jul 22 at 14:18
Ross Millikan
276k21186352
edited Jul 22 at 14:40
answered Jul 22 at 14:18
Ross Millikan
276k21186352
answered Jul 22 at 14:18
Ross Millikan
276k21186352
answered Jul 22 at 14:18
Ross Millikan
276k21186352
276k21186352
Dear Ross Millikan. Thank you for your answer! However 2 is not a primitive root of 2003. In fact order of 2 mod 2003 is actualy 286?. But I understand your idea and I appreciated your help. Sincerely.
– Mathwriter
Jul 22 at 15:58
@Mathwriter: when I see a problem like this I try to find ways to bring the calculation into a range of what is reasonable. Probably knowing that $2$ is not a primitive root $bmod 7$ should have tipped me off. The fact that it is not primitive may change the $1001$ that is subtracted a bit.
– Ross Millikan
Jul 22 at 17:00
@Mathwriter: the fact that $2$ is not a primitive root can change the $1001$ term in my expression, but not by much. Most of the digits of the answer will be correct.
– Ross Millikan
Jul 23 at 14:51
Thanks, but can you give the explicit expression?
– Mathwriter
Jul 23 at 15:11
It is just six times the sum of all the powers of $2$ $pmod 2003$divided by $2003$. Six comes from $2003/286=6$ so you go around six times.
– Ross Millikan
Jul 23 at 15:26
 |Â
show 4 more comments
Dear Ross Millikan. Thank you for your answer! However 2 is not a primitive root of 2003. In fact order of 2 mod 2003 is actualy 286?. But I understand your idea and I appreciated your help. Sincerely.
– Mathwriter
Jul 22 at 15:58
@Mathwriter: when I see a problem like this I try to find ways to bring the calculation into a range of what is reasonable. Probably knowing that $2$ is not a primitive root $bmod 7$ should have tipped me off. The fact that it is not primitive may change the $1001$ that is subtracted a bit.
– Ross Millikan
Jul 22 at 17:00
@Mathwriter: the fact that $2$ is not a primitive root can change the $1001$ term in my expression, but not by much. Most of the digits of the answer will be correct.
– Ross Millikan
Jul 23 at 14:51
Thanks, but can you give the explicit expression?
– Mathwriter
Jul 23 at 15:11
It is just six times the sum of all the powers of $2$ $pmod 2003$divided by $2003$. Six comes from $2003/286=6$ so you go around six times.
– Ross Millikan
Jul 23 at 15:26
Dear Ross Millikan. Thank you for your answer! However 2 is not a primitive root of 2003. In fact order of 2 mod 2003 is actualy 286?. But I understand your idea and I appreciated your help. Sincerely.
– Mathwriter
Jul 22 at 15:58
Dear Ross Millikan. Thank you for your answer! However 2 is not a primitive root of 2003. In fact order of 2 mod 2003 is actualy 286?. But I understand your idea and I appreciated your help. Sincerely.
– Mathwriter
Jul 22 at 15:58
@Mathwriter: when I see a problem like this I try to find ways to bring the calculation into a range of what is reasonable. Probably knowing that $2$ is not a primitive root $bmod 7$ should have tipped me off. The fact that it is not primitive may change the $1001$ that is subtracted a bit.
– Ross Millikan
Jul 22 at 17:00
@Mathwriter: when I see a problem like this I try to find ways to bring the calculation into a range of what is reasonable. Probably knowing that $2$ is not a primitive root $bmod 7$ should have tipped me off. The fact that it is not primitive may change the $1001$ that is subtracted a bit.
– Ross Millikan
Jul 22 at 17:00
@Mathwriter: the fact that $2$ is not a primitive root can change the $1001$ term in my expression, but not by much. Most of the digits of the answer will be correct.
– Ross Millikan
Jul 23 at 14:51
@Mathwriter: the fact that $2$ is not a primitive root can change the $1001$ term in my expression, but not by much. Most of the digits of the answer will be correct.
– Ross Millikan
Jul 23 at 14:51
Thanks, but can you give the explicit expression?
– Mathwriter
Jul 23 at 15:11
Thanks, but can you give the explicit expression?
– Mathwriter
Jul 23 at 15:11
It is just six times the sum of all the powers of $2$ $pmod 2003$divided by $2003$. Six comes from $2003/286=6$ so you go around six times.
– Ross Millikan
Jul 23 at 15:26
It is just six times the sum of all the powers of $2$ $pmod 2003$divided by $2003$. Six comes from $2003/286=6$ so you go around six times.
– Ross Millikan
Jul 23 at 15:26
 |Â
show 4 more comments
up vote
0
down vote
Solution from a friend of mine: Since $$2^1001=-1(mod 2003) $$ then $$ 2^1001 + i + 2^i = 0 (mod 2003),$$ thus $$ left lfloorfrac2^1001 + i2003right rfloor + left lfloorfrac2^i2003right rfloor = frac2^1001 + i + 2^i2003 - 1,$$ therefore $$sum_k=0^2001Big lfloor frac2^k2003Big rfloor=frac 2^2002-12003-1001$$
answered Jul 24 at 11:11
Mathwriter
265
I had said that $2^1001equiv -1 bmod 2003$ was enough to show the subtraction was $1001$. I just realized that if you know the order of $2$ is $286$ the fact that $2002/286=7$ it is enough to show this. I don't know how to prove that without direct computation.
– Ross Millikan
Jul 24 at 13:55
add a comment |Â
up vote
0
down vote
Solution from a friend of mine: Since $$2^1001=-1(mod 2003) $$ then $$ 2^1001 + i + 2^i = 0 (mod 2003),$$ thus $$ left lfloorfrac2^1001 + i2003right rfloor + left lfloorfrac2^i2003right rfloor = frac2^1001 + i + 2^i2003 - 1,$$ therefore $$sum_k=0^2001Big lfloor frac2^k2003Big rfloor=frac 2^2002-12003-1001$$
answered Jul 24 at 11:11
Mathwriter
265
I had said that $2^1001equiv -1 bmod 2003$ was enough to show the subtraction was $1001$. I just realized that if you know the order of $2$ is $286$ the fact that $2002/286=7$ it is enough to show this. I don't know how to prove that without direct computation.
– Ross Millikan
Jul 24 at 13:55
add a comment |Â
up vote
0
down vote
up vote
0
down vote
Solution from a friend of mine: Since $$2^1001=-1(mod 2003) $$ then $$ 2^1001 + i + 2^i = 0 (mod 2003),$$ thus $$ left lfloorfrac2^1001 + i2003right rfloor + left lfloorfrac2^i2003right rfloor = frac2^1001 + i + 2^i2003 - 1,$$ therefore $$sum_k=0^2001Big lfloor frac2^k2003Big rfloor=frac 2^2002-12003-1001$$
answered Jul 24 at 11:11
Mathwriter
265
Solution from a friend of mine: Since $$2^1001=-1(mod 2003) $$ then $$ 2^1001 + i + 2^i = 0 (mod 2003),$$ thus $$ left lfloorfrac2^1001 + i2003right rfloor + left lfloorfrac2^i2003right rfloor = frac2^1001 + i + 2^i2003 - 1,$$ therefore $$sum_k=0^2001Big lfloor frac2^k2003Big rfloor=frac 2^2002-12003-1001$$
answered Jul 24 at 11:11
Mathwriter
265
answered Jul 24 at 11:11
Mathwriter
265
answered Jul 24 at 11:11
Mathwriter
265
answered Jul 24 at 11:11
Mathwriter
265
265
I had said that $2^1001equiv -1 bmod 2003$ was enough to show the subtraction was $1001$. I just realized that if you know the order of $2$ is $286$ the fact that $2002/286=7$ it is enough to show this. I don't know how to prove that without direct computation.
– Ross Millikan
Jul 24 at 13:55
add a comment |Â
I had said that $2^1001equiv -1 bmod 2003$ was enough to show the subtraction was $1001$. I just realized that if you know the order of $2$ is $286$ the fact that $2002/286=7$ it is enough to show this. I don't know how to prove that without direct computation.
– Ross Millikan
Jul 24 at 13:55
I had said that $2^1001equiv -1 bmod 2003$ was enough to show the subtraction was $1001$. I just realized that if you know the order of $2$ is $286$ the fact that $2002/286=7$ it is enough to show this. I don't know how to prove that without direct computation.
– Ross Millikan
Jul 24 at 13:55
I had said that $2^1001equiv -1 bmod 2003$ was enough to show the subtraction was $1001$. I just realized that if you know the order of $2$ is $286$ the fact that $2002/286=7$ it is enough to show this. I don't know how to prove that without direct computation.
– Ross Millikan
Jul 24 at 13:55
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%2f2859417%2fsum-of-integers-using-order-of-integers-and-primitive-roots%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
Note: I changed your notation for the floor function. These days, I think it is more common to write $lfloor x rfloor$ for the floor, and $lceil x rceil$ for the ceiling (the least integer which is not less than $x$). If you prefer the other notation, please change it back.
– lulu
Jul 22 at 13:51
For what it's worth: a (forbidden) computer calculation yields a formidable answer which this comment section is too small to allow me to reprint. This leads me to doubt that there is a terribly quick method, but who knows?
– lulu
Jul 22 at 13:54
Dear lulu, thank you for correcting my mistakes. I am not familiar with LaTex codes, so I appreciated your help. Sincerely.
– Mathwriter
Jul 22 at 13:55
No problem, and I wouldn't really call it a mistake. The notation you used was entirely standard not all that long ago, but I think the newer notation is better (as it lets us get at both floors and ceilings.
– lulu
Jul 22 at 13:56
Entertainingly, the computed result is exactly the maximum number of characters the comments will allow...I can't even add the usual dollar signs to get the typeface right. I'll post the computed solution in the next comment. I think you'll agree that, at least in that form, it's hard to imagine an easy argument. Of course it may be that this mess admits a nice interpretation, as a sum or difference of simply described exponents or such.
– lulu
Jul 22 at 13:57