The question is: to divide a plane into X pieces, how many lines (cuts) are needed? Magically, the answer is found on page 499 of Knuth’s Concrete Mathematics 2nd Ed. (or p485 in this PDF), and is as follows:
N.B. is the binomial coefficient function.
So this solves for regions given the number of cuts. But in this problem we’re to solve it the other way around; this is done via binary search.
My solution is in git and here: