Find a divisibility pattern

Question

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.

The task

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

Answer 1

05AB1E, 21 20 19 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)

Answer 2

Haskell, 63 bytes

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

Try it online!

Answer 3

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!

Answer 4

R, 92 86 85 83 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.

Answer 5

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
}                       //

Answer 6

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

Answer 7

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 
}

Answer 8

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.

Answer 9

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.

Answer 10

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

Answer 11

Husk, 38 33 28 22 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)

Answer 12

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!