Why stop there? If you switch to triples (10 flips, reroll on 1000-1023) then you can get an amortized cost of about 3.4 flips per d10. That's very close to the

Why stop there? If you switch to triples (10 flips, reroll on 1000-1023) then you can get an amortized cost of about 3.4 flips per d10. That's very close to the ideal outcome of log2(10) ~= 3.32 flips. Above 3d10 the rate of re-rolls increases; 20 flips for 6d10 gives a worse amortized cost than two sets of three.