Find a divisibility pattern

Background

Sometimes when I'm golfing a program, I'm presented with the following situation: I have an integer value $$\x\$$ on some fixed interval $$\[a, b]\$$, and I'd like to test whether it's in some fixed subset $$\S \subset [a, b]\$$ with as few bytes as possible. One trick that sometimes works in a language where nonzero integers are truthy is finding small integers $$\n\$$ and $$\k\$$ such that $$\x \in S\$$ holds precisely when $$\x + k\$$ doesn't divide $$\n\$$, because then my test can be just n%(x+k). In this challenge your task is to compute the minimal $$\n\$$ and $$\k\$$ from the fixed data.

Your inputs are a number $$\b\$$ and a set $$\S\$$ of integers between $$\1\$$ and $$\b\$$ inclusive (we assume $$\a = 1\$$ for simplicity), in any reasonable format. You may take the complement of $$\S\$$ if you want. If you take $$\S\$$ as a list, you can assume it's sorted and duplicate-free. You can also assume $$\b\$$ is at most the number of bits in an integer and take $$\S\$$ as a bitmask if you want.

Your output is the lexicographically smallest pair of integers $$\(n,k)\$$ with $$\n \geq 1\$$ and $$\k \geq 0\$$ such that for each $$\1 \leq x \leq b\$$, $$\k+x\$$ divides $$\n\$$ if and only if $$\x\$$ is not an element of $$\S\$$. This means that $$\n\$$ should be minimal, and then $$\k\$$ should be minimal for that $$\n\$$. Output format is also flexible.

Note that you only have to consider $$\k \leq n\$$, because no $$\k+x\$$ can divide $$\n\$$ when $$\k \geq n\$$.

The lowest byte count in each language wins.

Example

Suppose the inputs are $$\b = 4\$$ and $$\S = [1,2,4]\$$. Let's try $$\n = 5\$$ (assuming all lower values have been ruled out).

• The choice $$\k=0\$$ doesn't work because $$\k+1 = 1\$$ divides $$\5\$$ but $$\1 \in S\$$.
• The choice $$\k=1\$$ doesn't work because $$\k+3 = 4\$$ does not divide $$\5\$$ but $$\3 \notin S\$$.
• The choice $$\k=2\$$ works: $$\k+1 = 3\$$, $$\k+2 = 4\$$ and $$\k+4 = 6\$$ don't divide $$\5\$$, and $$\k+3 = 5\$$ divides $$\5\$$.

Test cases

b S -> n k
1 [] -> 1 0
1  -> 1 1
2 [] -> 2 0
2  -> 3 1
2  -> 1 0
2 [1,2] -> 1 1
4 [1,2,4] -> 5 2
4 [1,3,4] -> 3 1
5 [1,5] -> 168 4
5 [2,5] -> 20 1
5 [3,4] -> 6 1
5 [2,3,4,5] -> 1 0
6  -> 3960 6
8 [2,3,6,7] -> 616 3
8 [1,3,5,7,8] -> 105 1
8 [1,2,3,4,5] -> 5814 11
9 [2,3,5,7] -> 420 6
14 [3,4,6,7,8,9,10,12,13,14] -> 72 7
• Can I take S as a 0-indexed list i.e. the values range from 0<=x<b?
– Neil
Oct 6 '20 at 12:23
• @Neil Sure, that's reasonable. Oct 6 '20 at 12:30
• May we take the complement of the set instead? Oct 6 '20 at 13:54
• @Arnauld Sure, that's fine Oct 6 '20 at 14:29
• @LuisMendo 1 does divide 3. Oct 6 '20 at 17:46

05AB1E, 212019 18 bytes

Thanks to Kevin Cruijssen for -1 byte!
-1 byte inspired by xash's Brachylog answer!

[¼¾ƒ²L¾ÑN-K¹Qi¾N‚q

Try it online!
or
Try most test cases! (based on the test-suite by FryAmTheEggman for this answer.)

# see below for the remainder of the code
²L          # push [1 .. b]
¾Ñ        # push the divisors of n
N-      # subtract k from each
# this is now a list of all x in [-k+1 .. n-k] with n%(x+k)==0
K     # remove this from [1 .. b]
¹Q   # is this equal to S?

05AB1E, 24 23 bytes

First line of input is the set $$\S\$$, second one $$\b\$$.

[¼¾ƒ¾¹²L‚N+Ö_O¹gªËi¾N‚q

Try it online!

This iterates through all possible pairs in lexicographical order and checks for each pair:

\begin{align*} \left|S\right| &=\left|\left\{ x \in [1 .. b] \mid x \;\text{does not divide}\; n \right\}\right| \\&= \left|\left\{ x \in S \mid x \;\text{does not divide}\; n \right\}\right| \end{align*}

Commented:

[                # infinite loop
¼¾              # increment and push the counter (n)
ƒ             # for N(=k) in [0 .. n]:
¾                #   push n
¹               #   push the first input (S)
²L             #   push [1 .. second input (b)]
‚            #   pair these two lists up
N+          #   add current k to both lists
Ö_        #   do they not divide n (vectorizes)
O       #   sum both lists
¹g     #   push the length of S
ª    #   append this to the list
Ë   #   are all equal?
i                #   if this is true:
¾               #     push n
N              #     push k
‚             #     pair n and k
q            #     quit the program (implicit output)
• Nice alternative 20-byter. You can drop the Θ though, since only 1 is truthy in 05AB1E, so just the Pi is enough. Oct 6 '20 at 15:17
• @KevinCruijssen thanks a lot!
– ovs
Oct 6 '20 at 15:20

b!s=[(n,k)|n<-[1..],k<-[0..n],[x|x<-[1..b],mod n(k+x)>0]==s]!!0

Try it online!

Python 3, 110 91 89 bytes

Saved a whopping 19 21 bytes thanks to Jitse!!!

Blows up on TIO because of insane recursion depths! :(

f=lambda b,S,n=1,k=0:S==[x+1for x in range(b)if n%(k-~x)]and(n,k)or f(b,S,n+k//n,-~k%-~n)

Try it online!

• Can be 91 bytes using recursion, but TiO can't finish all tests. Oct 7 '20 at 12:55
• @Jitse Yeah, had similar issues when I went down that path. Think it's ok though, since in principal it's correct - thanks! :-) Oct 7 '20 at 13:30
• Also (n>k)*-~k can be -~k%-~n for -2 bytes. Oct 7 '20 at 13:34
• @Jitse Very nice - thanks! :D Oct 7 '20 at 13:40

R, 92868583 82 bytes

Edit: -2 bytes thanks to Giuseppe, then -1 more byte thanks to Robin Ryder

function(b,S)repeat for(k in 0:(F=F+1))if(all(1:b%in%S-!F%%(1:b+k)))return(c(F,k))

Try it online!

Tests increasing velues of n (actually defined as F here, to exploit its default initial value of zero), and for each one loops through all k and returns F,k if they satisfy !F%%(x+k) != x %in% S for all x in 1:b.

Now 6 bytes shorter than my previous recursive version, and it can actually complete all the test cases without needing to increase the R recursion limit and allocated stack size.

• 83 bytes by reversing the comparison order. Oct 7 '20 at 17:53
• @Giuseppe Thanks! I kind-of thought that there were too many parentheses... Oct 7 '20 at 19:41
• Couldn't that != be a - for -1 byte? Oct 7 '20 at 19:50
• I know the feeling: it probably took half-a-dozen comments from @Giuseppe on various answers of mine before I started remembering that seq(a=...) exists. :-) Oct 7 '20 at 19:59

Try it online!