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

# Prime Number Problem

Standard

Following is a problem about prime factorization of the sum of consecutive odd primes. (source: problem 80 from The Green Book of Mathematical Problems)

Prove that the sum of two consecutive odd primes is the product of at least three (possibly repeated) prime factors.

The first thing to observe is that sum of odd numbers is even, hence the sum of two consecutive odd primes will be divisible by 2. Let’s see factorization of some of the examples:

$3 + 5 = 2\times 2 \times 2$
$5 + 7 = 2 \times 2\times 3$
$7+11 = 2 \times 3\times 3$
$11+13 = 2 \times 2 \times 2 \times 3$
$13+17 = 2 \times 3 \times 5$
$17+19 = 2\times 2\times 3 \times 3$
$19+23 = 42 = 2\times 3\times 7$
$23+29 = 52 = 2\times 2 \times 13$

Now let $p_n$ and $p_{n+1}$ be the consecutive odd primes, then from above observations we can conjecture that either $p_n+p_{n+1}$ is product of at least three distinct primes or $p_n+p_{n+1}= 2^k p^\ell$ for some odd prime $p$ such that $k+\ell \geq 3$.

To prove our conjecture, let’s assume that $p_n+p_{n+1}$ is NOT a product of three (or more) distinct primes (otherwise we are done). Now we will have to show that if $p_n+p_{n+1}= 2^k p^\ell$ for some odd prime $p$ then $k+\ell \geq 3$.

If $\ell = 0$ then we should have $k\geq 3$. This is true since $3+5=8$.

Now let $\ell > 0$. Since $k\geq 1$ (sum of odd numbers is even), we just need to show that $k=1, \ell=1$ is not possible. On the contrary, let’s assume that $k=1,\ell = 1$. Then $p_n+p_{n+1} = 2p$. By arithmetic mean property, we have

$\displaystyle{p_n < \frac{p_n+p_{n+1}}{2}} = p

But, this contradicts the fact that $p_n,p_{n+1}$ are consecutive primes. Hence completing the proof of our conjecture.

This is a nice problem where we are equating the sum of prime numbers to product of prime numbers. Please let me know the flaws in my solution (if any) in the comments.