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

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

• I think I remember seeing this problem on Math.SE recently. I'll look for it. Jan 24, 2021 at 22:03
• Looks like this: oeis.org/A002024 Jan 24, 2021 at 22:40
• Found the correct sequence! oeis.org/A140358 Jan 24, 2021 at 23:29
• Yes, A002024 allows 0 coefficients in addition to +1 and -1. Jan 24, 2021 at 23:48
• Here is the Question I was remembering: Proof: Find minimum moves to reach target on an infinite line algorithm Notice how its Accepted Answer deals with the parity issue. Jan 25, 2021 at 1:30

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

• How do you know that these solutions are optimal ?
– user65203
Jan 24, 2021 at 22:25
• I will edit my post to make it more clear. Jan 24, 2021 at 22:26
• Is it more clear now? Jan 24, 2021 at 22:36
• Yep, it is, thanks.
– user65203
Jan 24, 2021 at 22:41
• 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.
– user65203
Jan 24, 2021 at 22:44

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.

• "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$. Jan 25, 2021 at 0:10
• @inavda: $T_3$ does not have the right parity.
– user65203
Jan 25, 2021 at 0:11