# hw23MattHohertz.txt
# answer to last question forthcoming

with(LinearAlgebra):

Fc:=proc(n::posint, K::posint)
	local B, BRsq, lg, i, v:

	B:=Matrix([[1,1],[1,0]]):
	
	lg:=floor(log[2](n)):
	BRsq:=B:

	for i from 1 to lg do
		BRsq:=BRsq^2 mod K:
	od:
	for i from (2^lg+1) to n do
		BRsq:=(BRsq.B) mod K:
	od:
	
v:=BRsq.Vector([1,0]):
	
	v[2] mod K:
end:


Tc:=proc(n::posint, K::posint)
	local B, BRsq, lg, i, v:

	B:=Matrix([[1,1,1],[1,0,0],[0,1,0]]):
	
	lg:=floor(log[2](n)):
	BRsq:=B:

	for i from 1 to lg do
		BRsq:=BRsq^2 mod K:
	od:
	for i from (2^lg+1) to n do
		BRsq:=(BRsq.B) mod K:
	od:
	
	v:=BRsq.Vector([1,0,0]):

	v[3] mod K:
end:


























## BEGIN MRHSTDLIB (helper functions)
insertLines:=proc(n::integer) 
	description "Appends {n} lines.",
	"See also: nl, pskip":
	local i:

	for i from 1 to n do:
		printf("\n");
	od:
end:

nl:=proc(): insertLines(1): end:
pskip:=proc(): insertLines(2): end:

PrintHelp:=proc(LofPs::list(procedure)) 
	description "Prints descriptions for the procedures in {LofPs}."
	:
	local P, i, NProcs:

	NProcs:=nops(LofPs):

	for i from 1 to NProcs do
		P:=LofPs[i]:
		printf("### %s ###", P);
		nl();
		Describe(P);
		pskip();
	od:
end:
## END MRHSTDLIB
Box:=proc(n::nonnegint)
	local S, s;
	if (n=0) then
		return({[]}):
	fi:

	S:=Box(n-1):
	
	{seq([op(s),0], s in S), seq([op(s),1], s in S)}:
end:
IsGG:=proc(v::list)
local i;
	for i from 1 to nops(v) - 1 do
		if v[i] = 1 and v[i+1] = 1 then
			return(false):
		fi:
	od:
	true:
end:
Fsss:=proc(n::nonnegint)
	local rval, i, bx, ct;
	bx:=Box(n):
	ct:=0:
	for i in bx do
		if IsGG(i) then ct:=ct+1: fi:
	od:
	ct:
end:

Fs:=proc(n::nonnegint, K::posint)
	option remember:
	if (n < 2) then
		return(n);
	fi:

	return (Fs(n - 1, K) + Fs(n - 2, K) mod K);
end:
F:=proc(n::nonnegint, K::posint)
	local a, b, c, i:

	a:=0:
	b:=1:

	for i from 1 to n do
		c:=a+b mod K:
		a:=b:
		b:=c:
	od:

	a:
end:

RP:=proc(x,d,K) local ra, i:
	ra:=rand(1..K)():
	add(x^ra(), i=0..d);
end:

RC:=proc(x,d,K,n) local i:
	[seq(RP(x,d,K), i=1..n)]:
end:

EvalC:=proc(L,x,x0)
	description "inputs list L of expressions in variable x and number x0, outputs L[n](L[n-1](L(n)))";
	local a, i;
	a:=x0:
	for i from 1 to nops(L) do
		a:=subs(x=a, L[i]) mod K:
	od:
a:
end:


















## BEGIN MRHSTDLIB (helper functions)
insertLines:=proc(n::integer) 
	description "Appends {n} lines.",
	"See also: nl, pskip":
	local i:

	for i from 1 to n do:
		printf("\n");
	od:
end:

nl:=proc(): insertLines(1): end:
pskip:=proc(): insertLines(2): end:

PrintHelp:=proc(LofPs::list(procedure)) 
	description "Prints descriptions for the procedures in {LofPs}."
	:
	local P, i, NProcs:

	NProcs:=nops(LofPs):

	for i from 1 to NProcs do
		P:=LofPs[i]:
		printf("### %s ###", P);
		nl();
		Describe(P);
		pskip();
	od:
end:
## END MRHSTDLIB