Generating uniform integers in a range from a random generator with another range
I think I can show the optimality of a scheme that I skteched in the question, the one that does rejection sampling but reuses the remaining entropy.

Description of the scheme. Thinking as an algorithm, the scheme is the following. It has two parameters, an integer $n$, and a bound $m$, $0 \leq n &lt; m$, with the invariant that $n$ was drawn uniformly at random in $[0, m[$. (I'll rephrase everything to ranges of the form [0, n[ rather than $\{1, \ldots, n\}$ because it's simpler.)

At each step we do the following:


if $m &lt; q$, then we need more entropy: let $n'$ be the result of calling the oracle that samples in $[0, p[$ uniformly, and recurse with $n := n p + n'$ (i.e., a combination of the current $n$ and the new draw) and $m := m p$ (a larger interval). It is clear that if $n$ is uniform in $[0, m[$ and $n'$ is uniform in $[0, p[$ then the combination $n p + n'$ is uniform in $[0, mp[$
if $m \geq q$, then let $M$ be the largest multiple of $q$ which is smaller than $m$. If $n$ is in $[0, M[$, then we return $n \text{ mod } q$ as the result: this is uniform. Otherwise, the remainder $n - M$ is uniform in the range $[0, m - M[$, so we recurse with $n := n - M$ and $q := q - M$.


In pseudocode, reformulating the second point to substract $q$ multiple times instead of finding $M$, we get the following very simple algorithm:

int algo(int n, int m) {
  // invariant: n is uniform in the range [0, m[
  if (m &lt; q)
    return algo(p*n + randint(p), m * p);  
  if (n &lt; q)
    return n;
  return algo(n-q, m-q);
}

algo(0, 1);


Optimality. This algorithm is, I think, optimal. To see why, let me reformulate it in terms of decision trees. What the algorithm does is, at every level, if we have at least $q$ leaves then turn into leaves the largest multiple of $q$ that you can, and grow the other nodes; otherwise just grow all nodes. (This makes it clear that the scheme is uniform, because the labels in $[0, q[$ on the tree are used in exactly the same way.)

Let us consider the (generally infinite) tree $T$ obtained by such a scheme, and consider a hypothetical tree $T'$ which denotes a uniform strategy with a better expected score.

It is clear that the performance of the tree depends only on the number of internal nodes at every depth. In other words, if I can show that, at every level, the number of internal nodes of $T'$ is at least that of $T$, then $T'$ cannot be better than $T$.

But consider any depth $k$. It is clear that, in $T$, the number of internal nodes is precisely $p^k - M$ for $M$ the largest multiple of $q$ which is below $p^k$: let's write $M = mq$. Now if $T'$ does better than this and has less than this number of internal nodes, let us divide the $p^k$ possible outcomes at depth $k$ of $T'$ between the decided ones and the yet undecided ones: more than $mq$ must be decided (to be better than $T$) and they must be split between $q$ outcomes, so the most probable outcome $v$ at that level must have probability at least $(m+1)/p^k$. Now by maximality of $m$ we have $(m+1)q &gt; p^k$, so that $(m+1)/p^k &gt; 1/q$. But by uniformity the probability of $v$ overall (so, in particular, at depth $k$) should not be more than $1/q$. So $T'$ cannot be uniform: outcome $v$ has probability $&gt; 1/q$.

Hence, $T'$ never does better than $T$.

Expected performance. To compute the expected performance of this optimal strategy, one can just write out an equation system based on which recursive calls are performed by the pseudocode above (with the indicated probability distribution). The value of the parameters is bounded, so presumably, for given values of $p$ and $q$, this should be solvable as a geometric series or something like that. (This can be interpreted as an equation system describing the expected number of draws required for a decision forest with $n$ root nodes, $n$ being the number of nodes at the current level.)

Extending to multiple draws. One can generalize this scheme to draw multiple values, in the following way: when you have made a draw in $[0, q[$, instead of starting at a single-root decision tree for the next draw, start at a forest with $m$ nodes, the number of the outcomes with the same label at the level at which you decided, to use this remaining entropy. My conjecture would be that the resulting scheme would have the same performance as the $p$- and $q$-ary solution sketched in my question (so be optimal for multiple draws while concluding faster for a single draw). I have no proof of this fact, though.