Minimal steps to reach a natural number by a signed arithmetic progression

Question

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

Answer 1

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.

Answer 2

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.