#!/usr/local/bin/maple

# Nathaniel Shar

###############
## Problem 2 ##
###############

f2 := proc(n) option remember:

	if n <= 0 then
		1:
	elif n = 1 then
		1:
	elif n = 2 then
		2:
	else
		f2(n-1) + f2(n-2) + f2(n-3):
		# Because the last number in the sum can be either 1, 2, or 3.
	fi:
end:

# The sequence is on OEIS and is A000073 (Tribonacci numbers), though our
# version is offset by 2.

###############
## Problem 3 ##
###############

f := proc(a,b) option remember:

	if a < 0 or b < 0 then
		0:
	elif a = 0 and b = 0 then
		1:
	else
		f(a-1, b) + f(a, b-1):
	fi:
end:

# The sequence is on OEIS and is A000984 (Central binomial coefficients).

###############
## Problem 4 ##
###############

g := proc(a,b) option remember:

	if a < 0 or b < 0 then
		0:
	elif a = 0 and b = 0 then
		1:
	elif a = b then
		g(a-1, b) + g(a, b-1) + g(a-1, b-1):
	else
		g(a-1, b) + g(a, b-1):
	fi:
end:

# This sequence is also on OEIS and is A026671.

###############
## Problem 5 ##
###############

h := proc(a,b) option remember:

	if a < 0 or b < 0 then
		0:
	elif a = 0 and b = 0 then
		1:
	else
		h(a-1, b) + h(a, b-1) + h(a-1, b-1):
	fi:
end:

# This sequence is on OEIS and is A001850.

###############
## Problem 8 ##
###############

with(numtheory);

M := proc(n) option remember:

	add(mobius(i), i=1..n);
end:

# Okay, but using this is too slow
# Let's try again and this time have the function do all the work for us.

CheckConjecture := proc(low, high)

	total := M(low);
	maxratio := 0;
	maxk := 1;
	for k from low+1 to high do
		total := total+mobius(k):
		b := evalf(total^2/k):
		if b > maxratio then
			maxratio := b:
			maxk := k:
		fi:
		if b >= 1 then
			print(total):
			print(k):
			break:
		fi:
	od:
	print(maxratio);
	print(maxk);
	print("Done"):
end:

# This isn't any better.

# I haven't found a counterexample, but I see no reason there couldn't be one.
# The problem with this kind of problem is that the expected number of distinct
# prime factors of n is O(log log n). Since mobius(n) depends on the number of
# distinct prime factors of n, it is very possible that |M(n)| is bounded by
# of something like Csqrt(n)log(log(n)) (or has a bound related to log(log(n))
# in some other way. If this is the case, and C is # smaller than 1/6 or so,
# the conjecture would be false but there would be no hope to find a
# counterexample by just enumerating all the values from 1 upwards.