# Problem Of The Week #398 Dec 19th, 2019

Status
Not open for further replies.

#### anemone

##### MHB POTW Director
Staff member
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.

-----

#### anemone

##### MHB POTW Director
Staff member
Congratulations to the following members for their correct solution!

1. castor28
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.