Welcome to our community

Be a part of something great, join today!

Problem Of The Week #398 Dec 19th, 2019

Status
Not open for further replies.
  • Thread starter
  • Admin
  • #1

anemone

MHB POTW Director
Staff member
Feb 14, 2012
3,894
Here is next week's (23th December 2019) POTW:

-----

Evaluate \(\displaystyle \left\lfloor{\frac{1}{3}}\right\rfloor+\left\lfloor{\frac{2}{3}}\right\rfloor+\left\lfloor{\frac{2^2}{3}}\right\rfloor+\left\lfloor{\frac{2^3}{3}}\right\rfloor+\cdots+\left\lfloor{\frac{2^{1000}}{3}}\right\rfloor\), without the help of a calculator.

-----

Remember to read the POTW submission guidelines to find out how to submit your answers!
 
  • Thread starter
  • Admin
  • #2

anemone

MHB POTW Director
Staff member
Feb 14, 2012
3,894
Congratulations to the following members for their correct solution!

1. castor28
2. kaliprasad
3. MegaMoh

Solution from castor28 :
Let us define:

  • $\displaystyle S = \sum_{k=0}^{1000}{\left\lfloor\frac{2^k}{3}\right\rfloor}$. This is the expression to be evaluated.
  • $\displaystyle T = \sum_{k=0}^{999}{\left\lfloor\frac{2^k}{3}\right\rfloor}$. This is the same as $S$, without the last term.
  • $\displaystyle U = \sum_{k=0}^{999}{\frac{2^k}{3}}$. This is the same as $T$ without the floor function.

$U$ is a geometric progression, with sum $\dfrac{2^{1000}-1}{3}$.

Since $2^{2k}\equiv1\pmod{3}$ and $2^{2k+1}\equiv2\pmod3$, we have:
$$
\left(\frac{2^{2k}}{3} + \frac{2^{2k+1}}{3}\right)-\left(\left\lfloor\frac{2^{2k}}{3}\right\rfloor+\left\lfloor\frac{2^{2k+1}}{3}\right\rfloor\right)=\frac13+\frac23=1
$$
As $T$ and $U$ contain $500$ such pairs of consecutive terms, we have $T = U - 500 = \dfrac{2^{1000}-1}{3}-500$.

As $ S = T + \left\lfloor\dfrac{2^{1000}}{3}\right\rfloor = T + \dfrac{2^{1000}-1}{3}$, we have $S = \dfrac{2(2^{1000}-1)}{3} - 500$.
 
Status
Not open for further replies.