Tag Archives: sequence

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.

ss

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.