since all sequences of 3 flips with 1 head have the same probability, and all sequences of 3 flips with 2 heads have the same probability (though probably different from the 1 head probability), we can avoid discarding more of the sequences by accepting one sequence from each of the two sets..

For N = 3; if the outcome is:

HHT or TTH, select A

HTH or THT, select B

THH or HTT, select C

Now we only discard HHH and TTT, which occur with probability p^3 and q^3. So expected number of flips E = 3 * (1 - p^3 - q^3) + (E+3) * (p^3+q^3))

E = 3 + E * (p^3+q^3)

E = 3 / (1 - p^3 - q^3)

for p = 0.5, E = 4

for p = 0.1, E > 13

Clearly, generalizing this approach is difficult algorithmically.

for N = 4; pascal's triangle is 1,4,6,4,1 So we can use choose one from each of the 4, one from each of the other 4, and one from each of four of the 6, leaving 4 sequences to be discarded.

for N = 5; 1,5,10,10,5,1 Similar to the 3 case, we can divide the 5, divide the other 5, divide the 10 into 5 pairs, ditto for the other 10, winding up with only two sequences to discard.

for N = 6; 1,6,15,20,15,6,1 we can use 6 of the 6, 12 of the 15, 18 of the 20, 12 of the 15, and 6 of the 6.

for N = 7; 1,7,21,35,35,21,7,1 since all the groups are divisible by 7, we can use up all the cases but all-heads and all-tails.

for N=8; 1,8,28,56,70,56,28,8,1

for N=9; 1,9,36,84,126,126,84,36,9,1

Apparently, for odd N, we can use up all the cases but all-heads and all-tails, so it approaches a very good, if not minimal, numbr of flips.