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
  • 1
    $\begingroup$ I think I remember seeing this problem on Math.SE recently. I'll look for it. $\endgroup$
    – hardmath
    Jan 24, 2021 at 22:03
  • 1
    $\begingroup$ Looks like this: oeis.org/A002024 $\endgroup$
    – RobPratt
    Jan 24, 2021 at 22:40
  • 1
    $\begingroup$ Found the correct sequence! oeis.org/A140358 $\endgroup$
    – inavda
    Jan 24, 2021 at 23:29
  • 1
    $\begingroup$ Yes, A002024 allows 0 coefficients in addition to +1 and -1. $\endgroup$
    – RobPratt
    Jan 24, 2021 at 23:48
  • 2
    $\begingroup$ 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. $\endgroup$
    – hardmath
    Jan 25, 2021 at 1:30

2 Answers 2

6
$\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$
    – user65203
    Jan 24, 2021 at 22:25
  • $\begingroup$ I will edit my post to make it more clear. $\endgroup$
    – inavda
    Jan 24, 2021 at 22:26
  • $\begingroup$ Is it more clear now? $\endgroup$
    – inavda
    Jan 24, 2021 at 22:36
  • 1
    $\begingroup$ Yep, it is, thanks. $\endgroup$
    – user65203
    Jan 24, 2021 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$
    – user65203
    Jan 24, 2021 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, 2021 at 0:10
  • $\begingroup$ @inavda: $T_3$ does not have the right parity. $\endgroup$
    – user65203
    Jan 25, 2021 at 0:11

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .