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!!

  • 2
    $\begingroup$ Why not $f(c,n)$? $\endgroup$ – String Mar 5 '15 at 22:32
  • 1
    $\begingroup$ 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$ $\endgroup$ – Elaqqad Mar 5 '15 at 22:40
  • 3
    $\begingroup$ $f(c,n+c)=f(c,n)$ so one can study $f(c,n)$ for $0\leq n\leq c-1$ $\endgroup$ – 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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.