# A sequence I didn’t like

Standard

Following is a problem I encountered many times in my high school olympiads, but was never able to solve it. Hence didn’t like it.

What is the 100th term in the sequence $1,2,2,3,3,3,4,4,4,4,5,\ldots$?

Following is a quick solution:

In this post, I will discuss the solution given in The Green Book of Mathematical Problems (problem 14).

Determine a function $f(n)$ such that the $n^{th}$ term of the sequence $1,2,2,3,3,3,4,4,4,4,5,\ldots$ is given by $\lfloor f(n)\rfloor$.

Let’s denote the $n^{th}$ number of the sequence by $a_n$, i.e. $a_n=\lfloor f(n)\rfloor$. The integer $m$ first occurs in the sequence when each of the integers from 1 to $m-1$ have already appeared 1 to $m-1$ times, respectively. Hence, if $a_n=m$ then
$n = [1 + 2 + 3 + \ldots + (m-1)]+1 +\ell = \frac{m(m-1)}{2} + 1 + \ell$
for $\ell = 0,1,2,\ldots, m-1$.

Hence we have:
$\displaystyle{0\leq n - \frac{m(m-1)}{2} - 1 \leq m-1}$

$\displaystyle{\Rightarrow \frac{m^2-m+2}{2}\leq n \leq \frac{m^2+m}{2}}$

$\displaystyle{\Rightarrow m^2-m+2\leq 2n \leq m^2+m}$

$\displaystyle{\Rightarrow \left(m-\frac{1}{2}\right)^2+\frac{7}{4}\leq 2n \leq \left(m+\frac{1}{2}\right)^2-\frac{1}{4}}$

$\displaystyle{\Rightarrow (2m-1)^2+7\leq 8n \leq (2m+1)^2 - 1}$

$\displaystyle{\Rightarrow (2m-1)^2 \leq 8n - 7 \leq (2m+1)^2 - 8}$

$\displaystyle{\Rightarrow (2m-1)^2 \leq 8n - 7 < (2m+1)^2}$

$\displaystyle{\Rightarrow 2m-1 \leq \sqrt{8n-7}<2m+1}$

$\displaystyle{\Rightarrow m \leq \frac{1+\sqrt{8n-7}}{2} < m+1}$

$\displaystyle{\Rightarrow m=\left\lfloor \frac{1+\sqrt{8n-7}}{2} \right\rfloor}$

Hence we have $a_n = \left\lfloor \frac{1+\sqrt{8n-7}}{2} \right\rfloor$. Thus, we have

$\displaystyle{\boxed{f(n) =\frac{1+\sqrt{8n-7}}{2}}}$

Now compared to the earlier solution obtained by observing the pattern, one might ask “Is there is a better formula?”. For that, you might also look at the discussion at Math.SE.

# Pulsating Checkpoint Sequence

Standard

Today my (first) sequence submitted to OEIS got approved.

OEIS Foundation Inc. (2016), The On-Line Encyclopedia of Integer Sequences, http://oeis.org/A264962

Special thanks to editor Jon E. Schoenfield for many useful suggestions.