What's the minimum number of keystrokes needed to type n asterisks?

Question

Suppose you're editing a plain txt file and need to input a line of $n$ asterisk characters. You could press the * key $n$ times (assuming you have a numpad with a dedicated * key) but there is certainly a faster way by using the select-all/copy/paste keyboard shortcuts. For example if $n = 80$ you can type the asterisks with these eighteen keystrokes:

*****Ctrlacvvvvacvvvv

For a particular $n$ is there is a way to determine the minimum number of keystrokes necessary?

Answer 1

Here's an $O(n^{1.5})$ time solution assuming you are only allowed to use *, ctrl, a,c,v, and that further you're only allowed to use them to

1. print *
2. copy what you have already and paste it k times.

(not sure if there are other clever key combinations with these keys.)

Algorithm:

Assume inductively that you know an optimal way to produce, $0, 1, ..., n-1$ *'s. Call these strings of keystrokes $b_0, \ldots, b_{n-1}$.

Now, we just try each possibility.

First we consider just taking the solution $b_{n-1}$ and typing another *. This takes $l(b_{n-1}) + 1$ keystrokes, where $l(b_{i})$ means the number of keystrokes in solution $b_i$.

Then, for each divisor $d>1$ of $n$, we consider trying: $b_n$ + Ctrlacv...v with $n/d$ v's. This takes $l(b_n) + 3 + n/d$ keystrokes. This is assuming that we needed to use Ctrl; if there was a Ctrl already active, we only need $l(b_n) + 2 + n/d$ keystrokes. (We need to release the Ctrl to write *, at least on my keyboard...).

Then, we take the optimal of all these possibilities. We can use trial division for this, and so at most $\sqrt{n}$ steps are taken. Implementing this in Python I get $l(b_{80}) = 18$ as you do.

As the comments mention, if you are allowed to delete, we can optimize further, but this would force considering $b_k$ for $k > n$ which wouldn't be allowed under our inductive assumption, and so this recursive algorithm would not seem to be easily adapted.

edit:

The most efficient strings I found for $n \leq 20$ are

0 
1 *
2 * *
3 * * *
4 * * * *
5 * * * * *
6 * * * * * *
7 * * * * * * *
8 * * * * * * * *
9 * * * ctrl a c v v v
10 * * ctrl a c v v v v v
11 * * ctrl a c v v v v v *
12 * * * ctrl a c v v v v
13 * * * ctrl a c v v v v *
14 * * ctrl a c v v v v v v v
15 * * * ctrl a c v v v v v
16 * * * * ctrl a c v v v v
17 * * * * ctrl a c v v v v *
18 * * * ctrl a c v v v v v v
19 * * * ctrl a c v v v v v v *
20 * * * * ctrl a c v v v v v

and the values of $l(b_n)$ for $0 \leq n \leq 100$ are

0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 10, 11, 12, 11, 11, 12, 12, 13, 12, 13, 14, 15, 13, 13, 14, 14, 14, 15, 14, 15, 15, 16, 17, 15, 15, 16, 17, 17, 16, 17, 16, 17, 18, 16, 17, 18, 16, 17, 17, 18, 18, 19, 17, 18, 18, 19, 20, 21, 17, 18, 19, 18, 17, 18, 19, 20, 19, 20, 19, 20, 18, 19, 20, 18, 19, 20, 20, 21, 18, 19, 20, 21, 19, 20, 21, 21, 21, 22, 19, 20, 21, 21, 22, 21, 19, 20, 21, 22, 19

As we might expect, it exhibits logarithmic growth: