4
$\begingroup$

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 ?

$\endgroup$

closed as off-topic by mechanodroid, Henrik, John Doe, Hurkyl, Foobaz John Dec 27 '17 at 23:33

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is missing context or other details: Please improve the question by providing additional context, which ideally includes your thoughts on the problem and any attempts you have made to solve it. This information helps others identify where you have difficulties and helps them write answers appropriate to your experience level." – mechanodroid, Henrik, John Doe, Hurkyl, Foobaz John
If this question can be reworded to fit the rules in the help center, please edit the question.

11
$\begingroup$

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

$\endgroup$
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ (+1) how did you come up with this? $\endgroup$ – Yanko Dec 27 '17 at 18:20
  • 2
    $\begingroup$ @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$. $\endgroup$ – Oleg567 Dec 27 '17 at 18:25
  • $\begingroup$ Ahh I see good thinking. Thanks! $\endgroup$ – Yanko Dec 27 '17 at 18:40
9
$\begingroup$

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!

$\endgroup$
  • $\begingroup$ @JohnLou Indeed! Thanks, I've fixed it. $\endgroup$ – Tiwa Aina Dec 27 '17 at 18:44
  • 1
    $\begingroup$ "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 $\endgroup$ – Malloc Dec 27 '17 at 19:43
  • 2
    $\begingroup$ 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 $\endgroup$ – Malloc Dec 27 '17 at 19:59
  • $\begingroup$ Good ole tail recursion. $\endgroup$ – Adonalsium Dec 27 '17 at 20:39
  • 1
    $\begingroup$ @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. $\endgroup$ – Malloc Dec 27 '17 at 21:20
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.