Math Is Fun Forum

Dragonshade

Member

Registered: 2008-01-16

Posts: 147

just came up with a problem

I came up with this when I was playing games on my comp

It goes like this: What is the least number of operations it takes to type 10000 letters A. (You have two operations, just by pressing "A" , or copy&Paste.  Pressing "A" counts as 1 operation,  Copy and Paste counts as 2)

I don't know if this can be generalized, I think the solution would be different for large number opposed to the small number of A

I think the least number of operation, goes like, 
First type

number of  As,
then keep copying and pasting the whole thing , r times until it gets the closest it can get to the total number of A

Use letter e to denote the remainder

The number of operations would be

thats as far as I can get : (

Last edited by Dragonshade (2009-11-18 10:02:10)

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: just came up with a problem

Here's my way of making 10000:

No. of A's / Keystrokes

1/1
2/2
4/4
8/6
9/7
18/9
19/10
38/12
39/13
78/15
156/17
312/19
624/21
625/22
1250/24
2500/26
5000/28
10000/30

That does it in 30 presses. If it's not optimal, I'm guessing it's close.

I did that by going backwards from 10000, dividing by 2 when I could and subtracting 1 otherwise.
One exception to that is that I got from 2 to 1 by subtracting rather than dividing, since that's cheaper.

---

Why did the vector cross the road?
It wanted to be normal.

Dragonshade

Member

Registered: 2008-01-16

Posts: 147

Re: just came up with a problem

Looks like you are using 1, as the base
I put n=1 into my formula's, then I got
2^13 = 8192,
number = 2+13*2+2=30

oh yeah, I should have made it clear, that you could paste any portion of the As, if not, its hard to make it to 10000 precisely
sorry about that
So its like, when you pass 5000, you could reach 10000 in one copy and paste....
but wait, that doesnt sound really realistic...I think your solution might be the best

Last edited by Dragonshade (2009-11-18 12:05:00)

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: just came up with a problem

Oh, OK. If you don't have to C&P the whole thing, your way is probably best.

Get 2 A's with two presses, then double that 12 times to get 8196 in 26 presses.
Now you can C&P the remaining A's you need, and it's done with 28 operations.

---

Why did the vector cross the road?
It wanted to be normal.

simplyjasper

Member

Registered: 2009-11-15

Posts: 24

Re: just came up with a problem

I think there is a need for restriction?
Things like
- u can't copy only a portion of the 'a's u type
- deleting is counted as 1 operation

Else it is pretty simple ...

What mathsyperson did was the best
or in another way would be type 4 'a's and do that 11 times

As typing 4 'a's and typing 2 'a's then copy and paste yield 4 operations

Dragonshade

Member

Registered: 2008-01-16

Posts: 147

Re: just came up with a problem

Yea, I agree that I have to restrict it, so that I have to C&P the entire thing
then Mathsyperson's solution should be the best
since C&P a portion of it, doesnt sound possible when the number is huge 

Last edited by Dragonshade (2009-11-18 15:21:33)

mathsyperson

Moderator

Registered: 2005-06-22

Posts: 4,900

Re: just came up with a problem

Ooh, I like jasper's twist. If we were also allowed to delete one A at the cost of one keystroke, that makes the problem a little more complex.

For example, my suggestion from before could be improved by replacing:

...4, 8, 9, 18, 19, 38, 39...

with

...4, 5, 10, 20, 40, 39...

To go from 4 to 39 originally cost nine keystrokes, but now would only cost eight.
That's just one example of an improvement though. I'm not sure what the new best solution would be.

---

Why did the vector cross the road?
It wanted to be normal.

simplyjasper

Member

Registered: 2009-11-15

Posts: 24

Re: just came up with a problem

I didn't really came out with the twist... I remembered doing one such problem before haha...
It was in my number theory or algebra module

Last edited by simplyjasper (2009-11-19 03:20:06)