[badFEengineer]

nice! an alternative solution I came up with (it's the same intuition as divide and conquer, just a flattened out version, same value of 49):

Just go left to right on each bottle, and keep track of how often each prefix has appeared (i.e. on the first bottle, if you get 1, 0, 0, 1), we'd keep track of: {"1": 1, "10": 1, "100": 1}. Now, if a prefix of length 1 appears 7 times, or a prefix of length 2 appears 3 times, we stop measuring (because there's only 1 left).

In all cases, for 8 bottles you will need 4 measurements, for 4 bottles you will need 3 measurements, 2 bottles will require 2 measurements, and 2 bottles will require 1 measurement. (4 * 8) + (4 * 3) + (2 * 2) + (2 * 1) = 32 + 12 + 4 + 2 = 50. But for the very last bottle, you can just do 0 measurements, by way of process of elimination. so 50 - 1 = 49.

[Jtsummers]

\* or ** to (reliably) put * into your text.

  (4**8) + (4**3) + (2**2) + (2**1) = ...

(4*8) + (4*3) + (2*2) + (2*1) = ...

If you have an * surrounded by whitespace it's left alone but then you have to remember to always surround * by whitespace.