Expanding the floor function. $ \lfloor n/p \rfloor=?$

Question

$n$ is a positive integer. Than we can write this.

$$\lfloor n/2 \rfloor= \left(n+\frac{(-1)^{n}-1}{2}\right)\frac{1}{2}$$

I wonder can we do that simplifying with other dividers? Like can we do the similar thing to $\lfloor n/3 \rfloor$?

Answer 1

We obtain a formula for $\left\lfloor\frac{n}{p}\right\rfloor$ using the $p$-th root of unity \begin{align*} \omega_j=e^{\frac{2j\pi i}{p}}\qquad\qquad 0\leq j \leq p-1 \end{align*}

The following holds true for $n\geq 0, p\geq 1$ \begin{align*} \left\lfloor\frac{n}{p}\right\rfloor&=\frac{n}{p}-\frac{p-1}{2p}+\frac{1}{p}\sum_{j=1}^{p-1}\frac{\omega_j^{n-p+1}}{w_j-1}\qquad\qquad \omega_j=e^{\frac{2j\pi i}{p}} \end{align*}

For $p=2,3,4$ we get \begin{align*} \left\lfloor\frac{n}{2}\right\rfloor&=\frac{n}{2}-\frac{1}{4}\left(1-(-1)^{n}\right)\\ \left\lfloor\frac{n}{3}\right\rfloor &=\frac{n}{3}-\frac{1}{3}+\frac{1}{18}(3-i\sqrt{3})\left(-\frac{1}{2}+i\frac{\sqrt{3}}{2}\right)^n +\frac{1}{18}(3+i\sqrt{3})\left(-\frac{1}{2}-i\frac{\sqrt{3}}{2}\right)^n\\ \left\lfloor\frac{n}{4}\right\rfloor&=\frac{n}{4}-\frac{3}{8}+\frac{1}{8}\left((-1)^n+\left(1+(-1)^n\right)i^n-\left(1-(-1)^n\right)i^{n+1}\right) \end{align*}

$$ $$

Since for $n\geq 0$ \begin{align*} S(n,p)=\frac{1}{p}\sum_{j=0}^{p-1}w_j^n= \begin{cases} 1&\qquad p|n\\ 0&\qquad otherwise \end{cases} \end{align*} we get for $0\leq j\leq p-1$ \begin{align*} S(n-j,p)=\frac{1}{p}\sum_{j=0}^{p-1}w_j^{n-j}= \begin{cases} 1&\qquad n\equiv j(\bmod\,p)\\ 0&\qquad otherwise \end{cases} \end{align*}

Example: $p=4$

\begin{align*} \left\lfloor\frac{n}{4}\right\rfloor&=\frac{n}{4}- \begin{cases} 0&\qquad n\equiv 0(\bmod\,4)\\ \frac{1}{4}&\qquad n\equiv 1(\bmod\,4)\\ \frac{2}{4}&\qquad n\equiv 2(\bmod\,4)\\ \frac{3}{4}&\qquad n\equiv 3(\bmod\,4)\\ \end{cases}\\ &=\frac{n}{4}-\frac{1}{4}S(n-1,4)-\frac{2}{4}S(n-2,4)-\frac{3}{4}S(n-3,4) \end{align*}

We obtain for general $p$ \begin{align*} \left\lfloor\frac{n}{p}\right\rfloor&=\frac{n}{p}-\sum_{k=1}^{p-1}\frac{k}{p}S(n-j,p)\\ &=\frac{n}{p}-\frac{1}{p^2}\sum_{k=1}^{p-1}k\sum_{j=0}^{p-1}\omega_j^{n-k}\\ &=\frac{n}{p}-\frac{1}{p^2}\sum_{j=0}^{p-1}\omega_j^n\sum_{k=1}^{p-1}k\omega_j^{-k}\\ &=\frac{n}{p}-\frac{p-1}{2p}-\frac{1}{p^2}\sum_{j=1}^{p-1}\omega_j^n\sum_{k=1}^{p-1}k\omega_j^{-k}\tag{1}\\ \end{align*}

In (1) we extract the summand with $j=0$ ($\omega_0=1$).

Since \begin{align*} \sum_{k=1}^{p-1}kx^k&=x\sum_{k=0}^{p-1}kx^{k-1}=x\frac{d}{dx}\sum_{k=0}^{p-1}x^k =x\frac{d}{dx}\frac{1-x^p}{1-x}\\ &=\frac{(p-1)x^{p+1}-px^p+x}{(1-x)^2} \end{align*}

we obtain with $x=\frac{1}{\omega}$ from (1)

\begin{align*} \left\lfloor\frac{n}{p}\right\rfloor&=\frac{n}{p}-\frac{p-1}{2p} -\frac{1}{p^2}\sum_{j=1}^{p-1}\frac{w_j^p-p\omega_j+p-1}{(w_j-1)^2}\omega_j^{n-p+1}\tag{2}\\ &=\frac{n}{p}-\frac{p-1}{2p}+\frac{1}{p}\sum_{j=1}^{p-1}\frac{\omega_j^{n-p+1}}{w_j-1} \end{align*}

Let's look at the formula for small $p=2,3,4$

Example: $p=2$

With $\{\omega_0,\omega_1\}=\{1,-1\}$ we obtain

\begin{align*} \left\lfloor\frac{n}{2}\right\rfloor&=\frac{n}{2}-\frac{1}{4}+\frac{1}{2}\sum_{j=1}^{1}\frac{w_j^{n-1}}{w_j-1}\\ &=\frac{n}{2}-\frac{1}{4}-\frac{1}{4}(-1)^{n-1}\\ &=\frac{n}{2}-\frac{1}{4}\left(1-(-1)^{n}\right) \end{align*}

Example: $p=3$

With $\{\omega_0,\omega_1,\omega_2\}=\{1,-\frac{1}{2}+i\frac{\sqrt{3}}{2},-\frac{1}{2}-i\frac{\sqrt{3}}{2}\}$ we obtain

\begin{align*} \left\lfloor\frac{n}{3}\right\rfloor&=\frac{n}{3}-\frac{1}{3}+\frac{1}{3}\sum_{j=1}^{2}\frac{w_j^{n-2}}{w_j-1}\\ &=\frac{n}{3}-\frac{1}{3}+\frac{1}{18}(3-i\sqrt{3})\left(-\frac{1}{2}+i\frac{\sqrt{3}}{2}\right)^n +\frac{1}{18}(3+i\sqrt{3})\left(-\frac{1}{2}-i\frac{\sqrt{3}}{2}\right)^n \end{align*}

Example: $p=4$

With $\{\omega_0,\omega_1,\omega_2,\omega_3\}=\{1,i,-1,-i\}$ we obtain

\begin{align*} \left\lfloor\frac{n}{4}\right\rfloor&=\frac{n}{4}-\frac{1}{4}+\frac{1}{4}\sum_{j=1}^{3}\frac{w_j^{n-3}}{w_j-1}\\ &=\frac{n}{4}-\frac{3}{8}+\frac{1}{4}\left(\frac{i^{n-3}}{i-1}+\frac{(-1)^{n-3}}{-2}+\frac{(-i)^{n-3}}{-i-1}\right)\\ &=\frac{n}{4}-\frac{3}{8}+\frac{1}{8}\left((-1)^n+\left(1+(-1)^n\right)i^n-\left(1-(-1)^n\right)i^{n+1}\right) \end{align*}

Answer 2

The Floor function:

$$\left\lfloor \frac{n}{k}\right\rfloor =\frac{n+1}{k}+\frac{i \log \left(-(-1)^{\frac{2 (n+1)}{k}}\right)}{2 \pi }-\frac{1}{2}$$