Amount of different numbers in a sequence

Question

Given a sequence $[\frac{1^2}{2018}]$, $[\frac{2^2}{2018}]$, ...,$[\frac{2018^2}{2018}]$. ( $[x]$ is the integer part of $x$) How can I find the amount of different numbers in this sequence? The squares confuse me.

Answer 1

We have the sequence $(q_k)$ with $$ q_k = \left \lfloor \frac{k^2}{2018} \right\rfloor \quad (k \in I=\{ 1, \dotsc, 2018 \}) $$ The sequence starts with $q_1=0$ and finishes with $q_{2018} = 2018$. It is monotonically increasing, but not strictly.

So how many different elements has $(q_k)$?

The difference between elements is $$ \Delta q_k = q_{k+1} - q_k = \left \lfloor \frac{(k+1)^2}{2018} \right\rfloor - \left \lfloor \frac{k^2}{2018} \right\rfloor $$

We can write $\Delta q_k$ as $$ \begin{align} \Delta q_k &= \frac{(k+1)^2}{2018} - \epsilon_1 - \left( \frac{k^2}{2018} - \epsilon_2 \right) \\ &= \frac{2k+1}{2018} + \epsilon_2 - \epsilon_1 \\ &\in \left( \frac{2k+1}{2018}-1, \frac{2k+1}{2018}+1 \right) \end{align} $$ where $\epsilon_i \in [0,1)$ are the fractional parts.

Here is an image:

The differences $\Delta q_k$ are rendered in red, they wobble around the line $f(k) = (2k+1)/2018$, which is rendered in green. The bounds are parallel lines rendered in grey.

Clashes:

Elements are not different if $\Delta q_k = 0$, in this case the new value clashes with the last value.

There are no clashes, if our lower bound line is on or above the $x$-axis: $$ \begin{align} \frac{2k+1}{2018}-1 &\ge 0 \iff \\ k &\ge 1008.5 \end{align} $$ Thus the feasible indices $1009$ to $2018$ will result in $1010$ distinct elements.

Gaps:

One index before, at $k=1008$, we have reached value $$ q_{1008} = \left \lfloor \frac{1008^2}{2018} \right\rfloor = 503 $$ So this means there could be values from $0$ to $503$, which are $504$ different ones.

Is it possible, that less values showed up in the sequence up to this point?

This would be the case, if we had gaps, thus $\Delta q_k \ge 2$.

For gaps to be possible, our upper bound must be above the line $y = 2$: $$ \begin{align} \frac{2k+1}{2018} + 1 &> 2 \iff \\ k &> 1008.5 \end{align} $$ We are lucky, there is no gap possible for indices $1$ to $1008$, so all $504$ values have to show up in the sequence.

Result:

We have $504$ distinct sequence elements for indices $1$ to $1008$ and $1010$ distinct sequence elements for indices $1009$ to $2018$. This gives $1514$ distinct sequence elements in total.

Answer 2

If $(n+1)^2-n^2\ge 2018$ (equivalently, if $2n+1>2018$), then clearly $$ \left\lfloor\frac{(n+1)^2}{2018}\right\rfloor-\left\lfloor\frac{n^2}{2018}\right\rfloor\ge 1. $$ So, the numbers $$ \left\lfloor\frac{n^2}{2018}\right\rfloor, \quad n=1010,\ldots,2018 $$ are different from each other. In particular $\left\lfloor\frac{1010^2}{2018}\right\rfloor=505$

On the other hand, $$ \left\lfloor\frac{n^2}{2018}\right\rfloor, \quad n=1,\ldots,1009 $$ is a sequence, which is increasing but not strictly, and the diference of two consecutive terms can not exceed 1. Hence $$ \left\{\left\lfloor\frac{n^2}{2018}\right\rfloor: n=1,\ldots,1009\right\}=\left\{0,1,2,\ldots,\left\lfloor\frac{1009^2}{2018}\right\rfloor\right\}=\{0,1,\ldots,504\} $$ Altogether: $$ 1009+505=1514 $$ different values.