#OK to post homework
#Victoria Chayes, 4/21/19, Assignment 23

Help:=proc(): print(`Fc(n,K),Tc(n,K),Tabitdumber(n,K)`): end:
with(LinearAlgebra):

#1. Maple can easily compute the millionth-Fibonacci number mod 2003, say using the program F(n,K) we did in class, by typing F(10^6,2003); But F(n,K) is not as clever as I claimed. It can't find the 10^20-th Fibonacci number mod 2003. Write a program that finds F(n,K) for very large n.

Fc:=proc(n,K) local A, b:
A:=Matrix([[0,1],[1,1]]):
b:=Matrix(2,1,[0,1]):
LinearAlgebra[Modular][Mod](K,Multiply(LinearAlgebra[Modular][MatrixPower](K,A,n),b),integer)[1][1]:
end:

#I tested Fc against smaller numbers, and it agreed with the F(n,K) we wrote in class.

#Fc(10^20,2003);
#    999
#time(Fc(10^20,2003));
#    0.6e-2

#2 Write a program Tc(n,K) that finds the n-th Tribonacci number mod K. What is Tc(10^100,2003);?

Tc:=proc(n,K) local A, b:
A:=Matrix([[0,1,0],[0,0,1],[1,1,1]]):
b:=Matrix(3,1,[0,0,1]):
LinearAlgebra[Modular][Mod](K,Multiply(LinearAlgebra[Modular][MatrixPower](K,A,n),b),integer)[1][1]:
end:

#I wrote the following version for testing against smaller numbers, and Tc agreed with it:

Tabitdumber:=proc(n,K) local a,b,c,d,i:
a:=0:
b:=0:
c:=1:

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

#Tc(10^100, 2003);
#    7
#time(Tc(10^100, 2003));
#    0.17e-1