22
\$\begingroup\$

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
\$\endgroup\$
8
  • \$\begingroup\$ Can I take S as a 0-indexed list i.e. the values range from 0<=x<b? \$\endgroup\$
    – Neil
    Oct 6 '20 at 12:23
  • \$\begingroup\$ @Neil Sure, that's reasonable. \$\endgroup\$
    – Zgarb
    Oct 6 '20 at 12:30
  • \$\begingroup\$ May we take the complement of the set instead? \$\endgroup\$
    – Arnauld
    Oct 6 '20 at 13:54
  • \$\begingroup\$ @Arnauld Sure, that's fine \$\endgroup\$
    – Zgarb
    Oct 6 '20 at 14:29
  • \$\begingroup\$ @LuisMendo 1 does divide 3. \$\endgroup\$
    – Zgarb
    Oct 6 '20 at 17:46

12 Answers 12

7
\$\begingroup\$

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)
\$\endgroup\$
2
  • 1
    \$\begingroup\$ Nice alternative 20-byter. You can drop the Θ though, since only 1 is truthy in 05AB1E, so just the Pi is enough. \$\endgroup\$ Oct 6 '20 at 15:17
  • \$\begingroup\$ @KevinCruijssen thanks a lot! \$\endgroup\$
    – ovs
    Oct 6 '20 at 15:20
6
\$\begingroup\$

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!

\$\endgroup\$
6
\$\begingroup\$

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!

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

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.

\$\endgroup\$
8
  • 1
    \$\begingroup\$ 83 bytes by reversing the comparison order. \$\endgroup\$
    – Giuseppe
    Oct 7 '20 at 17:53
  • \$\begingroup\$ @Giuseppe Thanks! I kind-of thought that there were too many parentheses... \$\endgroup\$ Oct 7 '20 at 19:41
  • 3
    \$\begingroup\$ Couldn't that != be a - for -1 byte? \$\endgroup\$ Oct 7 '20 at 19:50
  • 1
    \$\begingroup\$ 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. :-) \$\endgroup\$ Oct 7 '20 at 19:59
  • 1
    \$\begingroup\$ @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. \$\endgroup\$
    – Noodle9
    Oct 7 '20 at 21:21
4
\$\begingroup\$

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
}                       //
\$\endgroup\$
4
\$\begingroup\$

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
\$\endgroup\$
2
  • \$\begingroup\$ Here you go. The longer cases were taking a while so I commented them out. \$\endgroup\$ Oct 6 '20 at 21:51
  • \$\begingroup\$ Thank you very much @FryAmTheEggman! \$\endgroup\$ Oct 7 '20 at 11:35
4
\$\begingroup\$

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 
}
\$\endgroup\$
3
\$\begingroup\$

Charcoal, 32 29 bytes

W¬№ωθ≔⭆⁺L⊞OυθLθ¬﹪Lυ⊕κωI⟦Lυ⌕ωθ

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:

W¬№ωθ

Repeat until the desired bitmask is found in the current bitmask.

≔⭆⁺L⊞OυθLθ¬﹪Lυ⊕κω

Increment \$ n \$ and calculate the full bitmask for \$ 1 \leq k + x \leq n + b \$.

I⟦Lυ⌕ωθ

Output \$ n \$ and the index \$ k \$ of the input bitmask \$ S \$ in the full bitmask.

\$\endgroup\$
3
\$\begingroup\$

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.
\$\endgroup\$
3
\$\begingroup\$

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
\$\endgroup\$
2
\$\begingroup\$

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)
\$\endgroup\$
5
  • \$\begingroup\$ (I'll be adding more golfs, add them in when I post a tio link) o←ηf becomes VI \$\endgroup\$
    – Razetime
    Oct 11 '20 at 4:08
  • \$\begingroup\$ ←ηfmo=² becomes ηḟmo=² \$\endgroup\$
    – Razetime
    Oct 11 '20 at 4:16
  • \$\begingroup\$ o←↓¬ becomes ḟI \$\endgroup\$
    – Razetime
    Oct 11 '20 at 4:24
  • \$\begingroup\$ Try it online!(28 bytes) I've never used η before, so I haven't touched most of the things in the lambda. \$\endgroup\$
    – Razetime
    Oct 11 '20 at 4:30
  • 1
    \$\begingroup\$ @Razetime Thanks x3! (same for me re:η, but luckily ηf is specifically mentioned in the Husk wiki as a common use-case!) \$\endgroup\$ Oct 11 '20 at 8:07
1
\$\begingroup\$

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!

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.