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.



A faster way to spoil an injection?
Bipartite matching.


I am using a refactored version of an algorithm of Hopcroft and Karp found at 
<https://en.wikipedia.org/wiki/Hopcroft>–Karp\_algorithm . I found that instead of reintializing the Pairu and Pairv arrays for each run, I can modify them from the previous run to take advantage of previous work. I may post AWK code here later after I have finished tweaking it. I do not have asymptotics for this version, but even running the algorithm every time a new index and set is added is better than cubic in the number of vertices for low degree situations, which is what I have (average set size is less than 4).


Gerhard "Spared No Rods For This" Paseman, 2017.10.26.


