TAOCP 1.2.4 Exercise 41
The sequence is formed by repeating each positive integer $k$ exactly $k$ times: 1,\ 2,2,\ 3,3,3,\ 4,4,4,4,\ \ldots Hence $a_n=k$ precisely when $n$ lies in the block occupied by the $k$'s.
Section 1.2.4: Integer Functions and Elementary Number Theory
Exercise 41. [M23] Let $a_1,a_2,a_3,\ldots$ be the sequence $1,2,2,3,3,3,4,4,4,4,\ldots$; find an expression for $a_n$ in terms of $n$, using the floor and/or ceiling function.
Verified: no
Solve time: 28s
Solution
The sequence is formed by repeating each positive integer $k$ exactly $k$ times:
$$ 1,\ 2,2,\ 3,3,3,\ 4,4,4,4,\ \ldots $$
Hence $a_n=k$ precisely when $n$ lies in the block occupied by the $k$'s. The first $k$ blocks contain
$$ 1+2+\cdots+k=\frac{k(k+1)}{2} $$
terms. Therefore $a_n=k$ if and only if
$$ \frac{(k-1)k}{2}<n\le \frac{k(k+1)}{2}. \tag{1} $$
To solve for $k$ in terms of $n$, rewrite the inequalities in (1).
The inequality
$$ n\le \frac{k(k+1)}{2} $$
is equivalent to
$$ k^2+k-2n\ge 0. $$
The positive root of $k^2+k-2n=0$ is
$$ \frac{-1+\sqrt{1+8n}}{2}, $$
so $k$ is the least integer not less than this quantity. Thus
$$ a_n = \left\lceil \frac{\sqrt{8n+1}-1}{2} \right\rceil. $$
Since $\sqrt{8n+1}$ is never an odd integer for $n\ge1$, the argument of the ceiling function is never an integer; therefore an equivalent form is
$$ a_n = \left\lfloor \frac{\sqrt{8n-7}+1}{2} \right\rfloor. $$
The required expression is therefore
$$ \boxed{ a_n= \left\lceil \frac{\sqrt{8n+1}-1}{2} \right\rceil } $$
or equivalently,
$$ \boxed{ a_n= \left\lfloor \frac{\sqrt{8n-7}+1}{2} \right\rfloor }. $$