The point of this entry is the math problem at the end... which is really most of the entry

[sniffnoy]

Gah. Mr. Holbrook messed up and gave me the regional Mandelbrot and I didn't even notice. Well, 9+2ε.

I don't really have much to say, except this really neat problem from the 1986 AIME (#7):

Consider the sequence 1, 3, 4, 9, ... of all numbers which are powers of 3 or sums of distinct powers of 3 (see subject for first few terms). Find the 100th element of this sequence.

Apparently you can do it a straightforward and painful way, but there's also a really neat solution which makes it really easy which I saw immediately, but so far nobody else I've told it to has. Not that I've told it to too many people.

-Sniffnoy

--
"Entropy ain't what it used to be."
-Aquarion, afda

Comments

[kalo-khei.livejournal.com]

Got it.

Sequence contains those numbers that can be represented by 1's and 0's in base 3. When arrange in order in base 3, they are 1, 10, 11, 100, etc., i.e. counting in binary. 100 = 1100100 base 2, 1100100 base 3 = 9 + 243 + 729 = 981

[ahhhdontpokeme.livejournal.com]

I had a parallel solution. For any integer n >= 2 , n^0 + n^1 + ... + n^(x-1) < n^x (x an integer > 0). Thus, for any n^x, all combinations of all terms below it sum to less than n^x. Thus there are 2^(x-1) terms below n^x. From there it's pretty easy to jump to representation of 100 in binary and the rest follows as Charlie's solution. (Actually, I didn't think to represent 100 in binary and ended up doing the equivalent of stripping off the digits the stupid way, i.e. - 64 < 100 < 126, yielding 2^6, then 100 - 64 = 36, and repeat. But it's close enough.)