Spoiler for It seems to me...that for each digit in the binary representation, if your coin flip is not the outcome representing the digit, you stop. So 50% chance of needing another coin flip at any point in the process.

So there's a 50% chance of it taking only 1 flip.

There's a 25% chance of it taking 2 flips.

There's a 12.5% chance of it taking 3 flips.

etc.

So the infinite sum for the average flips needed is the sum from i=1 to infinity of i/(2^i).

f(y) = sum x=1 to inf xy^-x

f(y)/y = sum x=1 to inf xy^-(x+1)

integrate (f(y)/y) + c = sum x=1 to inf -y^-x

-integrate (f(y)/y) + c = (1/y)/(1-(1/y))

-integrate (f(y)/y) + c = (1/y)/((y-1)/y)

-integrate (f(y)/y) + c = 1/(y-1)

integrate (f(y)/y) + c = -1/(y-1)

f(y)/y = d(-1/(y-1))/dy

f(y)/y = d(-(y-1)^-1)/dy

f(y)/y = (y-1)^-2

f(y) = y(y-1)^-2

Plugging in 2 for y gives f(y)=2.So it takes 2 flips on average.

Of course, it would be easier to formulate it this way...

All need at least 1 flip.

50% need at least an additional 1 flip.

25% need at least an additional 1 flip.

etc.

So 1 + .5 + .25 + .125 + ... = 2.

Great solve. It is indeed surprising how efficient bonanova's and your algorithm is.