# Cover a set with multiples

Lets take a set of integers greater than 1 and call it X. We will define S(i) to be the set of all members of X divisible by i where i > 1. Would like to choose from these subsets a group of sets such that

• Their union is the set X

• No element of X is in two of the sets.

For example we can regroup {3..11} as

      {3,4,5,6,7,8,9,10,11}
S(3): {3,    6,    9,     }
S(4): {  4,      8,       }
S(5): {    5,        10,  }
S(7): {        7,         }
S(11):{                 11}


Some sets cannot be expressed in this way. For example if we take {3..12}, 12 is a multiple of both 3 and 4 preventing our sets from being mutually exclusive.

Some sets can be expressed in multiple ways, for example {4..8} can be represented as

      {4,5,6,7,8}
S(4): {4,      8}
S(5): {  5,     }
S(6): {    6,   }
S(7): {      7, }


but it can also be represented as

      {4,5,6,7,8}
S(2): {4,  6,  8}
S(5): {  5,     }
S(7): {      7, }


Our goal is to write a program that will take a set as input and output the smallest number of subsets that cover it in this fashion. If there are none you should output some value other than a positive integer (for example 0).

This is a question so answers will be scored in bytes, with less bytes being better.

## Tests

{3..11}       -> 5
{4..8}        -> 3
{22,24,26,30} -> 1
{5}           -> 1

• If there are none you should output some value other than a positive integer (for example 0). Can't our program result in undefined behaviour instead? – Mr. Xcoder Jul 15 '17 at 16:13
• Also, can you add a test case like [5..5]? Can we receive things like [8..4]? – Mr. Xcoder Jul 15 '17 at 16:14
• @Mr.Xcoder No it may not. Programs should be able to identify impossible cases not just loop forever or crash on them. – Post Rock Garf Hunter Jul 15 '17 at 16:14
• "12 is a multiple of both 3 and 4 preventing our sets from being mutually exclusive": why? I don't see anything else in the problem statement which requires 12 to go into both subsets. – Peter Taylor Jul 15 '17 at 16:14
• Also, what's with the test cases? [22,24,26,30] are all multiples of 2. Are you sure it wouldn't be better to delete this and sandbox it? – Peter Taylor Jul 15 '17 at 16:16

# Python 2, 167 bytes

lambda a:([q for q in range(a[-1])if a in[sorted(sum(j,[]))for j in combinations([[p for p in a if p%i<1]for i in range(2,1+a[-1])],q)]]+[0])[0]
from itertools import*


Try it online!

-9 bytes thanks to Zacharý
-4 bytes thanks to Mr. Xcoder
-2 bytes by using lists instead of sets
-5 bytes by using a in [...] rather than any([a == ...]).
-2 bytes thanks to Mr. Xcoder
-8 bytes by merging statements
-5 bytes thanks to Mr. Xcoder
-7 bytes thanks to Mr. Xcoder / Zacharý
+7 bytes to fix bug
-1 byte thanks to ovs

### note

This is extremely slow for larger maximum numbers because it is in no way optimized; it did not within 2 minutes on Mr. Xcoder's device for [22, 24, 26, 30].

# Clingo, 51 bytes

{s(2..X)}:-x(X).:-x(X),{s(I):X\I=0}!=1.:~s(I).[1,I]


### Demo

$echo 'x(3..11).' | clingo cover.lp - clingo version 5.1.0 Reading from cover.lp ... Solving... Answer: 1 x(3) x(4) x(5) x(6) x(7) x(8) x(9) x(10) x(11) s(3) s(4) s(5) s(7) s(11) Optimization: 5 OPTIMUM FOUND Models : 1 Optimum : yes Optimization : 5 Calls : 1 Time : 0.003s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s) CPU Time : 0.010s$ echo 'x(4..8).' | clingo cover.lp -
clingo version 5.1.0
Reading from cover.lp ...
Solving...
x(4) x(5) x(6) x(7) x(8) s(3) s(4) s(5) s(7)
Optimization: 4
x(4) x(5) x(6) x(7) x(8) s(2) s(5) s(7)
Optimization: 3
OPTIMUM FOUND

Models       : 2
Optimum    : yes
Optimization : 3
Calls        : 1
Time         : 0.001s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s
$echo 'x(22;24;26;30).' | clingo cover.lp - clingo version 5.1.0 Reading from cover.lp ... Solving... Answer: 1 x(22) x(24) x(26) x(30) s(5) s(8) s(22) s(26) Optimization: 4 Answer: 2 x(22) x(24) x(26) x(30) s(3) s(22) s(26) Optimization: 3 Answer: 3 x(22) x(24) x(26) x(30) s(2) Optimization: 1 OPTIMUM FOUND Models : 3 Optimum : yes Optimization : 1 Calls : 1 Time : 0.004s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s) CPU Time : 0.000s$ echo 'x(5).' | clingo cover.lp -
clingo version 5.1.0
Reading from cover.lp ...
Solving...
x(5) s(5)
Optimization: 1
OPTIMUM FOUND

Models       : 1
Optimum    : yes
Optimization : 1
Calls        : 1
Time         : 0.001s (Solving: 0.00s 1st Model: 0.00s Unsat: 0.00s)
CPU Time     : 0.000s

• This seems to not detect cases without solutions like x(3..12). (or do I need to update?). BTW, can you suggest a good introduction to clingo? – Christian Sievers Jul 17 '17 at 12:03
• @ChristianSievers Oops, that was a bug, which I’ve now fixed. It should output UNSATISFIABLE in such a case. I mostly used the Potassco guide. – Anders Kaseorg Jul 17 '17 at 12:12

# Mathematica, 105 bytes

Length@Select[Subsets@Table[Select[s,Mod[#,i]==0&],{i,2,Max[s=#]}],Sort@Flatten@#==Sort@s&][[1]]~Check~0&


Try it online
copy and paste the code with ctrl+v,
paste the input at the end of the code,
hit shift+enter to run

input

[{3,4,5,6,7,8,9,10,11}]

takes a list as input
outputs 0 if there are none

• Nice use of Check – Keyu Gan Jul 16 '17 at 2:27
• Why didn't you undelete your first answer once you had a working version? – Neil Jul 16 '17 at 15:41
• Because this was a totally new approach? Is there a problem? – J42161217 Jul 16 '17 at 15:43

## Haskell, 136 bytes

import Data.List
f l|m<-maximum l=(sort[n|(n,c)<-[(length s,[i|j<-s,i<-[j,2*j..m],elem i l])|s<-subsequences[2..m]],c\\l==l\\c]++[0])!!0


Try it online!

How it works

f l     =                           -- input set is l
|m<-maximum l                    -- bind m to maximum of l
[   |s<-subsequences[2..m]]  -- for all subsequences s of [2..m]
(length s, )                -- make a pair where the first element is the length of s
[i|j<-s,i<-[j,2*j..m],elem i l]
-- and the second element all multiples of the numbers of s that are also in l
[n|(n,c)<-       ,c\\l==l\\c]  -- for all such pairs (n,c), keep the n when c has the same elements as l, i.e. each element exactly once
sort[ ]++[0]                     -- sort those n and append a 0 (if there's no match, the list of n is empty)
(     )!!0                         -- pick the first element


Take a lot of time for {22,24,26,30}.

# Jelly, 38353433312825242320 19 bytes

ṀḊŒPð%þ@⁹¬Sḟ1ðÐḟL€Ḣ


-5 bytes thanks to Leaky Nun

Try it online!

I think the third test case works, but it is very slow. 0 is outputted when there are no solutions.

Explanation (might have gotten this explanation wrong):

ṀḊŒPð%þ@⁹¬Sḟ1ðÐḟL€Ḣ     (input z)
ṀḊ                      - 2 .. max(z)
ŒP                    - powerset
ð                   - new dyadic chain
%þ@⁹               - modulo table of z and that
¬              - logical not
S             - sum
ḟ1           - filter out 1's
ðÐḟ        - filter out elements that satisfy that condition
L€      - length of each element
Ḣ     - first element

• 18 bytes – Leaky Nun Jul 16 '17 at 12:53
• Thanks! And thank you for not submitting that yourself! – Zacharý Jul 16 '17 at 13:26
• I've got a different 18 byte solution closer to my original, I personal like this one better: ṀḊŒPðḍ@þ@⁹Sḟ1ðÐḟḢL – Zacharý Jul 16 '17 at 13:29
• Woah... ṀḊ actually is a really cool trick! – Zacharý Jul 16 '17 at 13:30
• Whoops, that doesn't work, and neither does my rewrite! This should output 0, not 1 – Zacharý Jul 16 '17 at 13:48

# Julia, 91 bytes

x->(t=[];for i in x z=findfirst(x->x==0,i%(2:maximum(x)));z∈t?1:push!(t,z) end;length(t))

• Um ... did you forget to include a link within the language name, or is it actually named "[Julia]"? – Zacharý Jul 16 '17 at 15:04
• You are right, the name is Julia without brackets – Tanj Jul 16 '17 at 15:08
• You might want to fix that on your other answers as well! – Zacharý Jul 16 '17 at 15:09
• Wow, that was a lot of answers! And if you want to insert a link, the syntax is [Text to display](link to website) – Zacharý Jul 16 '17 at 15:23