# OK to post homework
# Salman Manzoor, 4/13/25, Assignment 21

with(ListTools):


CFx:=proc(x,k) local lis,curr,item,i:
Digits:=max(Digits,100):
lis:=[]:
curr:=x:
for i from 1 to k do
    item:=floor(curr):
    lis:=[op(lis),item]:
	if (curr=item) then break: fi:
    curr:=1/(curr-item):
od:
lis:
end:

ExtractListPortion:=proc(a,b,L) local tLis,i,k:
k:=min(b,nops(L)):
tLis:=[]:
for i from a to k do
    tLis:=[op(tLis),L[i]]:
od:
tLis:
end:

GuessPCF:=proc(x) local searchSpace,searchCF,initGuess,periodicGuess,i,j,guessArray:
if(type(x,rational)) then RETURN(FAIL): end:
searchSpace:=20:
searchCF:=CFx(x,searchSpace):
for i from 1 to searchSpace do
    initGuess:=ExtractListPortion(1,i,searchCF):
    for j from 0 to searchSpace do
	periodicGuess:=ExtractListPortion(i+1,i+1+j,searchCF);
	guessArray:=[op(initGuess),op(periodicGuess)]:
	while(nops(guessArray) < searchSpace) do
            guessArray:=[op(guessArray) , op(periodicGuess)]:
        od:
        if(comparray(ExtractListPortion(1,searchSpace,guessArray) , searchCF, dontprint )) then 
            RETURN([initGuess, periodicGuess]):
        fi:
    od:
od:
RETURN(FAIL):
end:

tempDriver:=proc() local i,lis:
lis:=[]:
for i from 0 to 100 do
	if not (type(sqrt(i),rational)) then lis:=[op(lis),nops(GuessPCF(sqrt(i))[2])]: end:
od:
lis:
end:

#tempDriver gives the sequence A013943 in the OEIS
#sqrt(94) has the longest periodic portion at length 16

findBestRationalApprox:=proc(x,maxSens) local CF,currSize:
currSize:=1:
CF:=CFx(x,currSize):
while(denom(EvalCF(CF)) < maxSens) do currSize+=1: CF:=CFx(x,currSize): od:
EvalCF(CFx(x,currSize-1)):
end:

#the inputs (Pi,10^7) and (exp(1),10^7) give
#5419351/1725033 and 14665106/5394991 respectively



#from C21, added option remember

#EvalCF(L): inputs a list of pos. integers and outputs the fraction whose cont. fraction it is
#(reverse of CF(f))
EvalCF:=proc(L) option remember:
if nops(L)=1 then
 L[1]:
else
L[1]+1/EvalCF([op(2..nops(L),L)]):
fi:
end: