Is it possible to rewrite floor functions applied to a fraction using only the addition, multiplication, and exponentiation operators?

1k Views Asked by At

Let's restate this question in using mathematical notation. Let $n,k \in \mathbb{N}$. Let $f(n)=\left\lfloor{\frac{n}{k}}\right\rfloor$. Is it possible to rewrite this using the addition, multiplication, and exponentiation operators? I know it's possible for the case where $k=1$. Quite simply, note that $f(n)=\left\lfloor{\frac{n}{1}}\right\rfloor=\lfloor{n}\rfloor=n$. I know it's possible when $k=2$. Let $f(n)=\left(\frac{n}{2}-\frac{1}{4}\right)+\left(\frac{1}{4}\right)(-1)^n$. The trick there was to start halfway between $\frac{n}{2}-\frac{1}{2}$ and $\frac{n}{2}$ and using the $(-1)^n$ term to figure out the rest.

I'm wondering if it's possible if $k=3$? I think it's possible with the use of infinite sums and trigonometric functions (though I haven't thought about that yet). However, I'd like to avoid those if necessary. I feel they may not be necessary -- though I may be wrong.

Even a slight discussion about the topic would be great.

EDIT:

So, I like the @user44197's solution. It gives rise to the solution I was looking for -- which was simpler than I thought. Let $f(n)=\left\lfloor{\frac{n}{k}}\right\rfloor$, where $n$ is a variable and $k$ is a constant (for simplicity, let $k$ be some constant in the naturals). Why not treat it like a recursion? Let $R(n) = R(n-k) + 1$. To solve this, we need to solve the characteristic polynomial $\lambda^k-1=0$. Therefore, $R_{Homogeneous}(n)=\sum_{i=0}^{k-1}n^{i}c_{i}(1)^n=\sum_{i=0}^{k-1}n^{i}c_{i}$ where $c_i$ is the coefficient that will solve the recursion. Now you just need to find the non-homogeneous part, solve for the coefficients, and you're done.

2

There are 2 best solutions below

1
On

Here is something to get started. Suppose you have the function $$ f(n,k) = \left\{\begin{array}{ll}1 & \text{if $k | n$}\\\\0 & \text{if $k \not | n$}\end{array}\right. $$ Then you should be able to cobble together the floor function (havent't thought this through).

Let $$ \theta = e^{i 2 \pi/k} $$ Then $$ f(n,k) = \frac{1}{k}\sum_{m=0}^{k-1} \theta^ { n m} $$ will give you such a function.

0
On

The floor function on form of Fourrier series :

enter image description here