# Formula for the sequence 1 1 2 2 3 3 [closed]

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 ?

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

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

• (+1) how did you come up with this? Dec 27, 2017 at 18:20
• @yanko, $(-1)^n$ is the sequence $-1,1,-1,1,\ldots$. And see that $2,2,4,4,6,6,8,8,\ldots$ is almost Arithmetic Progression: $1.5, \;2.5, \;3.5, \;4.5,\; \ldots$ slightly corrected: $1.5+0.5, \;2.5-0.5, \;3.5+0.5, \;4.5-0.5,\; \ldots$. Dec 27, 2017 at 18:25
• Ahh I see good thinking. Thanks! Dec 27, 2017 at 18:40

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!

• @JohnLou Indeed! Thanks, I've fixed it. Dec 27, 2017 at 18:44
• "While this would work, it would perform much worse than a function defined using the ceiling function." You severely underestimate modern compilers. ;) godbolt.org/g/xJMhQ3 Dec 27, 2017 at 19:43
• Just realized that many here probably don't read assembly, sorry. In plain English: It compiles to almost the same code as the ceil solution. godbolt.org/g/aYtnVo Dec 27, 2017 at 19:59
• Good ole tail recursion. Dec 27, 2017 at 20:39
• @EricDuminil That's just idx / 2 without the ceil. It would yield the same sequence, but two based instead of 1 based. But I did mess up the operator precedence, it should be (idx >> 1) + (idx & 1) instead. facepalm Anyways, the point stands. Dec 27, 2017 at 21:20

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}$$

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

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.