3
$\begingroup$

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?

$\endgroup$
4
  • $\begingroup$ Note: I changed your notation, $[n]$ into $\lfloor n \rfloor$ as being, I think the more standard notation for the floor function these days. If you prefer it the other way, just roll back my edit. $\endgroup$
    – lulu
    Commented Jun 28, 2019 at 17:47
  • $\begingroup$ @lulu It's OK. Actually I wanted that notation too but didn't know how to do it. $\endgroup$
    – infinite-blank-
    Commented Jun 28, 2019 at 17:49
  • $\begingroup$ No problem, if you click on the thing that says "edited X mins ago" you can see the syntax I used. $\endgroup$
    – lulu
    Commented Jun 28, 2019 at 17:53
  • 1
    $\begingroup$ To your question, the values for the floor change every time $i^2$ crosses over a number of the form $\sqrt {2005n}$ for some integer $n$. Thus the first $1$ you get comes at $i=45$, where $\sqrt {2005}\approx 44.78$ and the first $2$ you get comes at $i=64$ where $\sqrt {2\times 2005}\approx 63.32$. The problems start around $i=523$, since $\sqrt {523\times 2005}\approx 1024.02$ and $\sqrt {524\times 2005}\approx 1024.99756$ and of course it gets worse from there. $\endgroup$
    – lulu
    Commented Jun 28, 2019 at 18:00

2 Answers 2

Reset to default
2
$\begingroup$

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.)

$\endgroup$
2
  • 2
    $\begingroup$ Since we get $$\Big\lfloor\frac{1002^2}{2005}\Big\rfloor=500$$ then that means that we have $0-500$ till that point. Then doesn't that mean that we get a new distinct integer from $1003-2005$. So that would be $501+1003=1504$ distinct integers? $\endgroup$
    – infinite-blank-
    Commented Jun 29, 2019 at 16:01
  • $\begingroup$ Thanks for re-checking. I counted $i=1002$ twice. And when I pulled WA's results into Excel to remove the duplicates, I forgot to take out the blank that was counted. You're correct. $\endgroup$
    – John
    Commented Jun 29, 2019 at 17:24
1
$\begingroup$

$\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}$

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .