9
$\begingroup$

Given $n\in\mathbb{N}$, I need to get just enough more than half of it. For example (you can think this is : number of games $\rightarrow$ minimum turns to win)

$$ 1 \rightarrow 1 $$ $$ 2 \rightarrow 2 $$ $$ 3 \rightarrow 2 $$ $$ 4 \rightarrow 3 $$ $$ 5 \rightarrow 3 $$ $$ 6 \rightarrow 4 $$ $$ 7 \rightarrow 4 $$ $$ \vdots $$ $$ 2i \rightarrow i+1 $$ $$ 2i+1 \rightarrow i+1 $$ $$ \vdots $$

Is it possible to create a simple formula without piecewise it into odd and even? Sorry for my bad English.

$\endgroup$
  • 2
    $\begingroup$ One approach: Are you familiar with the floor and/or ceiling functions? See here: en.wikipedia.org/wiki/Floor_and_ceiling_functions and consider using division by 2. $\endgroup$ – Xoque55 Jan 31 '16 at 1:20
  • 1
    $\begingroup$ By splitting the formula into cases for the input being either even or odd you can describe the sequence quite concisely using only the most elementary language and symbols. Why do you want to avoid splitting it? What is gained? $\endgroup$ – gnyrinn Feb 1 '16 at 16:29
41
$\begingroup$

The formula is $$n\to \left\lfloor \frac{n}{2} \right\rfloor +1$$ where the notation $\lfloor x \rfloor$ means the greatest integer not exceeding $x$.

$\endgroup$
  • 1
    $\begingroup$ And in some programming languages the expression $\left\lfloor \frac{n}{2} \right\rfloor$ is written as a single infix operator, for example n/2 (where integer division with discarding the remainder is implied) or n\2. $\endgroup$ – Jeppe Stig Nielsen Feb 1 '16 at 14:36
63
$\begingroup$

How about: $$ \frac{3+2n+(-1)^n}{4} $$ or (continuous function of $n \in \mathbb R$ or even $\mathbb C$): $$ \frac{3+2n+\cos(\pi n)}{4} $$

$\endgroup$
  • 5
    $\begingroup$ Cute! Not all that useful in practice, but a fresh way to look at the question. I give it a thumbs up. $\endgroup$ – Mark Fischler Jan 31 '16 at 2:03
  • 4
    $\begingroup$ I like continuity. $\endgroup$ – PyRulez Jan 31 '16 at 22:08
  • $\begingroup$ From the question, $n\in\mathbb{N}$. Any function $\mathbb{N} \to \mathbb{N}$ is continuous. The two formulas represent the same continuous function on $\mathbb{N}$ (as required when they are both correct). But the second expression generalizes to $\mathbb{R} \to \mathbb{R}$ or $\mathbb{C} \to \mathbb{C}$ and this extension is still continuous (and even analytic). $\endgroup$ – Jeppe Stig Nielsen Feb 1 '16 at 14:30
  • 1
    $\begingroup$ @JeppeStigNielsen ... thanks for that clarification $\endgroup$ – GEdgar Feb 1 '16 at 14:36
6
$\begingroup$

The formula below uses the floor function. $\lfloor x\rfloor$ denotes the floor function of x. For example, $\lfloor2\rfloor=2$ while $\lfloor2.5\rfloor=2$. For more on the floor and ceiling functions, go checkout Wikipedia's page on them.

$\frac{2i}{2}=i$, so $\lfloor\frac{2i}{2}\rfloor=i$. Meanwhile, $\frac{2i+1}{2}=i+\frac 1 2$, so $\lfloor\frac{2i+1}{2}\rfloor=i$. Therefore, for any $x$ that is either $2i$ or $2i+1$, $\lfloor\frac x 2\rfloor+1=i+1$. Thus, the function you are looking for is $f(x)=\lfloor\frac x 2\rfloor+1$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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