Find number of distinct integer terms in the sequence We have to find the number of distinct integer terms in the sequence $$\Big\lfloor\frac{i^2}{2005}\Big\rfloor$$ from $i=1$ to $2005$ where $\lfloor . \rfloor$ represents the floor function.
Initially I calculated the first few terms and saw all the integers from $0$ coming up so I assumed this to be the norm and answered as $2006$.
But when I put it on WolframAlpha, I saw that there didn't seem to be a pattern especially towards the end.
Can someone explain any method to determine and predict this trend without using a calculator?
 A: You're only guaranteed a distinct value going from $i$ to $i+1$ if $$(i+1)^2 - i^2 = 2i + 1 \geq 2005.$$ You may get a distinct value for values of $i$ less that that, but not necessarily.
However, this implies that you are guaranteed to hit every non-negative integer value up to that point. You may get the values more than once, but you only count them once.
The crossover point happens at $2i+1 = 2005$ or $i = 1002$. The value of the floor function is $\lfloor 1002^2/2005\rfloor = 500$. So you have all of the integers from $0$ to $500$, plus one distinct integer apiece for every value of $i>1002$, which amounts to $1003$ integers.
So, the list contains $501 + 1003 = 1504$ distinct integers. (This agrees with the number of integers WA came up with.)
A: $\mathbb{S} \subset \{0,1,2,...,2005\}$
Let $f : \{1,2,3, \cdots , 2005\} \rightarrow \mathbb{S}$ be such that $f(x) = \lfloor \frac{x^2}{2005} \rfloor$.
Claim : $f$ is onto function in $\{ 1,2,\cdots , 1002\}$ and one to one function in $\{ 1003,1004,\cdots,2005\}$.
Proof : Let $a = \lfloor \frac{x^2}{2005} \rfloor$ where $a \in \mathbb{S}$. From the property of greatest integer function, it can be concluded that $$a≤ \frac{x^2}{2005} < a+1 \iff 2005a ≤ x^2 < 2005(a+1) \iff \sqrt{2005a} ≤ x < \sqrt{2005(a+1)}$$
Now for $f$ to be onto, for every $a$ there exist $x$, i.e., there must be at least one integer between $\sqrt{2005(a+1)}$ and $\sqrt{2005a}$. This is possible when $$\sqrt{2005(a+1)} - \sqrt{2005a} ≥ 1 \implies 2005a ≤ 1002^2 \implies a ≤ \Big \lfloor \frac{1002^2}{2005} \Big \rfloor = 500 \Box $$
For $f$ to be one to one function, no value in $\mathbb{S}$ may be taken by $f(x)$ more than once. Therefore, $$\Big \lfloor \frac{x^2}{2005} \Big \rfloor \ne \Big \lfloor \frac{(x+1)^2}{2005} \Big \rfloor$$ $\frac{(x+1)^2}{2005} = \frac{x^2}{2005} + \frac{2x+1}{2005}$ Therefore when $\frac{2x+1}{2005}>1 \iff (2x+1) > 2005$ , or $x > 1002$, $f$ is one to one $\Box$.
Final Solution : $|\mathbb{S}| = 501 + (2005-1002) = \boxed{1504}$
