Sum of floored fractions $\lfloor \frac{1^3}{2009} \rfloor + \lfloor \frac{2^3}{2009} \rfloor + \cdots + \lfloor \frac{2008^3}{2009} \rfloor$

Question

I want to compute the remainder of $A$ divided by 1000, where $A$ is

$$A = \lfloor \frac{1^3}{2009} \rfloor + \lfloor \frac{2^3}{2009} \rfloor + \cdots + \lfloor \frac{2008^3}{2009} \rfloor.$$

I tried to observe the number of $x$'s that satisfies $\lfloor \frac{x^3}{2009} \rfloor = k$, for each $k$. However this turned out to be hard because I cannot find out general formula for such number in terms of $k$. Computing manually is also not possible because there are too many candidates for $k$. ($0 \sim \lfloor \frac{2008^3}{2009} \rfloor$)

Thank you for any form of hint, help, or solution.

Answer 1

It seems like you might be able to find a general form for \begin{equation*} \sum_{k=1}^{n} \frac{k^3}{2009}. \end{equation*} Fixing $n=2008$ might help thereafter. Modular arithmetic should quickly deal with the fractional part. Let me know if this is too vague of a hint.

Answer 2

The $k$th term of $A$ can be written as

$$\left\lfloor\frac{k^3}{2009}\right\rfloor = \frac{k^3 - \left(k^3\bmod 2009\right)}{2009}$$

So the whole sum $A$ is

$$\begin{align*} A &= \sum_{k=1}^{2008} \left\lfloor\frac{k^3}{2009}\right\rfloor\\ &= \sum_{k=1}^{2008} \frac{k^3 - \left(k^3\bmod 2009\right)}{2009}\\ &= \frac{\sum_{k=1}^{2008} k^3}{2009} - \frac{\sum_{k=1}^{2008} \left(k^3\bmod 2009\right)}{2009} \tag1 \end{align*}$$

The sum of cubes is well-known:

$$\begin{align*} \frac{\sum_{k=1}^{2008} k^3}{2009} &= \frac{2008^2 \cdot (2008+1)^2}{2^2\cdot 2009}\\ &= 1004^2\cdot 2009 \tag2 \end{align*}$$

For the sum of remainders in $(1)$, by factorising $2009 = 7\cdot 7\cdot 41$, for integer $k$,

$$2009 \mid k^3 \iff 7\cdot 41 = \frac{2009}7 \mid k^3$$

and consider the remainders of $k^3$ and $(2009-k)^3$,

$$\begin{align*} k^3 + (2009-k)^3 \equiv k^3 + (-k)^3 &\equiv 0 \pmod{2009}\\ \left(k^3 \bmod 2009\right) + \left((2009-k)^3 \bmod 2009\right) &= \begin{cases} 0, & 2009\mid k^3\\ 2009, & 2009 \nmid k^3 \end{cases}\\ &= \begin{cases} 0, & \frac{2009}7 \mid k\\ 2009, & \frac{2009}7 \nmid k \end{cases}\\ \end{align*}$$

So the terms of $\sum_{k=1}^{2008} \left(k^3\bmod 2009\right)$ pair up, with $6$ terms of zero while other pairs each add to $2009$:

$$\begin{align*} \sum_{k=1}^{2008} \left(k^3\bmod 2009\right) &= \frac{2008-6}{2} \cdot 2009\\ \frac{\sum_{k=1}^{2008} \left(k^3\bmod 2009\right)}{2009} &= 1001 \tag3 \end{align*}$$

From $(2)$ and $(3)$,

$$\begin{align*} A = 1004^2 \cdot 2009 - 1001 &\equiv 4^2 \cdot 9 - 1\\ &\equiv 143 \pmod{1000} \end{align*}$$

(Recording my comments under another answer as a post)

Answer 3

Let $\{x\} = x - \lfloor x \rfloor \in [0,1)$ be the fractional number of $x$.

For any integer $1 \le k \le 1004$, $2009$ divides $k^3 + (2009-k)^3$ and hence $\frac{k^3}{2009} + \frac{(2009-k)^3}{2009}$ is an integer. This implies

$$\small \left\{\frac{k^3}{2009}\right\} + \left\{\frac{(2009-k)^3}{2009}\right\} = \frac{k^3}{2009} + \frac{(2009-k)^3}{2009} - \left\lfloor\frac{k^3}{2009}\right\rfloor - \left\lfloor\frac{(2009-k)^3}{2009}\right\rfloor\tag{*1}$$ is an integer in $[0,2)$. ie. it equals to either $0$ or $1$.

In order for it to be $0$, we need $\left\{\frac{k^3}{2009}\right\} = \left\{\frac{(2009-k)^3}{2009}\right\} = 0$. This is equivalent to $2009| k^3$. Since $2009 = 7^2\cdot 41$, this reduces to $284|k$. For $1 \le k \le 1004$, there are only three such $k: 284,568,852$.

Summing $(*1)$ from $k = 0$ to $1004$ and rearrange, we get

$$\begin{align} A = \sum_{k=1}^{2008} \left\lfloor \frac{k^3}{2009}\right\rfloor &= \sum_{k=1}^{2008} \frac{k^3}{2009} - (1004 - 3)\\ &= \frac1{2009}\left(\frac{2008(2008+1)}{2}\right)^2 - 1001\\ &= 2009(1004)^2 - 1001\\ \end{align}$$

So the remainder is $$A \equiv 9(4)^2 - 1 \equiv 143 \pmod{1000}$$