#OK to post
#Michael Yen, 9/20/20, Assignment 4

#1. Carefully study the Maple code for lecture 4 and find
#CP({a,b,c},{b,c,d}); -> {[a, b], [a, c], [a, d], [b, b], [b, c], [b, d], [c, b], [c, c], [c, d]}#CheckMult({1,2},{3,4}); -> true
#CheckAdd({1,2,3},{3,4,5}); -> {1, 2, 3}, {3, 4, 5}, have the following common elements , {3} FAIL
#member([d,o,r,o,n],Words({d,o,n,r},5)); -> true

#2. [I did not do it myself, and would like to know] In class we searched Neil Sloane's amazing On-Line #Encyclopedia of Integer Sequences for
#1,2,3,4,5,6,7,8,9
#and found 2904 hits.
#Find the smallest positive integer n such that

#1, 2, 3, ....., n (in Maple: seq(i,i=1..n) ) only returns ONE hit, namely A27 [Typo corrected thanks to 
#Tifany Tong]

#At n=106 the only single hit left is A262530, the list of numbers such that digits occur at most twice in 
#decimal representation. At n=105 there is still another hit, A291179, the list of numbers in at least one 
#Fibonacci sequence starting with two 1-digit numbers. For some reason the list of positive integers (A27) 
#disappears at 77; it does not go any higher. If A27 was represented correctly, A262530 goes away at n=111 
#because it jumps from 111 to 112. Thus at n=111 the only hit remaining would have been A27.

#3. The Principle of Inclusion-Exclusion (that we will discuss in Lecture 5) for TWO sets says that that 
#given a UNIVERSAL set U, and subsets A1, A2, defining the COMPLEMENT of a subset A of U by Comp(U,A),
#|Comp(U,A1) intersect Comp(U,A2)|= |U|- |A1|-|A2|+ |A1 intersect A2|

#Do the following

#Check it by hand for U={1,..., 15}, A1= subset of U that are multiples of 3, A2=subsets of U that are 
#multiples of 5

#U={1,2,3,4,5,6,7,8,9,10,11,12,13,14,15}
#A1={3,6,9,12,15} Comp(U,A1)={1,2,4,5,7,8,10,11,13,14}
#A2={5,10,15} Comp(U,A2)={1,2,3,4,6,7,8,9,11,12,13,14}
#|Comp(U,A1) intersect Comp(U,A2)|=|{1,2,4,7,8,11,13,14}|=8
#Using formula |Comp(U,A1) intersect Comp(U,A2)|=15-5-3+1=8
#They are the same!

#Write a Maple procedure
#PIE2(U,A1,A2)

#that inputs three sets U, A1, A2. After checking that U, A1,A2, are indeed sets (return FAIL if they are 
#not) AND that A1 or A2 are NOT subsets of U (return FAIL if they are not), computes it in two ways. The 
#first way by directly finding |Comp(U,A1) intersect Comp(U,A2)| and the second way by using the above 
#formula, namely

#|U|- |A1|-|A2|+ |A1 intersect A2|

#For example the output of

#PIE2({1,2,3,4,5},{1,2,3},{2,3,5})

#should be [1,1]

PIE2:=proc(U,A1,A2) local w1,w2:
option remember:

if not type(U,set) then
 print(U, `is not a set `):
 RETURN(FAIL):
fi:

if not type(A1,set) then
 print(A1, `is not a set `):
 RETURN(FAIL):
fi:

if not type(A2,set) then
 print(A2, `is not a set `):
 RETURN(FAIL):
fi:

if not verify(A1,U,`subset`) then
 print(A1, `is not a subset of U`):
 RETURN(FAIL):
fi:

if not verify(A2,U,`subset`) then
 print(A2, `is not a subset of U`):
 RETURN(FAIL):
fi:

w1:=nops((U minus A1) intersect (U minus A2)):
w2:=nops(U)-nops(A1)-nops(A2)+nops(A1 intersect A2):

[w1,w2]:

end:

#4.[Optional challenge] Do the analogous thing for
#PIE3(U,A1,A2,A3)

#5.[Super Optional super challenge] Do the analogous thing for
#PIE4(U,A1,A2,A3,A4)