I had a similar problem a few years ago, when I was making gears (and gear shaped objects) in a machine shop on old gear driven machines. We had most, but not all, of the change gears, and when making Worm or Bevel Gears, you'd often have a ratio, and have to work backwards to figure out a set of gears to get as close as possible to that ratio.
I wrote the simplest possible pascal/windows GUI application[1] to simply try all the possible gear combinations, and keep the lowest. I was shocked when it returned an answer in less than a second. I thought for sure I was going to be digging into algorithms like this, but nope... cheap compute saved me. I'd quickly get the gears, and the error in parts per million.
I do feel myself getting Nerd Sniped though... must resist.