#OK to post homework
#Kent Mei, 9/13/2020, Assignment 1

#----------------------------
#Part 1

gcd(28743,552805);
#11
ithprime(100);
#541
diff(x^3+3*x,x);
#3*x^2+3

#----------------------------
#Part 2

#F(6) = {[1,1,1,1,1,1],[2,1,1,1,1],[1,2,1,1,1],[1,1,2,1,1],[1,1,1,2,1],[1,1,1,1,2],[2,2,1,1],[2,1,2,1],[2,1,1,2],[1,2,2,1],[1,2,1,2],[1,1,2,2],[2,2,2]}

#----------------------------
#Part 3

#L2 := [op(L1),Mars];
#We initialize WALKS(m,n) with either m or n negative to be the Empty set because there is no way to get to a negative coordinate using only positive steps.
#We initialize WALKS(0,0) to be the singleton set {[]} because there is exactly one way to get to (0,0) from (0,0) and that's by doing nothing. This contrasts from the previous one because there is a way to get to that coordinate though.

#-----------------------------
#Part 4

F:= proc(n) local W1,W2,w1,w2:
option remember:

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

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

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

W1 := F(n-1):
W2 := F(n-2):

{seq([op(w1),1],w1 in W1), seq([op(w2),2],w2 in W2)}:

end:

F(6);
#F(6) = {[2, 2, 2], [1, 1, 2, 2], [1, 2, 1, 2], [1, 2, 2, 1], [2, 1, 1, 2], [2, 1, 2, 1], [2, 2, 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, 1, 1, 1, 1]}
#The output is the same as what I found by hand, although in a different order.

#-----------------------------
#Part 5

NuF:= proc(n) option remember:


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

if n <= 1 then 
	RETURN (1):
fi:

NuF(n-1) + NuF(n-2):

end:


{seq(nops(F(n)) - NuF(n), n = 1..10)};
#{0} which mean nops(F(n)) and NuF(n) agree for n = 1..10.

NuF(1000);
#NuF(1000) = 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501

#Maple would try to complain if we tried to do nops(F(1000)) because in that case, 
#Maple would have to generate all the lists from F(1) to F(1000) and then count the number of operands
#in those lists, which is much more computationally expensive than adding two numbers over and over as 
#is the case in the NuF() procedure.