# Combining Floor Functions

Hey fellow math enthusiasts,

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

where $c, n \in \mathbb{N}$.

Based on basic test cases using wolfram alpha it appears $f(c,n)$ is either $0$ or $1$.

The two pieces of information I am curious about is when does $f(c,n)=0$ (and by negation when does it equal $1$) and what is $\sum\limits_{c=1}^{x}{f(c,n)}$?

Thanks guys for taking a look at the problem!!

• Why not $f(c,n)$? – String Mar 5 '15 at 22:32
• As a first observation $f(c,n)=1$ iff $(2n+1 \mod c)+(n^2 \mod c)\geq c$ with $x\mod y$ is the remainder of the division of $x$ by $y$ – Elaqqad Mar 5 '15 at 22:40
• $f(c,n+c)=f(c,n)$ so one can study $f(c,n)$ for $0\leq n\leq c-1$ – Elaqqad Mar 5 '15 at 22:53

Let us for a moment forget the specific expressions within the floor functions and consider the form of the question: $$\lfloor x+y\rfloor-\lfloor y\rfloor=\lfloor x\rfloor+f(x,y)\\$$ which we may write as $$\lfloor x+y\rfloor=\lfloor x\rfloor+\lfloor y\rfloor+f(x,y)$$

Now let us first establish why $f(x,y)\in\{0,1\}$. Note that $x\mapsto\lfloor x\rfloor$ is an increasing function that is the identity on the integers. Since $\lfloor x\rfloor\leq x<\lfloor x\rfloor+1$ we then have $$\lfloor x\rfloor+\lfloor y\rfloor\leq x+y<\lfloor x\rfloor+\lfloor y\rfloor+2$$ Then applying the increasing function $x\mapsto\lfloor x\rfloor$ to each expression observing that the outer expressions are integers so they are mapped to themselves, we then have $$\lfloor x\rfloor+\lfloor y\rfloor\leq \lfloor x+y\rfloor<\lfloor x\rfloor+\lfloor y\rfloor+2$$ showing that the difference $f(x,y)=\lfloor x+y\rfloor-\lfloor x\rfloor-\lfloor y\rfloor$ is an integer in the interval $[0,2)$.

Defining $\{x\}=x-\lfloor x\rfloor\in[0,1)$ to be the fractional part of $x$ we have $\lfloor x\rfloor=x-\{x\}$. So in particular $$\lfloor x\rfloor+\lfloor y\rfloor=\lfloor x+y\rfloor\\ \iff\\ x-\{x\}+y-\{y\}=(x+y)-\{x+y\}\\ \iff\\ 0\leq\{x\}+\{y\}=\{x+y\}<1\\ \iff\\ \{\{x\}+\{y\}\}=\{x+y\}$$ where the last step holds since taking the fractional part of a number that is already in the interval $[0,1)$ changes nothing. Now $\{x\}+\{y\}\in[0,2)$ so the cases for which the above will not hold must therefore be when $\{x\}+\{y\}\in[1,2)$.

Your specific setup corresponds to $x=\frac{(n+1)^2}c$ and $y=\frac{n^2}c$. Taking the great observation by Elaqqad given in the comments into consideration, we therefore have for $n\pmod c=[n]_c=k\in\{0,1,2,...,c-1\}$ that $$\{x\}=\frac{[(k+1)^2]_c}c\quad\text{and}\quad\{y\}=\frac{[k^2]_c}c$$ So we need to study when $[(k+1)^2]_c+[k^2]_c\geq c$ for $k\in\{0,1,2,...,c-1\}$. These will be the congruence classes for which $f(c,n)=f(c,k)=1$.

If we replaced $(n+1)$ by some unrelated integer $m$, the number of cases for which $f(m,n,c)=1$ could be found by determining the quadratic residues $Q(c)$ modulo $c$ and finding pairs $(a,b)\in Q(c)\times Q(c)$ that lies in the closed half plane $a+b\geq c$ and the corresponding pairs $\{(m,n)\mid [m^2]_c=a\wedge[n^2]_c=b\}$. But the cases among those for which $m=n+1$ would depend heavily on $c$, so I suspect it would be hard to say anything general about those without choosing a specific $c$ and analyse that.