#Ok to post homework
#Tifany Tong, September 12th, 2020, HW #1

# Question Number 1:
# Here are some of the lines I tried out in Maple:
# diff(x^3,x);
# 2/3 + 3/5
# b:= 1-q^7 -q^8 - q^9 + q^15 + q^16 + q^17 - q^24: factor(b);
# p:=(x+y+1)*(x-y+1)*(x-y-1): q:= expand("): coeff(q,x,2);
# isprime(2^101-1)
# v:= Int(4*Pi*x*sqrt(1-x^2),x=0..r): v:= value(v);
# s := 1,8,27,64,125: s[3];

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

# Question Number 3: 
# To convert L1:= [Mercury, Venus,Earth] to L2:=[Mercury,Venus,Earth,Mars], we do [op(L1),Mars].

# We initialize WALKS(m,n) to be the Empty set {} when either m/n/both are negative because these are our initial conditions. This prevents us from an infinite recursion, which will cause 
# the computer to complain and return error messages. Unless we are given improper inputs(not non-negative inputs m and n),
# it should be impossible for us to have the case of m<0 or n<0. 

# We initialize WALKS(0,0) to be the singleton set {[]} because we are trying to go from [0,0] to [0,0]. Doing nothing counts as something - it
# is an empty walk, so we would just return an empty set indicating that we don't need to do any actions to reach our target of [0,0]. This is another intitial condition.

# Question Number 4:
F:= proc(N) 
option remember; 
local OneStep, TwoStep, w1, w2; 
if N < 0 then RETURN({}): fi:
if N = 0 then RETURN({[]}): fi:
OneStep:= F(N - 1):
TwoStep := F(N - 2): 
{seq([op(w1), 1], w1 in OneStep), seq([op(w2), 2], w2 in TwoStep)}:
end:

# The answers I got for F(6) in question 2 and 4 were the same, except I ordered the lists differently within the set.

# Question Number 5: 
NuF := proc(N)
local OneStep, TwoStep;
option remember;
if N < 0 then RETURN(0): fi:
if N = 0 then RETURN(1): fi:
OneStep := NuF(N - 1):
TwoStep := NuF(N - 2):
OneStep + TwoStep:
end:

# NuF(1000) = 70330367711422815821835254877183549770181269836358732742604905087154537118196933579742249494562611733487750449241765991088186363265450223647106012053374121273867339111198139373125598767690091902245245323403501
# Maple would complain if we tried to do nops(F(1000)) because it'd first have to generate all NuF(1000) lists in the set by trying every recursive step first 
# before counting how many lists are in the set. Generating all the lists is very expensive and time consuming.