If they do not know about it already, the OP would benefit from knowing more about Linear Programming and Mixed Integer Linear Programming. Many optimization problems can be naturally modeled into LPs or MILPs and there are POWERFUL solvers with decades of theory and optimization behind them already developed to solve them.

> The retry times are integers.

There's no reason the retry times have to be integers. But the number of retries has to be an integer.

The whole diophantine aspect of this seems contrived - where is the integer restriction coming from? Does that make the problem more tractable or more difficult?

This is an interesting approach, but a simpler one is to add a level of indirection by having a supervisor meter requests, including retries, and provide back-pressure as applicable.

Doing so allows other decisions to be made beyond rate limiting, such as prioritization, deferring invocations, memoization, etc.

Wrote something about applying math in modelling a rate-limiting scenario for API clients. Felt like posting it here. Happy to hear your thoughts, HN!