Ultimately this is about how primes jump. I will abstract the situation somewhat as there may be related applications which do not spring to my mind.

I want to find small spoilers to Hall's Marriage Theorem for a specific situation. As the index i increases, I will be processing a sequence S_i of subsets of Y, and I want to find the smallest i such that I cannot find an injective map from the subset of indices I processed so far into the union of the S_i such that every i maps to a member of S_i. Here is one way to go about it.

I create an arrangement of tallies for each subset of Y, and set them all to 0. Each time I encounter a set S_i, I increase the tally by 1 for that subset and also for each subset containing S_i. As I do this, if the tally for some subset T goes above the number of elements of T, I stop, for then I have spoiled the injection by violating the marriage condition, and I have then found i.

Unfortunately, this involves a lot of tallies. Is there a faster way to reach the spoiling i ?

Here is my actual application, and a potentially faster way to reach it. I am given number N and I am looking for the smallest i such that there is no injective map f from [N+1,N+i] into the primes such that f(k) divides k. I start by setting p to 2 and generating the smallest p-smooth numbers above N, and stop when I have 2 of them. I advance p to the next (jth ) prime and repeat, lowering my upper bound for I when I have 1 more than j many such smallest p-smooth numbers above N. I stop when the next prime is larger than the difference between N and the largest smooth number. I now have an upper bound on i, but need to do more work to find i. Again, is there a faster way to find the smallest i?

This is reminiscent of a reverse game of Chomp on a certain poset, and likely this corresponds to a type of cover problem, but I haven't put my finger on which type. Maybe register allocation or something in operations research? Suitable references are welcome.

Gerhard "Looking To Break Things Quicker" Paseman, 2017.04.30.