1

Consider the following step function: $f: \mathbb{N} \rightarrow \mathbb{N}, f(n) = \lfloor \frac{n^{2}}{2023} \rfloor$

Where $n \in [1, 2023]$. How many distinct values does the step function take?

Thanks!

  • 1
    Before a certain $n$, the values will keep overlapping. Afterwards, they'll all be different. – Benjamin Wang Feb 29 '24 at 14:04
  • Right! That's what I started with. All $n$ smaller than the square root of 2023 will get floored to 0. After $n = 1011$, it's easy to show that each new $n$ creates a different value of $f(n)$. However, I wonder if it's even possible to analytically solve for the values of $n$ between those points? –  Feb 29 '24 at 14:09
  • The general rule on this forum is that you should present your work on the problem in the question (or provide wider context to justify why the question is of interest to the community without these details). Please do so to avoid closure. – stochasticboy321 Feb 29 '24 at 14:22
  • Please edit this comment into the question. Also, you can add more thoughts or the proof with which you're not satisfied. – D S Feb 29 '24 at 14:23
  • @PudgeSuperior you don't need to analytically solve anything when the gaps are less than $2023$ and thus cannot skip an integer in the range, because all the integers in that range will be hit. – Benjamin Wang Feb 29 '24 at 14:33

1 Answers1

5

$45^2=2025$, so all values before $45$ return $0$.

$2023$ is the $1011$th odd number, so after $1011$ each interval between squares is equal to or greater than $2023$ and returns a new value.

Between $45$ and $1011$, you move from $45^2/2023=1.x$ to $1011^2/2023=505.x$ so you must have:

$0-44: 1$ value
$45-1011: 505$ values
$1012-2023: 1011$ values

For $1517$ values.

Edit: I can't do math: @Lozenges points out that $n=1012-2023$ yields $1012$ values for $1518$ total.

RobinSparrow
  • 1,091
  • Nice answer. Although to be more elegant, you don't need to distinguish 0-44 vs 45-1011. – Benjamin Wang Feb 29 '24 at 14:32
  • 1
    And more generally, if 2023 is replaced by $k$, we'll find about $3k/4$ distinct values of $\lfloor n^2/k\rfloor$ as $n$ ranges from $1$ to $k$ - about $k/4$ values for $n = 1, \ldots, k/2$ and about $k/2$ for n = k/2, \ldots, k$. (I'm being sloppy about the endpoints.) – Michael Lugo Feb 29 '24 at 15:08
  • 1
    $1012−2023$ : $1012$ values for a total of $1518$ – Lozenges Feb 29 '24 at 15:29