Prove or reject my solution to "How quickly can you type this unary string?"

Question

I had posted an answer on the Code Golf SE yesterday. Although the answer on that site remain valid if no counterexample can be find. I'm interesting in its correctness. So I want to find a prove or counterexample to my solution. While, answer this question do not involve any skill about programming, but only some math work about integers. So, don't panic.

You may find the question authed by emanresu A on Code Golf SE, and my answer. But let me briefly restate the question:

Question

One want to type $n$ letter a's on an editor. The editor starts with no content in it, and an empty clipboard. In each step, the user may:

• A: Type a letter a, so there is one more letter a in the editor.
• C(k): Copy k letter a's into the clipboard. $k$ must be less than or equals to the number of characters currently in the editor. The clipboard now have $k$ letter a's in it.
• V: Paste the clipboard to the editor content. So the editor have $k$ more a's in it. $k$ is the number of characters we just sent to the clipboard.

And the question is to implement the function $f(x)$, where $x\in\mathbb{N}^+$ is the number of a we want to type, and $f(x)$ is the minimal steps we need.

An example is $f(17)=8$, which can be shown as: AAA C(3)VV C(8)V.

And the first 30 terms have shown in the question:

1,2,3,4,5,5,6,6,6,7,7,7,8,8,8,8,8,8,9,9,9,9,9,9,10,9,10,10,10

Notice that this function is not monotone, as $f(27)=9<10=f(26)$.

My Solution

My solution is define the function as (to not confuse with the $f$, let's denote it as $g$)

$$ g(x)= \begin{cases} n & n<6 \\ \min \left\{g\left(n-\left\lfloor\frac{n}{2}\right\rfloor\right)+2, g\left(n-2\left\lfloor\frac{n}{3}\right\rfloor\right)+3 \right\} & \text{otherwise} \end{cases} $$

• If you want to type $n$ characters, for $n>5$. You may want to:
  • First type $\displaystyle \left(n-\left\lfloor\frac{n}{2}\right\rfloor\right)$ characters, then copy paste $\displaystyle \left\lfloor\frac{n}{2}\right\rfloor$ characters.
  • First type $\displaystyle \left(n-2\left\lfloor\frac{n}{3}\right\rfloor\right)$ characters, then copy paste $\displaystyle \left\lfloor\frac{n}{3}\right\rfloor$ characters twice.

As the above discussion shown that it is possible to get $x$ a's in $g(x)$ steps. I can ensure that $g(x)\ge f(x)$ for any $x$. But I cannot show that $g(x)=f(x)$. And I have tested the function $g$ with every $x<2000$ with an referenced implementation, and it simply pass for all these testcases.

So what I'm wondering that if some one may either prove $g\equiv f$, or find a counterexample so $g(x)\ne f(x)$.

Answer 1

Fact 1: We may never paste more than two times in a row at the end:

If we ends in $C(r)V^{2k+1}$ with $k\geq 1$, replace by $C(r)VC(2r)V^{k}$, and we have $k+2 \leq 2k+1$.

If we ends in $C(r)V^{2k}$ with $k\geq 2$, replace by $C(r)VVC(2r)V^{k-1}$, and we have $k+2\leq 2k$.

By induction, we have our result.

Corollary: We have the induction: $$g(n) = \min\left\{\min_{r\geq \left\lfloor\frac{n}{2}\right\rfloor} g(n-r)+2, \min_{r\geq \left\lfloor\frac{n}{3}\right\rfloor} g(n-2r)+3\right\}$$

---

Fact 2: $g(n) \leq g(n+2)$

The optimal solution of $g(n+2)$ ends in $C(r)V$ or $C(r)VV$. We replace it by $C(r-2)V$ or $C(r-1)VV$ to upper bound $g(n)$ by $g(n+2)$.

Corollary: If $g(n) > g(n+1)$ then $g(n+1)$ ends in $C(r)VV$

Corollary: We are left with an induction that relies on three cases (when we end in two pastes, there is only one case – the third one – because the other inductions are at least two steps away) : $$g(n) = min \left\{g\left(n-\left\lfloor\frac{n}{2}\right\rfloor\right)+2, g\left(n-\left\lfloor\frac{n}{2}\right\rfloor+1\right)+2, g\left(n-2\left\lfloor\frac{n}{3}\right\rfloor\right)+3 \right\} $$

---

Fact 3: We can avoid the second case of the induction

Suppose that we get the second case of the induction, then we end in $C(r)VVC(\lfloor\frac{n}{2}\rfloor-1)V$.

• If $r+\lfloor\frac{n}{2}\rfloor-1$ is even, we can rewrite this end as $C(r)VC((r+\lfloor\frac{n}{2}\rfloor-1)/2)VV$

We just need to verify that

$$(r+\lfloor\frac{n}{2}\rfloor-1)/2 \leq n-\left\lfloor\frac{n}{2}\right\rfloor+1 - r$$

We must have $3r \leq n-\left\lfloor\frac{n}{2}\right\rfloor+1$, so $r$ grows in $\mathcal{O}(\frac{n}{3})$ so the left hand side grows $\mathcal{O}(\frac{n}{3})$ and the right hand side grows $\Omega(n)$ thus we will verify the inequality for some sufficiently large $n$ (and probably not very large).

• Otherwise, we rewrite it as $C(r-1)VC((r+\lfloor\frac{n}{2}\rfloor)/2)VV$

As above, we can verify that it is well defined for some sufficiently large $n$

---

Conclusion: We are thus left with the two cases that forms your conjecture.