2
$\begingroup$

$F:=\big\{f\,\big|\,\text{function }f: \mathbf N\rightarrow \{1,2\}\big\}$. \begin{align} &\min_{f\in F,\,k\in\mathbf N} k, \\ &\sum_{i=1}^k (-1)^{f(i)}i = n \in\mathbf N. \end{align}

  1. Is there an analytical or an asymptotic solution to this problem for general $n$?

  2. For a specifically given $n$, what would a good algorithms to solve this problem? The dynamic programming?

$\endgroup$
8
5
$\begingroup$

Essentially, for any given $n$, the task is to select $+$'s and $-$'s to reach $n$ as fast as possible (minimize $k$): $$\pm 1 \pm 2 \pm 3 \pm \dots \pm k = n$$

If we don't worry about overshooting $n$, the obvious strategy is to only add and never subtract. If $n$ is a triangular number, this will give us the answer. This would necessarily be the optimal solution since we did not subtract at all.

If $n$ is not a triangular number, at some point $k'$, we will overshoot $n$: $$1 + 2 + 3 + \dots + k' > n$$

Since we need $k$ at least $k'$ to even reach $n$, we know that $k=k'$ is optimal if it works.

Consider the value $1 + 2 + 3 + \dots + k' - n$. We will denote this amount as $a$. We know that $a < k'$. If $a$ is even, then we can switch the operator of $a/2$ to $-$, and we have our optimal solution.

Figuring out the solution for when $a$ is odd may be trickier.

EDIT:

Figured out the "odd" case!

If $a$ is odd, then we cannot have $k = k'$ because there is no expression that will give us exactly $n$ using $k'$ terms. For any signs we switch in the $k'$ terms, the total sum will retain the same parity, so we cannot reach exactly $n$. Thus, if we can find a solution with $k'+1$ terms, it is necessarily optimal.

Consider $1 + 2 + 3 + \dots + k' + (k'+1) = n + a + k'+1$.

If $k'$ is even, then consider the value $\frac{a+k'+1}{2}$. We have $$\frac{a+k'+1}{2} < \frac{2k'+1}{2} = k' + 1/2 \,.$$

So, $\frac{a+k'+1}{2} \leq k'$. Thus, it is in our series, so we can assign it the operator $-$, and we have achieved exactly a sum of exactly $n$.

Now, to consider what happens when both $a$ and $k'$ are odd...

EDIT 2:

First off, is it possible to find a solution with $k=k'+1$ when $k'$ is odd?

Well if we use all $+$'s, we have $1 + 2 + 3 + \dots + k' + (k'+1) = n + a + k' + 1$. As before, switching the signs of any of our terms will preserve the parity of the total sum. Since $a$ and $k'$ are odd, $n+a+k'+1$ has opposite parity from $n$. So, no rearrangement of signs will enable a series of $k'+1$ terms to work.

Our next candidate is $k=k'+2$. Let us consider the following sum: $$1 + 2 + 3 + \dots + k' + (k'+1) + (k'+2) = n + a + (k'+1) + (k'+2)$$

We are too high by the quantity $a + 2k' + 3$. We can switch the sign of $k'$ and switch the sign of $\frac{a+3}{2}$, and we arrive at exactly $n$ with $k=k'+2$.

And that concludes the proof! No dynamic programming needed - a purely analytic solution.


TL;DR

Let $k'$ be the least integer such that $T_{k'} \geq n$. If $T_{k'}$ and $n$ have the same parity, then $k=k'$. Else, $k$ is equal to the least odd integer greater than $k'$.

See this OEIS sequence.

$\endgroup$
10
  • 1
    $\begingroup$ How do you know that these solutions are optimal ? $\endgroup$ – Yves Daoust Jan 24 at 22:25
  • $\begingroup$ I will edit my post to make it more clear. $\endgroup$ – inavda Jan 24 at 22:26
  • $\begingroup$ Is it more clear now? $\endgroup$ – inavda Jan 24 at 22:36
  • 1
    $\begingroup$ Yep, it is, thanks. $\endgroup$ – Yves Daoust Jan 24 at 22:41
  • $\begingroup$ Can't you say that you start with the smallest $k$ such that $T_k\ge n$ and $T_k$ has the same parity as $n$, as the overshoot correction will be even. $\endgroup$ – Yves Daoust Jan 24 at 22:44
0
$\begingroup$

Continuing on @inavda's answer, for a given $n$ we find the minimum number of terms, which is the index of the smallest triangular number not smaller than $n$, and with the same parity. As the parities of the triangular numbers follow the pattern $e,o,o,e,e,o,o,e,e,\cdots$, we can find the smallest triangular number not smaller than $n$, and increment once or twice as needed to reach the desired parity.

Then we repeat this operation recursively on the half of the residue $\dfrac{k(k+1)}2-n$ to obtain the desired correction.

Example: $n=37$

$$37\le T_9=45, \text{half residue }4\to+++++++++$$

$$4\le T_3=6, \text{half residue }1\to---+++++$$

$$1=T_1\to+--++++++$$


The smallest triangular number is obtained by

$$\frac{k(k+1)}2\ge n$$ or

$$k\ge\frac{\sqrt{8n+1}-1}2,$$

$$k=\left\lceil\frac{\sqrt{8n+1}-1}2\right\rceil.$$


Notice that the procedure fails for $n=2$, as the smallest triangular number is $T_3=6$ and the half residue is again $2$. Also for $n=5$, $T_5=5$ and the half residue is $5$. These are the only fixed points. We solve these with $2=1-2+3$ and $5=1-2-3+4+5$.


Notice that the residue is on the order $O(\sqrt n)$, so that the successive residues decrease very quickly, and the recursion depth is of order $O(\log\log n)$.


Update:

Checking the example, it turns out that this procedure is wrong.

$\endgroup$
2
  • $\begingroup$ "We find the minimum number of terms, which is the index of the smallest triangular number not smaller than $n$, and with the same parity." I don't think this phrasing is quite correct. For example, $a(5)=5$, but the index of the smallest triangular number greater than $5$ is $3$. $\endgroup$ – inavda Jan 25 at 0:10
  • $\begingroup$ @inavda: $T_3$ does not have the right parity. $\endgroup$ – Yves Daoust Jan 25 at 0:11

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.