## The mathematics of CTRL-C CTRL-V

For the discussion of math. Duh.

Moderators: gmalivuk, Moderators General, Prelates

Siyko
Posts: 3
Joined: Sat Nov 21, 2009 3:04 am UTC

### The mathematics of CTRL-C CTRL-V

So let's say I want to type "this is spam this is spam this is spam this is spam this is spam this is spam this is spam this is spam this is spam this is spam..."

I want to type the string "this is spam" 20 times.

So I type it once, 13 keystrokes including the space at the end. I hit ctrl+(a, c, (v*20)). Total of 36 keystrokes.

But, I can also do ctrl+(a, c, (v*10), a, c, (v*2)) for a total of 30 keystrokes.

I can also do ctrl+(a, c, (v*5), a, c, (v*4)) for a total of 27

There has to be a mathematical formula to find the best way to do this - time is money!!!

njperrone
Posts: 102
Joined: Wed Sep 23, 2009 9:27 pm UTC

### Re: The mathematics of CTRL-C CTRL-V

Well, best thing i can think of doing is doing a series of experiments and recording them as coordinate pairs. this will generate some points to which you can do regression analysis for and using calculus you can minimize the keystrokes. You could also just brute force it entirely to find the minimum number of keystrokes. Unfortunately I cannot think of any nice purely mathematical approach, but I do hope some one can for the sake of elegance.

lingomaniac88
Posts: 127
Joined: Wed Apr 09, 2008 2:52 am UTC

### Re: The mathematics of CTRL-C CTRL-V

Here are my initial thoughts:

Spoiler:
The 13 keystrokes required for "this is spam " don't really matter, since they must be typed in every keystroke. Then, if you want "this is spam" to appear [imath]N[/imath] times, then you want to find [imath]k[/imath] positive integers [imath]a_1,a_2,\ldots,a_k[/imath] such that [imath]a_1a_2\ldots a_k=N[/imath] while minimizing [imath]3(a_1+a_2+\ldots+a_k)[/imath]. This immediately brings the AM-GM inequality to mind. I believe you'll want to make your [imath]a_i[/imath] as close as possible to each other.
"It is common sense to take a method and try it. If it fails, admit it frankly and try another. But above all, try something."
-- Franklin D. Roosevelt

EduardoLeon
Posts: 111
Joined: Wed Sep 30, 2009 2:26 am UTC
Location: Lima, Perú
Contact:

### Re: The mathematics of CTRL-C CTRL-V

These ideas might be helpful: Exponentiation by squaring.
Gott weiß ich will kein Engel sein!

qbg
Posts: 586
Joined: Tue Dec 18, 2007 3:37 pm UTC

### Re: The mathematics of CTRL-C CTRL-V

Sounds like trying to find the minimal addition chain, a hard problem.

squareroot1
Posts: 172
Joined: Fri Nov 06, 2009 8:27 pm UTC

### Re: The mathematics of CTRL-C CTRL-V

Questions:
Am I to assume the paste operation copies over what is selected, and after one paste the cursor goes to the end of the string? I assume yes on both counts.
Is there 'free' selection with the mouse or move to end of selection by hitting right arrow? I assume neither.
Do you have to hit the desired number of copies exactly? Did both, kinda.

In math,
Spoiler:
basically seems you want to minimize $\sum (a_i+2)$subject to$\prod a_i=N$ with i varying.
If you can overshoot it is mostly trivial,
Spoiler:
N copies minimum can be achieved with 4*floor(ln N / ln 2)+2 keystrokes (or something similar), just apply (acv^4) then repeat (acv^2) until you have N or more.
For the exact case, I suspect
Spoiler:
prime factorize N, $N=\prod p_i^{n_i}.$ Then apply (acv^pi) ni times. Do so for each i in turn, and you should get N copies. There are some special cases to consider, (acv^4) is preferred to (acv^2 acv^2), and (acv^2) is preferred to (acv^2 acv^3), but (acv^9) is not preferred to (acv^3 acv^3), for example. This operation should be commutative and associative, I think, but I'm too lazy atm to prove it.

Edit: Better notation, thanks Qaanol.

EduardoLeon wrote:These ideas might be helpful: Exponentiation by squaring.

qbg wrote:Sounds like trying to find the minimal addition chain, a hard problem.
There doesn't appear to be a method to select less significant groupings of copies. It seems like we are limited to ctrl+a,c, and v, and the implied action of the cursor after ctrl+v, so what you currently have is all you can use. This severely reduces the complexity of the problem and makes it much easier than the minimal addition chain. Atleast that's how I understand it.
Last edited by squareroot1 on Sat Nov 21, 2009 6:55 am UTC, edited 1 time in total.

Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

### Re: The mathematics of CTRL-C CTRL-V

27 is minimal here.

Edit: Incorrect statements removed, thanks.
Last edited by Qaanol on Sat Nov 21, 2009 12:24 pm UTC, edited 2 times in total.
wee free kings

squareroot1
Posts: 172
Joined: Fri Nov 06, 2009 8:27 pm UTC

### Re: The mathematics of CTRL-C CTRL-V

Qaanol wrote:27 is minimal here. There are 5 different ways to achieve it.

$acv^5acv^4 = acv^4acv^5 = acvacvacv^5 = acvacv^5acv = acv^5acvacv$

acv^4 can't equal acvacv, either acvacv=acv^3 or acv^2acv^2 = acv^4

Ctrl+v is either overwrite or append, hopefully OP will clear up which is preferred.

stephentyrone
Posts: 778
Joined: Mon Aug 11, 2008 10:58 pm UTC
Location: Palo Alto, CA

### Re: The mathematics of CTRL-C CTRL-V

As someone already said, this is an addition chain problem. There is no known algorithm to find the optimal chain that is better than brute force search. That isn't to say that it's impossible for one to exist, but the related decision problem is NP-complete, so if you found a fast algorithm for this, you would have better things to worry about anyway.
GENERATION -16 + 31i: The first time you see this, copy it into your sig on any forum. Square it, and then add i to the generation.

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

### Re: The mathematics of CTRL-C CTRL-V

squareroot1 wrote:Ctrl+v is either overwrite or append, hopefully OP will clear up which is preferred.

It is both. Immediately after Ctrl-a Ctrl-c, all the text is selected, so all Ctrl-v does is to overwrite the text with the same thing, but deselects it and puts the cursor at the end. Subsequent Ctrl-vs will append a copy of the original text.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

### Re: The mathematics of CTRL-C CTRL-V

OK, this is less hard than people are claiming. Admittedly, finding an optimal chain requires you to be able to factorize, but then so does finding any non-trivial chain.

Let [imath]f(n_1, \ldots, n_k)[/imath] be the number of copies of the original text created by [imath]acv^{n_1} \ldots acv^{n_k}[/imath], and let [imath]g(n_1, \ldots, n_k)[/imath] be the number of keystrokes required. Clearly [imath]g(n_1, \ldots, n_k) = c + \sum_{i=1}^k (n_i + 2)[/imath].

Lemma 1: [imath]f(n_1, \ldots, n_k) = \prod_{i=1}^k n_i[/imath].
Proof: In any sequence of ctrl-vs, the first v will overwrite the original text, and subsequent ones will duplicate it, so f(n) = n. Given [imath](n_1, \ldots, n_k)[/imath], the last [imath]n_k[/imath] ctrl-vs will copy the result of what came before [imath]n_k[/imath] times, so [imath]f(n_1, \ldots, n_k) = n_k f(n_1, \ldots, n_{k-1})[/imath]. So the result follows by induction on k.

The problem given can be rephrased as choosing [imath]k[/imath] and [imath](n_1, \ldots, n_k)[/imath] to minimize [imath]g(n_1, \ldots, n_k)[/imath], subject to [imath]f(n_1, \ldots, n_k) = N[/imath]. Neither f nor g depend on the ordering of the [imath]n_i[/imath], so we merely need to find a factorization of N that minimizes g.

Certainly optimal factorizations exist - let's assume we have one. What can we say about it? Certainly if [imath]n[/imath] appears in it, we shouldn't be able to factorize it into [imath]p[/imath] and [imath]q[/imath] with [imath]p + q + 2 < n[/imath], otherwise our factorization wouldn't be optimal. What numbers cannot be factorized in this way?

Lemma 2: If [imath]n[/imath] appears in an optimal factorization, then [imath]n[/imath] is either prime, 4, 6 or 8.
Proof: Let [imath]n[/imath] be in some optimal factorization, and let [imath]pq = n[/imath]. Without loss of generality let [imath]p \leq q[/imath]. If [imath]p \geq 3[/imath], then [imath]p + q + 2 < 3q \leq n[/imath], so the factorization is not optimal. If [imath]p = 2[/imath], then [imath]p + q + 2 \geq n[/imath] implies [imath]\frac{n}{2}+4 \geq n[/imath] implies [imath]n \leq 8[/imath]. And if [imath]p=1[/imath], then [imath]p+q+2 = n+3 > n[/imath], which is certainly worse.

Thus we only need to worry about the prime factors dividing n that are 2 or 3, as any other prime factor p of N must appear as a sequence of p keystrokes only. We might as well not have any 8s, as g(4,2) = g(8). Also, g(6,2) < g(4,3), so 2s would rather be paired with other 2s than 3s. So our sequence consists of all the prime factors greater than 3, then as many 4s as possible, then a 6 if we have an spare 2 and a 3, then any 2s or 3s that are left. This is optimal.

EDIT: Slight notation correction.
Last edited by Token on Sat Nov 21, 2009 1:06 pm UTC, edited 1 time in total.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

### Re: The mathematics of CTRL-C CTRL-V

Token wrote:OK, this is less hard than people are claiming. Admittedly, finding an optimal chain requires you to be able to factorize, but then so does finding any non-trivial chain.

Let [imath]f(n_1, \ldots, n_k)[/imath] be the number of copies of the original text created by [imath]acv^{n_1} \ldots acv^{n_k}[/imath], and let [imath]g(n_1, \ldots, n_k)[/imath] be the number of keystrokes required. Clearly [imath]g(n_1, \ldots, n_k) = c + \sum_{i=1}^k (n_i + 2)[/imath].

Lemma 1: [imath]f(n_1, \ldots, n_k) = \prod_{i=1}^k n_i[/imath].
Proof: In any sequence of ctrl-vs, the first v will overwrite the original text, and subsequent ones will duplicate it, so f(n) = n. Given [imath](n_1, \ldots, n_k)[/imath], the last [imath]n_k[/imath] ctrl-vs will copy the result of what came before [imath]n_k[/imath] times, so [imath]f(n_1, \ldots, n_k) = n_k f(n_1, \ldots, n_{k-1})[/imath]. So the result follows by induction on k.

The problem given can be rephrased as choosing [imath]k[/imath] and [imath](n_1, \ldots, n_k)[/imath] to minimize [imath]g(n_1, \ldots, n_k)[/imath], subject to [imath]f(n_1, \ldots, n_k) = N[/imath]. Neither f nor g depend on the ordering of the [imath]n_i[/imath], so we merely need to find a factorization of N that minimizes g.

Certainly optimal factorizations exist - let's assume we have one. What can we say about it? Certainly if [imath]n[/imath] appears in it, we shouldn't be able to factorize it into [imath]p[/imath] and [imath]q[/imath] with [imath]p + q + 2 < n[/imath], otherwise our factorization wouldn't be optimal. What numbers cannot be factorized in this way?

Lemma 2: If [imath]n[/imath] appears in an optimal factorization, then [imath]n_i[/imath] is either prime, 4, 6 or 8.
Proof: Let [imath]n[/imath] be in some optimal factorization, and let [imath]pq = n[/imath]. Without loss of generality let [imath]p \leq q[/imath]. If [imath]p \geq 3[/imath], then [imath]p + q + 2 < 3q \leq n[/imath], so the factorization is not optimal. If [imath]p = 2[/imath], then [imath]p + q + 2 \geq n[/imath] implies [imath]\frac{n}{2}+4 \geq n[/imath] implies [imath]n \leq 8[/imath]. And if [imath]p=1[/imath], then [imath]p+q+2 = n+3 > n[/imath], which is certainly worse.

Thus we only need to worry about the prime factors dividing n that are 2 or 3, as any other prime factor p of N must appear as a sequence of p keystrokes only. We might as well not have any 8s, as g(4,2) = g(8). Also, g(6,2) < g(4,3), so 2s would rather be paired with other 2s than 3s. So our sequence consists of all the prime factors greater than 3, then as many 4s as possible, then a 6 if we have an spare 2 and a 3, then any 2s or 3s that are left. This is optimal.

Well done.

If you want to maximize the number of copies that will be produced should you have to stop early, then work your way through the list from smallest to largest, and don't combine a 2 and 4 into an 8.
wee free kings

squareroot1
Posts: 172
Joined: Fri Nov 06, 2009 8:27 pm UTC

### Re: The mathematics of CTRL-C CTRL-V

Token wrote:
squareroot1 wrote:Ctrl+v is either overwrite or append, hopefully OP will clear up which is preferred.

It is both. Immediately after Ctrl-a Ctrl-c, all the text is selected, so all Ctrl-v does is to overwrite the text with the same thing, but deselects it and puts the cursor at the end. Subsequent Ctrl-vs will append a copy of the original text.

Good point, I was mainly stressing whether Ctrl-v would do that initial overwrite of the selected text or not. Basically, acv^2 is doubling, not acv which is the identity.

Token wrote:Thus we only need to worry about the prime factors dividing n that are 2 or 3, as any other prime factor p of N must appear as a sequence of p keystrokes only. We might as well not have any 8s, as g(4,2) = g(8). Also, g(6,2) < g(4,3), so 2s would rather be paired with other 2s than 3s. So our sequence consists of all the prime factors greater than 3, then as many 4s as possible, then a 6 if we have an spare 2 and a 3, then any 2s or 3s that are left. This is optimal.

I got the same result after fiddling with the approach I outlined above. I ended up watching Bones and The Bourne Ultimatum instead of posting. I didn't bother proving it with lemmas and all that jazz, but yeah. Spoiled for length.
Spoiler:
I like to think of the copying process as a string of 'a's, 'c's and 'v's coded by the composition of terms (acv^p)^n). EG. (acv^3)^2 results in acvvvacvvv.
Terms can interact: (acv^p)^n(acv^p)^m = (acv^p)^(n+m) (acv^p)^n(acv^q)^n=(acv^(p*q))^n.
The string length is the sum of the length of the terms, the length of a term is (2+p)*n.
A string is unique up to permutations of its terms.
There exists at least one minimal length string for any given N; it may not be unique.

One process to find a minimal length string for a given N is
1. Factor N over the primes.$N = \prod{{p_i}^{n_i}}$
2. Create the associated string S0 as the composition (multiplication) of the terms for each prime factor.
$S_0 = \prod{(acv^{p_i})^{n_i}}$
3.a This string will have minimal length if pi ≠ 2 for any i or pi=2, ni=1, pj ≠ 3 for some i and any j.
3.b Otherwise, compose as many (acv^2 acv^2) terms into (acv^4) terms as possible; if there is an extra (acv^2) term and a (acv^3) term, compose the two into a (acv^6) term.
The resulting string S1 will have minimal length for N.

I like that 3.a implies that S0 will have minimal length for any odd N or any even N not divisible by 3 or 4.

Edit: Very nice Token, very nice indeed.

Sobuno
Posts: 3
Joined: Sun Dec 14, 2008 10:44 pm UTC

### Re: The mathematics of CTRL-C CTRL-V

Hold down CTRL+V till the message has appeared 13 times, let go = 13*(CTRL+V) managed in one keystroke

Nitrodon
Posts: 497
Joined: Wed Dec 19, 2007 5:11 pm UTC

### Re: The mathematics of CTRL-C CTRL-V

The method described in this thread is usually optimal, but not always for large N. For instance, outputting "this is spam " 257 times takes 272 keystrokes by that method, but there's a way to do it in 58 (57 if you don't need a trailing space at the very end).

squareroot1
Posts: 172
Joined: Fri Nov 06, 2009 8:27 pm UTC

### Re: The mathematics of CTRL-C CTRL-V

Nitrodon wrote:The method described in this thread is usually optimal, but not always for large N. For instance, outputting "this is spam " 257 times takes 272 keystrokes by that method, but there's a way to do it in 58 (57 if you don't need a trailing space at the very end).

I assume you mean "this is spam "(acv^4)^4"this is spam"? Oh wait, that's 49 keystrokes (50 with the trailing space.) But it also uses keystrokes other than ctrl+{a,c,v}.

My method is obviously used to create N copies from a given, arbitrary string. I'm fairly sure I don't refer to the length of the initial string, because I'm not interested in an addition chain problem.

Sobuno wrote:Hold down CTRL+V till the message has appeared 13 times, let go = 13*(CTRL+V) managed in one keystroke

Sigh, so obviously its trivial, turn the repeat rate for the keyboard as high as possible, then do acv* and hold v until you get the desired number of copies. Release at the appropriate millisecond. Don't overshot! If you do, av* and try again.
Last edited by squareroot1 on Sat Nov 21, 2009 11:45 pm UTC, edited 1 time in total.

Qaanol
The Cheshirest Catamount
Posts: 3069
Joined: Sat May 09, 2009 11:55 pm UTC

### Re: The mathematics of CTRL-C CTRL-V

I count 50.

Initial 13 + ctrl + (1 + 1 + 4)*4 + 13 = 13 + 1 + 24 + 12 = 50
wee free kings

Siyko
Posts: 3
Joined: Sat Nov 21, 2009 3:04 am UTC

### Re: The mathematics of CTRL-C CTRL-V

Thanks a lot for all the replies - my math background is not good enough to know all the references, but I understand the formulas.

The 13 keystrokes required for "this is spam " don't really matter, since they must be typed in every keystroke.

This is true - the only time string length would ever make a difference would be if it were less than 4 keystrokes (typing 'a <space> a <space> ctrl+(acv)' is faster than 'a <space> ctrl+(acv acv)') but that only really matters for the initial steps, and the rules of what changes are pretty simple.

Hold down CTRL+V till the message has appeared 13 times, let go = 13*(CTRL+V) managed in one keystroke

This is missing the point

To specify some confusion, after selecting all, the next strike of 'v' performs the same function as 'right arrow' or 'end' - it overwrites the selected text with a copy of itself - and clears the 'selected' buffer, moving the cursor to the end of the selection (the end of the document if ctrl-a was used, which it was).

I'm going to try a bit harder to digest Token's reply. I'm glad this subject got the attention it deserved (it's very important!)

Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: The mathematics of CTRL-C CTRL-V

Let's take 7427466391 copies.

By Token's proof, this takes 7427466391+K (for some small K) steps, as this is a 10 digit prime.

My plan? Generate 7427466390, then manually type in the last copy (or use shift-arrow to highlight, ctrl-c, ctrl-v^2).

7427466390=2*3*5*31*139*57457
which, as you can quite imagine, takes less work to do this number than the original using Token's method.

Odds are pulling off the same trick on 57457, or changing the target number by something other than 1, would do even better.

Of course, this changes the problem from "has a pretty solution" to "oh my god, what have we done" hard, I suspect.
One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

squareroot1
Posts: 172
Joined: Fri Nov 06, 2009 8:27 pm UTC

### Re: The mathematics of CTRL-C CTRL-V

Yakk wrote:Of course, this changes the problem from "has a pretty solution" to "oh my god, what have we done" hard, I suspect.

You suspect correctly. The ability to simply type in the next n copies changes the complexity from "Here's a nice solution - with proof!" to "Oh me yarm addition chain! It's NP-complete!" as a few people have already stated.

OT: Is this thread dead yet, Jim?

Token
Posts: 1481
Joined: Fri Dec 01, 2006 5:07 pm UTC
Location: London

### Re: The mathematics of CTRL-C CTRL-V

People have said it's an addition chain problem, but I don't see how. Maybe I'm just too tired.
All posts are works in progress. If I posted something within the last hour, chances are I'm still editing it.

squareroot1
Posts: 172
Joined: Fri Nov 06, 2009 8:27 pm UTC

### Re: The mathematics of CTRL-C CTRL-V

Token wrote:People have said it's an addition chain problem, but I don't see how. Maybe I'm just too tired.

Let's see if I can explain this simply.

The difference is, some people consider it
1. Type string.
2. Press some combination of ctrl+a, ctrl+c, ctrl+v.
3. End.
while others consider it
1. Type string.
2. Press some combination of ctrl+a, ctrl+c, ctrl+v.
3. Type the string again?
4. Press some combination of ctrl+a, ctrl+c, ctrl+v?
5. Type the string again?
6. Press some combination of ctrl+a, ctrl+c, ctrl+v?
...
N. End

The latter is an addition chain problem and NP-complete, mainly because of the question marks.

phlip
Restorer of Worlds
Posts: 7573
Joined: Sat Sep 23, 2006 3:56 am UTC
Location: Australia
Contact:

### Re: The mathematics of CTRL-C CTRL-V

That's not quite an addition chain, though... an addition chain is "each new number can be the sum of some two previous numbers; minimise the length of the chain", whereas this new problem is more restrictive: "each new number is either the previous number plus or minus one (weight k), or the previous number times n for some natural n (weight an+b); minimise the total weight of the chain." Specifically, with a = 1, b = 2, k = the length of the initial string. That is, plus one means typing a k-character string... minus one means k backspaces (or possibly fewer ctrl+backspaces?)... multiplying it by n means acvn.

For instance, if you go "acvvacvvacvv" to get 8, you can't then quickly add 2 to get 10, even though you did, at one point, have 2 (indeed, you had 2 in the clipboard at one point). Your options after "acvvacvvacvv" are identical to your options after "acvvvvacvv". As opposed to an addition chain, where you can do (1,2,4,8,10).

I wouldn't be surprised if it's still NP-complete, though.

Note that the relative sizes of a, b and k in that definition are important, too... if I wanted 17 "1"s, then I could do "1111acvvvv1", but if I wanted 17 war-and-peaces, I'd do "<war and peace here>acv17".

I did some brute-forcing, results in the spoiler.
Spoiler:
Typing is represented by "+-----" to show the length of the string... backspacing by "<====". Copy/pasting by "acvvv".

For a one-character initial string:

Code: Select all

    0:     1: +    2: ++    3: +++    4: ++++    5: +++++    6: ++++++    7: +++++++    8: ++++acvv    9: +++acvvv   10: +++++acvv   11: +++++acvv+   12: ++++acvvv   13: ++++acvvv+   14: +++++++acvv   15: +++++acvvv   16: ++++acvvvv   17: ++++acvvvv+   18: ++++++acvvv   19: ++++++acvvv+   20: +++++acvvvv   21: +++++++acvvv   22: +++++++acvvv+   23: ++++++acvvvv<   24: ++++++acvvvv   25: +++++acvvvvv   26: +++++acvvvvv+   27: +++acvvvacvvv   28: +++++++acvvvv   29: +++++++acvvvv+   30: ++++++acvvvvv   31: ++++++acvvvvv+   32: ++++acvvacvvvv   33: +++++acvv+acvvv   34: ++++acvvvv+acvv   35: +++++++acvvvvv   36: ++++acvvvacvvv   37: ++++acvvvacvvv+   38: ++++++acvvv+acvv   39: ++++acvvv+acvvv   40: +++++acvvacvvvv   41: +++++acvvacvvvv+   42: +++++++acvvvvvv   43: +++++++acvvvvvv+   44: +++++acvv+acvvvv   45: +++++acvvvacvvv   46: +++++acvvvacvvv+   47: ++++acvvvacvvvv<   48: ++++acvvvacvvvv   49: ++++acvvvacvvvv+   50: +++++acvvacvvvvv   51: ++++acvvvv+acvvv   52: ++++acvvv+acvvvv   53: ++++++acvvvacvvv<   54: ++++++acvvvacvvv   55: ++++++acvvvacvvv+   56: +++++++acvvacvvvv   57: ++++++acvvv+acvvv   58: +++++++acvvvv+acvv   59: +++++acvvvacvvvv<   60: +++++acvvvacvvvv   61: +++++acvvvacvvvv+   62: +++++++acvvvacvvv<   63: +++++++acvvvacvvv   64: ++++acvvvvacvvvv   65: ++++acvvv+acvvvvv   66: +++++++acvvv+acvvv   67: ++++acvvvv+acvvvv<   68: ++++acvvvv+acvvvv   69: ++++++acvvvv<acvvv   70: +++++++acvvacvvvvv   71: ++++++acvvvacvvvv<   72: ++++++acvvvacvvvv   73: ++++++acvvvacvvvv+   74: +++++acvvvacvvvvv<   75: +++++acvvvacvvvvv   76: ++++++acvvv+acvvvv   77: ++++++acvvv+acvvvv+   78: +++++acvvvvv+acvvv   79: +++++acvvvvacvvvv<   80: +++++acvvvvacvvvv   81: +++acvvvacvvvacvvv   82: +++acvvvacvvvacvvv+   83: +++++++acvvvacvvvv<   84: +++++++acvvvacvvvv   85: ++++acvvvv+acvvvvv   86: ++++acvvvv+acvvvvv+   87: +++++++acvvvv+acvvv   88: +++++++acvvv+acvvvv   89: ++++++acvvvacvvvvv<   90: ++++++acvvvacvvvvv   91: ++++++acvvvacvvvvv+   92: ++++++acvvvv<acvvvv   93: ++++++acvvvvv+acvvv   94: ++++acvvvacvvvv<acvv   95: ++++++acvvv+acvvvvv   96: ++++++acvvvvacvvvv   97: ++++++acvvvvacvvvv+   98: ++++acvvvacvvvv+acvv   99: +++++acvvvvacvvvvv<  100: +++++acvvvvacvvvvv  101: +++++acvvvvacvvvvv+  102: ++++acvvvv+acvvvvvv  103: +++++acvvvvv+acvvvv<  104: +++++acvvvvv+acvvvv  105: +++++++acvvvacvvvvv  106: +++++++acvvvacvvvvv+  107: ++++acvvvacvvvacvvv<  108: ++++acvvvacvvvacvvv  109: ++++acvvvacvvvacvvv+  110: +++++++acvvv+acvvvvv  111: ++++acvvvacvvv+acvvv  112: +++++++acvvvvacvvvv  113: +++++++acvvvvacvvvv+  114: ++++++acvvv+acvvvvvv  115: ++++++acvvvv<acvvvvv  116: +++++++acvvvv+acvvvv  117: ++++acvvv+acvvvacvvv  118: ?  119: ++++++acvvvvacvvvvv<  120: ++++++acvvvvacvvvvv  121: ++++++acvvvvacvvvvv+  122: ?  123: ?  124: ++++++acvvvvv+acvvvv  125: +++++acvvvvvacvvvvv  126: +++++++acvvvacvvvvvv  127: ?  128: ++++acvvacvvvvacvvvv  129: ?  130: +++++acvvvvv+acvvvvv  131: ?  132: ?  133: ?  134: ?  135: +++++acvvvacvvvacvvv  136: ?  137: ?  138: ?  139: ?  140: +++++++acvvvvacvvvvv  141: ?  142: ?  143: ?  144: ++++acvvvacvvvacvvvv  145: ?  146: ?  147: ?  148: ?  149: ?  150: ++++++acvvvvvacvvvvv
For a three-character string:

Code: Select all

    0:     1: +--    2: +--+--    3: +--acvvv    4: +--acvvvv    5: +--acvvvvv    6: +--+--acvvv    7: +--acvvvvvvv    8: +--+--acvvvv    9: +--acvvvacvvv   10: +--+--acvvvvv   11: +--+--acvvvvv+--   12: +--+--acvvvvvv   13: +--+--acvvvvvv+--   14: +--+--acvvvvvvv   15: +--acvvvacvvvvv   16: +--acvvvvacvvvv   17: +--acvvvvacvvvv+--   18: +--+--acvvvacvvv   19: +--+--acvvvacvvv+--   20: +--acvvvvacvvvvv   21: +--acvvvacvvvvvvv   22: +--+--acvvvvvvvvvvv   23: +--+--acvvvacvvvv<==   24: +--+--acvvvacvvvv   25: +--acvvvvvacvvvvv   26: +--acvvvvvacvvvvv+--   27: +--acvvvacvvvacvvv   28: +--acvvvvacvvvvvvv   29: +--+--acvvvacvvvvv<==   30: +--+--acvvvacvvvvv   31: +--+--acvvvacvvvvv+--   32: +--+--acvvvvacvvvv   33: +--+--acvvvvacvvvv+--   34: +--acvvvvacvvvv+--acvv   35: +--acvvvvvacvvvvvvv   36: +--+--acvvvacvvvvvv   37: +--+--acvvvacvvvvvv+--   38: +--+--acvvvacvvv+--acvv   39: +--+--acvvvvacvvvvv<==   40: +--+--acvvvvacvvvvv   41: +--+--acvvvvacvvvvv+--   42: +--+--acvvvacvvvvvvv   43: +--+--acvvvacvvvvvvv+--   44: +--+--acvvvvv+--acvvvv   45: +--acvvvacvvvacvvvvv   46: +--acvvvacvvvacvvvvv+--   47: +--+--acvvvvacvvvvvv<==   48: +--+--acvvvvacvvvvvv   49: +--acvvvvvvvacvvvvvvv   50: +--+--acvvvvvacvvvvv   51: +--+--acvvvvvacvvvvv+--   52: +--+--acvvvvvv+--acvvvv   53: +--+--acvvvacvvvacvvv<==   54: +--+--acvvvacvvvacvvv   55: +--+--acvvvvv+--acvvvvv   56: +--+--acvvvvacvvvvvvv   57: +--+--acvvvacvvv+--acvvv   58: ?   59: +--+--acvvvvvacvvvvvv<==   60: +--+--acvvvvvacvvvvvv   61: +--+--acvvvvvacvvvvvv+--   62: ?   63: +--acvvvacvvvacvvvvvvv   64: +--acvvvvacvvvvacvvvv   65: +--+--acvvvvvv+--acvvvvv   66: +--+--acvvvvv+--acvvvvvv   67: ?   68: +--acvvvvacvvvv+--acvvvv   69: ?   70: +--+--acvvvvvacvvvvvvv   71: ?   72: +--+--acvvvacvvvacvvvv   73: ?   74: ?   75: +--acvvvacvvvvvacvvvvv   76: ?   77: ?   78: ?   79: ?   80: +--acvvvvacvvvvacvvvvv   81: +--acvvvacvvvacvvvacvvv   82: ?   83: ?   84: +--+--acvvvvvvacvvvvvvv   85: ?   86: ?   87: ?   88: ?   89: ?   90: +--+--acvvvacvvvacvvvvv   91: ?   92: ?   93: ?   94: ?   95: ?   96: +--+--acvvvacvvvvacvvvv   97: ?   98: +--+--acvvvvvvvacvvvvvvv   99: ?  100: +--acvvvvacvvvvvacvvvvv  101: ?  102: ?  103: ?  104: ?  105: +--acvvvacvvvvvacvvvvvvv  106: ?  107: ?  108: +--+--acvvvacvvvacvvvvvv  109: ?  110: ?  111: ?  112: +--acvvvvacvvvvacvvvvvvv  113: ?  114: ?  115: ?  116: ?  117: ?  118: ?  119: ?  120: +--+--acvvvacvvvvacvvvvv  121: ?  122: ?  123: ?  124: ?  125: +--acvvvvvacvvvvvacvvvvv  126: ?  127: ?  128: +--+--acvvvvacvvvvacvvvv
For a ten-character string:

Code: Select all

    0:     1: +---------    2: +---------acvv    3: +---------acvvv    4: +---------acvvvv    5: +---------acvvvvv    6: +---------acvvvvvv    7: +---------acvvvvvvv    8: +---------acvvacvvvv    9: +---------acvvvacvvv   10: +---------acvvacvvvvv   11: +---------acvvvvvvvvvvv   12: +---------acvvvacvvvv   13: +---------acvvvvvvvvvvvvv   14: +---------acvvacvvvvvvv   15: +---------acvvvacvvvvv   16: +---------acvvvvacvvvv   17: +---------acvvvvvvvvvvvvvvvvv   18: +---------acvvvacvvvvvv   19: +---------acvvvvvvvvvvvvvvvvvvv   20: +---------acvvvvacvvvvv   21: +---------acvvvacvvvvvvv   22: +---------acvvacvvvvvvvvvvv   23: ?   24: +---------acvvvvacvvvvvv   25: +---------acvvvvvacvvvvv   26: +---------acvvacvvvvvvvvvvvvv   27: +---------acvvvacvvvacvvv   28: +---------acvvvvacvvvvvvv   29: ?   30: +---------acvvvvvacvvvvvv   31: ?   32: +---------acvvacvvvvacvvvv   33: +---------acvvvacvvvvvvvvvvv   34: ?   35: +---------acvvvvvacvvvvvvv   36: +---------acvvvacvvvacvvvv   37: ?   38: ?   39: +---------acvvvacvvvvvvvvvvvvv   40: +---------acvvacvvvvacvvvvv   41: ?   42: +---------acvvvvvvacvvvvvvv   43: ?   44: +---------acvvvvacvvvvvvvvvvv   45: +---------acvvvacvvvacvvvvv   46: ?   47: ?   48: +---------acvvvacvvvvacvvvv   49: +---------acvvvvvvvacvvvvvvv   50: +---------acvvacvvvvvacvvvvv   51: ?   52: +---------acvvvvacvvvvvvvvvvvvv   53: ?   54: +---------acvvvacvvvacvvvvvv   55: +---------acvvvvvacvvvvvvvvvvv   56: +---------acvvacvvvvacvvvvvvv   57: ?   58: ?   59: ?   60: +---------acvvvacvvvvacvvvvv   61: ?   62: ?   63: +---------acvvvacvvvacvvvvvvv   64: +---------acvvvvacvvvvacvvvv   65: ?   66: +---------acvvvvvvacvvvvvvvvvvv   67: ?   68: ?   69: ?   70: +---------acvvacvvvvvacvvvvvvv   71: ?   72: +---------acvvvacvvvvacvvvvvv   73: ?   74: ?   75: +---------acvvvacvvvvvacvvvvv   76: ?   77: ?   78: ?   79: ?   80: +---------acvvvvacvvvvacvvvvv   81: +---------acvvvacvvvacvvvacvvv   82: ?   83: ?   84: +---------acvvvacvvvvacvvvvvvv   85: ?   86: ?   87: ?   88: ?   89: ?   90: +---------acvvvacvvvvvacvvvvvv   91: ?   92: ?   93: ?   94: ?   95: ?   96: +---------acvvvvacvvvvacvvvvvv   97: ?   98: ?   99: ?  100: +---------acvvvvacvvvvvacvvvvv  101: ?  102: ?  103: ?  104: ?  105: +---------acvvvacvvvvvacvvvvvvv  106: ?  107: ?  108: +---------acvvvacvvvacvvvacvvvv  109: ?  110: ?  111: ?  112: +---------acvvvvacvvvvacvvvvvvv  113: ?  114: ?  115: ?  116: ?  117: ?  118: ?  119: ?  120: +---------acvvvvacvvvvvacvvvvvv  121: ?  122: ?  123: ?  124: ?  125: +---------acvvvvvacvvvvvacvvvvv
As you'd expect... the one-character one has a lot of re-typing, less copying except when it's very useful. The ten-character one, at least looking this deep, never re-types, only copies. The three-character one is somewhere in-between.

All three of these were calculated by building every chain of at most 20 "steps", where a retyping or backspacing takes one step, regardless of the length of the string, but copy-paste to multiply the length by n takes n steps, in the interest of making it so that a finite number of steps will only have a finite number of possibilities. Then, all these chains are grouped by their final value, and the one with the fewest keystrokes for each group is selected. Then, if that result has fewer keystrokes than the absolute minimum number of keystrokes in a 21-step chain (the minimum of 21 times the length of the string, or one times the length of the string plus copy-pasting 20 times) then the result is definitely the shortest possible, so it's output. All those question marks, and all the numbers higher than the maximum, are values that were either never reached, or the shortest candidate was longer than the shortest possible 21-step chain.

[edit again]
Actually, if you remove the backspace option I threw in, I think this could be solved dynamically without too much trouble... if you have the solutions for 0 through n-1, then you can probably find the solution for n reasonably quickly, 'cause you don't have that many options to check, just n-1 and all of n's factors... Backspace complicates that a little, though.

Code: Select all

enum ಠ_ಠ {°□°╰=1, °Д°╰, ಠ益ಠ╰};void ┻━┻︵​╰(ಠ_ಠ ⚠) {exit((int)⚠);}
[he/him/his]

Siyko
Posts: 3
Joined: Sat Nov 21, 2009 3:04 am UTC

### Re: The mathematics of CTRL-C CTRL-V

Yeah backspace and typing both complicate it - but if it were simple it wouldn't be any fun, would it?

The rules on the space also cause problems. Does it have to end with a trailing space? Probably not, but if x is equal to the length of the string WITHOUT the space this means backspacing an instance costs (x+1) while typing in one on the end costs (x), and typing two on the end costs (2x+1).

Nobody has mentioned that we can also pick how much we want to highlight (remember no mouse). If I want to make exactly 19 copies of 'this is spam' (13 with trailing space), then I can do

13 + ctrl+ acv^7, a shift+(leftarrow * 13), ctrl+ c v^3

This doesn't save time over typing it out (since i have to hit leftarrow the same amount of times as the original string), but for larger numbers this might save time if we need to add on multiples of a specific number.

edahl
Posts: 61
Joined: Wed May 13, 2009 12:15 pm UTC

### Re: The mathematics of CTRL-C CTRL-V

Regarding this, I've reached the conclusion after a bunch of coding, that errors are invariant under copy-paste transformations.

Yakk
Poster with most posts but no title.
Posts: 11129
Joined: Sat Jan 27, 2007 7:27 pm UTC
Location: E pur si muove

### Re: The mathematics of CTRL-C CTRL-V

Oh ya -- ctrl-shift-arrow moves by words. One of the painful things about our time is that those who feel certainty are stupid, and those with any imagination and understanding are filled with doubt and indecision - BR

Last edited by JHVH on Fri Oct 23, 4004 BCE 6:17 pm, edited 6 times in total.

joeframbach
Posts: 1478
Joined: Sun Nov 05, 2006 12:49 am UTC

### Re: The mathematics of CTRL-C CTRL-V

Use the X copy buffer. Highlight, middle-click (x19).

SGI32127
Posts: 19
Joined: Sun Mar 07, 2010 8:44 am UTC

### Re: The mathematics of CTRL-C CTRL-V

joeframbach wrote:Use the X copy buffer. Highlight, middle-click (x19).

no middle-click. need more than 19

kevmus
Posts: 56
Joined: Wed Apr 22, 2009 2:35 am UTC

### Re: The mathematics of CTRL-C CTRL-V

Qaanol wrote:Or write a script to do what you need automatically.

Computers are really good at repetitive tasks.

If you have a repetitive task, there is an easy way to get a computer to do it for you.

In PHP
<?while($i<20){echo "this is spam";$i++);?>
43 characters. It's good if you want to type something 1000 times, but scripting is not optimal here.
(unless some code-guru can shorten this up a lot)

Return to “Mathematics”

### Who is online

Users browsing this forum: No registered users and 9 guests