...and, it looks like I generalized too quickly

[sniffnoy]

...did I say my proof worked for a≤19? I meant 18, apparently. Did I say 3log₃(3/2)? I meant 3log₃(4/3) (minus the exceptions - though the better bound is still often true). Oops. (Still have yet to prove *this*, mind you, but I'm pretty certain.)

-Harry

Comments

[jonpin.livejournal.com]

OK, are you doing two separate problems, or is this something related to the 1+1 problem? I've been confused for a while.
I did, however, think of an application problem which appears to be the 1+1 problem: You wish to create a string with exactly n x's, using only three keys: "x", "Copy all", and "Paste". Find the minimum number of keystrokes needed to make the string. For instance, n=9, you'd do x, x, x, Copy, Paste, Paste. On current thought, it might fail if any solutions have multiple products being added together like (1+1)*(1+1+1) + (1+1+1+1)*(1+1+1+1).

As a show of how boring my life is, I thought of this when looking at a wall of text (consisting of "hahaha" for about 12 lines) and thinking "what's the most efficient way to do that?"

[sniffnoy.livejournal.com]

Yeah, yeah. I was trying to prove that f(2^a3^b)=2a+3b for low a, and ended up coming up with a (mostly) general lower bound, which, while quite bad on the whole, I thought was good enough to prove it for a≤19, but actually is only good enough for a≤18. It's probably silly to put it in those terms, but that is how I was originally thinking about it.