# 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 1
2 [] -> 2 0
2 [1] -> 3 1
2 [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 [1] -> 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
• @DominicvanEssen Sorry it was me by accident! - couldn't figure how I got downvoted by -1 T_T Looked it up and saw the only way was if I downvoted someone. It's my "!$%&*" touchpad that I can't turn off - so sorry again. Oct 7 '20 at 21:21 # JavaScript (ES6), 85 83 82 bytes Expects (b)(s), where s is a Set. Returns [n, k]. b=>s=>{for(n=k=0;(g=x=>x&&n%(x+k)>0^s.has(x)|g(x-1))(b,k=k?k-1:++n););return[n,k]}  Try it online! ### Commented b => s => { // b = upper bound; s = set of integers for( // main loop: n = k = 0; // start with n = k = 0 ( // g = x => // g is a recursive function taking x: x && // stop if x = 0 n % (x + k) > 0 // otherwise yield 1 if x + k does not divide n ^ s.has(x) // XOR with 1 if x belongs to the set | g(x - 1) // recursive call with x - 1 )( // initial call to g: b, // start with x = b k = // update k: k ? k - 1 // decrement k if it's not equal to 0 : ++n // otherwise, increment n and set k to n ); // end of call to g; break if it's falsy ); // end of loop return [n, k] // return the result } //  # Jelly, 19 bytes Ż⁴+þ⁸%T€i© 1ç1#‘,®’  A full program accepting the set, $$\S\$$, and the upper bound, $$\b\$$, which prints the variables as a list, $$\[n,k]\$$. Try it online! Or see the test-suite (without the two longest-running inputs). Kindly provided by FryAmTheEggman. ### How? 1ç1#‘,®’ - Main Link: S, b 1 - set left to 1 1# - count up starting at x=left finding the first x which is truthy under: ç - call the helper Link as a dyad - f(x, S) ‘ - increment -> n+1 ® - recall the value from the register -> k+1 , - pair -> [n+1, k+1] ’ - decrement -> [n, k] - implicit print Ż⁴+þ⁸%T€i© - Link 1: potential_n, S Ż - zero-range -> [0..potential_n] (the potential k values) ⁴ - program's 4th argument, b þ - table of (implicitly uses [1..b]): + - addition ⁸ - chain's left argument -> potential_n % - modulo (vectorises) T€ - truthy 1-based indexes of each i - first index of (S); 0 if not found © - copy that to the register and yield it  • Here you go. The longer cases were taking a while so I commented them out. Oct 6 '20 at 21:51 • Thank you very much @FryAmTheEggman! Oct 7 '20 at 11:35 # C (gcc), 129 $$\\cdots\$$ 111 109 bytes x;s;n;k;f(b,S){for(s=n=1;s;++n)for(k=0;k++<=n&&s;)for(x=b,s=S;x--;)s-=!(n%(x+k))<<x;printf("%d %d",n-1,k-2);}  Try it online! Takes $$\S\$$ as an inverted bitmask of length $$\b\$$ and outputs $$\n\$$ and $$\k\$$ to  stdout. ### Explanation f(b,S){ // function f takes b as an int and S as a // inverted bitmask - the least significant // b-bits of S are unset only if that bit position // corresponds to a member of the original set S for(s=n=1; // loop starting with n=1 and s temporarily // set to 1 just to pass the first two loop tests s; // loop until s is 0 ++n) // bumping n up by +1 each time for(k=0; // inner loop trying values of k starting at 0 k++ // k is bumped up by +1 before use to offset b // which will be 1 less than needed <=n // loop until k is +1 greater than n &&s;) // or until we've hit our target for(x=b, // another nested for loop of x starting at b-1 s=S; // first real init of s to input bitmask x--;) // loop from b-1 down to 0 // which corresponds to b down to 1 // since x is offset by -1 s-=!(n%(x+k))<<x; // subtract off from s bits corresponding to values // for which n%(x+k) is false - because it's the // inverted bitmask // s will be 0 at the end of this most inner loop // iff n and k are our minimal targets printf("%d %d", // once we've discovered the smallest n and k n-1, // we need to compensated for loop increments k-2); // and k being offset by +1 }  # Charcoal, 32 29 bytes Ｗ¬№ωθ≔⭆⁺Ｌ⊞ＯυθＬθ¬﹪Ｌυ⊕κωＩ⟦Ｌυ⌕ωθ  Try it online! Link is to verbose version of code. Takes $$\ S \$$ as an inverted bitmask of length $$\ b \$$ and outputs $$\ n \$$ and $$\ k \$$ on separate lines. Explanation: Ｗ¬№ωθ  Repeat until the desired bitmask is found in the current bitmask. ≔⭆⁺Ｌ⊞ＯυθＬθ¬﹪Ｌυ⊕κω  Increment $$\ n \$$ and calculate the full bitmask for $$\ 1 \leq k + x \leq n + b \$$. Ｉ⟦Ｌυ⌕ωθ  Output $$\ n \$$ and the index $$\ k \$$ of the input bitmask $$\ S \$$ in the full bitmask. # Brachylog, 27 bytes ∧.Ċℕᵐ≥₁fʰgᵗz≜-ᵐF&h⟦₁;Fx~t?∧  Try it online! ### How it works ∧.Ċℕᵐ≥₁fʰgᵗz≜-ᵐF&h⟦₁;Fx~t?∧ . The output is Ċ [N, K], where … ℕᵐ N ≥ 0 and K ≥ 0, and … ≥₁ N ≥ K. fʰ Factors of N z zipped with gᵗ K: ≜-ᵐ label and take K from every factor. F Save the result as F. &h⟦₁ [1, …, b] ;Fx without the elements in F ~t? is S. ∧ Return output.  # K (ngn/k), 63 54 bytes {{(n+^k),k:*&(&/x=)'~(n(1+)\y)!''n:*z}[^y?x;x:1+!x]/1}  Try it online! • {{...}[^y?x;x:1+!x]/1} set up a "converge" / starting with an n of 1, fixing y as 1..b, and x as a boolean mask indicating whether or not each value of 1..b is present in S (1s if not present, 0s if present). each invocation returns a pair of integers, (n;k), with the execution ending when a valid k is identified • n:*z store the first value of z in n • (n(1+)\y) generate a (n+1)-by-b matrix; columns represent potential values of x, with rows representing potential values of k • ~(...)!''n identify pairs where k + x divides n • (&/x=)' determine if each pair is invalid because x is in (or not in) S, then determine if all xs are valid for this k • k:*& identify the first valid k (if there isn't one, this returns 0N, an integer null) • (...),k append the identified value of k... • (n+^k) to n if a valid k was identified, or an incremented n if not # Husk, 38332822 24 bytes Edits: -5 bytes thanks to Razetime, then -6 bytes thanks to Zgarb, then +2 bytes to fix bug that failed to find solutions for which k is zero §,o←ḟVImλVö=²Wḣ⁴%¹+ŀ)N  Try it online! Arguments are integer b and list S; outputs pair of integers (k,n). My second Husk answer, and it took me ages to get it to work at all, so I suspect it can still be golfed-down a lot quite significantly golfed-down by Razetime & Zgarb... Checks increasing values of n, and calculates the lowest k that can satisfy S == (n%(b+k)>0). Then retrieves this value, and its index, as k and n, respectively. Edit: In its original form, this missed solutions with k equal to zero, since this is the same result as failing to find a valid k. So now edited to calculate k+1, and then subtract 1 after retrieving the value. How? mλVö=²Wḣ⁴%¹+ḣ)N # part 1: calculate first value of k+1 for each possible n m # map function to each element of list N # N = infinite list of natural numbers λVö=²Wḣ⁴%¹+ḣ) # lambda function taking 1 argument: V ŀ # find the first 1-based index of k in 0..n with a truthy result of ö=²Wḣ⁴%¹+ # function to check if true indices of n%(k+b) are equal to S ö # composition of 4 functions + # add b %¹ # mod n Wḣ⁴ # get set of truthy indices of 1..b =² # is this equal to S? # (note that because we take the 1-based index # of a range from 0..n, this part calculates k+1, # or zero if there is no valid k) §,o←ḟVI # part 2: return the first k, n § # fork: apply func1 to the results of func2 & func3 , # func1 = join as pair o←ḟ # func2 (takes 2 args, 2-part fucntion combined using o): # increment the first truthy element of arg1 (a function) applied to arg2 (a list) V # func3 (takes 2 args): first truthy index of arg1 (a function) applied to arg2 (a list) I # arg1 for both func2 & func1 = identity function # arg2 for both func2 & func1 is part1 above: the first k for each n (if any)  • (I'll be adding more golfs, add them in when I post a tio link) o←ηf becomes VI Oct 11 '20 at 4:08 • ←ηfmo=² becomes ηḟmo=² Oct 11 '20 at 4:16 • o←↓¬ becomes ḟI Oct 11 '20 at 4:24 • Try it online!(28 bytes) I've never used η before, so I haven't touched most of the things in the lambda. Oct 11 '20 at 4:30 • @Razetime Thanks x3! (same for me re:η, but luckily ηf is specifically mentioned in the Husk wiki as a common use-case!) Oct 11 '20 at 8:07 # Perl 5-p, 70 bytes /,/;++$k>$n?$k=0*++$n:0until"@{[grep$n%($k+$_),1..$]}"eq$';$_="$n $k"  Try it online! or less understandable and trickier 68 bytes # -lp, 68 bytes /,/;++$\>$,?$\=0*++$,:0until"@{[grep$,%($\+$_),1..$]}"eq$';$_="$, "


Try it online!