# OK to post hw
# Michael Yen, 9/13/20, Assignment 1

# 1. Random Maple Lines
# p := x^2+5*x+6;
# factor(p);

# p := (x+2)*(x+3);
# expand(");

# sqrt(x+2)*sqrt(x+3);
# combine(");

# type(T,set);
# convert(A,list);

# f:=x->x^2-3*x+5;
# diff(f,x);

# Int(1/x/sqrt(x^2-1),x=1..2/sqrt(3));
# value(");

# 2. Human Problem: Let F(n) be the set of lists using {1,2} that add-up to n. For
# example, F(0)={[]}, F(1)={[1]}, F(2)={[1,1],[2]}, F(3)={[1,1,1],[1,2],[2,1]}.
# Write down F(6).
#
# F(6)={[1,1,1,1,1,1],[1,1,1,1,2],[1,1,1,2,1],[1,1,2,1,1],[1,2,1,1,1],[2,1,1,1,1],
# [1,1,2,2],[1,2,1,2],[2,1,1,2],[2,1,2,1],[2,2,1,1],[1,2,2,1],[2,2,2]}
# |F(6)|=1+5+6+1=13

# 3. Understand the Maple Code
#
# What Maple line converts L1:=[Mercury,Venus,Earth] to
# L2:=[Mercury,Venus,Earth,Mars]?
# L2:=[op(L1), Mars]
#
# Explain, in Plain English, why we initialize WALKS(m,n) with either m or n or both
# negative to be the Empty set {}
# m and n are both supposed to be non-negative positive integers. If either m or n or both
# are negative, there are no possible walks to achieve this because we assume each step
# is in a "positive" direction; only N and E are allowed, thus the empty set.
# 
# Explain, in Plain English, why we initialize WALKS(0,0) to be the singleton set {[]}
# There is one way to achieve this: take 0 steps - no N steps and no E steps. This
# is represented by {[]} since a solution exists, it just requires not taking any steps.

# 4. Write a Maple procedure, F(n), that inputs a non-negative integer n and outputs the
# set of lists in {1,2} that add-up to n. Compare the output of F(6) to the one that you
# found above by hand.

F:=proc(n) local F1,F2,f1,f2:
option remember:

if n<0 then
 RETURN({}):
fi:

if n=0 then
 RETURN({[]});
fi:

F1:=F(n-1):
F2:=F(n-2):

{seq([op(f1), 1],f1 in F1), seq([op(f2),2],f2 in F2)}:

end:

# The output for F(6) is the same as the result I calculated by hand.

# 5. Write a Maple procedure, NuF(n), that inputs a non-negative integer n and outputs the
# NUMBERS of lists in {1,2} that add-up to n. Make sure that nops(F(n))=NuF(n) are equal
# for n=1..10
# What is NuF(1000)? Why would Maple complain if you tried to do nops(F(1000))?

NuF:=proc(n) local F1,F2,f1,f2:
option remember:

if n<0 then
 RETURN(0):
fi:

if n=0 then
 RETURN(1);
fi:

F1:=NuF(n-1):
F2:=NuF(n-2):

F1+F2:
end:

# NuF(1000) is 
#70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501.
# Although I did not see any specific complaint by Maple when I tried to do nops(F(1000)), I
# would think that Maple may run out of memory or take an extremely long time before it ever
# finishes calculating nops(F(1000)) - the number is too big (I didn't try waiting to see how
# long it would take).