Formula for the sequence 1 1 2 2 3 3

Question

I am trying to solve a programming problem where i encounter this pattern 1 1 2 2 3 3 4 4 . What is the formula for computing it for Nth term ?

Answer 1

Perhaps: $ \operatorname{ceiling}\big( \frac{n}{2} \big) $ for $n = 1, 2, 3, 4, ...$

Answer 2

Create a function that takes only integers

$$f : \mathbb Z \rightarrow \mathbb Z$$

and define it as

$$f(x) = \lceil x/2 \rceil$$

where $\lceil x \rceil$ is the ceiling function.

---

Interesting fact: You can define this function recursively where $$f(-1) = 0$$ $$ f(0)=0$$ $$f(n)=1+f(n-2)$$ While this would work, it would perform much worse than a function defined using the ceiling function. As Malloc explains, thanks to the power of modern computing, this is just as good as the function that explicitly uses the ceiling function. In fact, when compiled, they come out to the same thing!

Answer 3

Formula $$f(n) = \dfrac{2n+1+(-1)^{n+1}}{4}, \qquad \quad n = 1,2,3,\ldots$$ works too.

Or anything like this: $$f(n) = \dfrac{2n+1-\cos(\pi n)}{4}, \qquad \quad n=1,2,3,\ldots .$$

Answer 4

$$ f(n)=\left\{ \begin{array}{c} n/2, \: n \: is \: even \\ (n+1)/2, \: n \: is \: odd \\ \end{array} \right. $$

Answer 5

Here is a way to arrive at an answer using generating functions. Let the desired sequence be $\{a_n\}$ for $n\geq 1$ ($a_0=0$). Note that $$ \sum_{n=0}^\infty a_nx^n=\sum_{n=0}^\infty \frac{x^{2n+1}}{1-x}=\frac{x}{(1-x)(1-x^2)}=\frac{-1}{4(1+x)}-\frac{1}{4(1-x)}+\frac{1}{2(1-x)^2}\tag{1} $$ by partial fractions. Equation (1) makes sense as an identity of formal power series or for $|x|<1$. Then using the geometric series we obtain $$ \sum_{n=0}^\infty a_nx^n=\sum_{n=0}^\infty \left(\frac{(-1)^{n+1}-1+2(n+1)}{4}\right) x^n =\sum_{n=1}^\infty \left(\frac{(-1)^{n+1}+2n+1}{4}\right) x^n.\tag{2} $$ Hence $$ a_n=\frac{(-1)^{n+1}+2n+1}{4};\quad {(n\geq1)}.\tag{3} $$

Answer 6

Well? What answer do you want?

$a_N \approx \frac N2$ but the exact value depends on whether $N$ is even or odd.

The must obvious "binary" function that has two values depending on if the input is even or odd is $(-1)^N$ which is $1$ if $N$ is even and $-1$ if $N$ is odd.

So you have if $N = 2n-1; 2n$ if $N$ is odd; even$ then $a_N = n = \frac N2; \frac {N+1}2$ if $N$ is even;odd.

Or $a_N = \frac N2 + b_N$ where $b_N = 0$ if $N$ is even or $b_N = \frac 12$ if $N$ is odd.

To solve for $b_N$ note:

$(-1)^N = 1; -1$ if $N$ is even; odd.

$(-1)^N - 1 = 0; -2$

$\frac {(-1)^N -1}4 = 0, -\frac 12$.

$-\frac{(-1)^N -1}4 = 0; \frac 12$

So $a_N = \frac N2 - \frac {(-1)^N -1}4$ is a solution if you must have a single line purely mathematical expression.

But surely if you are programming you are allowed to use conditional IF clauses and define a function based on whether the input is even or not.

So simply "if $N$ % $2== 0$ return $\frac N2$; else return $\frac {N+1}2$;" will do.