#OK to post homework
#Joseph Koutsoutis, 04-13-2025, Assignment 21

read `C21.txt`:


#1

CFx := proc(x, k) local a:
  if k = 0 then:
    return []:
  elif x - trunc(x) = 0 then:
    return [x]:
  else:
    a := trunc(x):
    return [a, op(CFx(1 / (x - a), k-1))]:
  fi:
end:


#2

#This function guesses [L1, L2] by computing CFx(x, k) and then finding a
#valid value of L2 that repeats the maximum number of times.
GuessPCF := proc(x, k) local L, i, j, l, rec, cha, cha_i, valid, curr:
  if x = trunc(x) then:
    return [trunc(x), []]:
  fi:
  L := CFx(x, k):
  rec := 1:
  cha_i := k+1:
  cha := []:
  for i from 1 to k do:
    for j from i to k do:
      curr := L[i..j]:
      valid := true:
      for l from 1 to k-j do:
        if L[l + j] <> curr[(l-1) mod (j-i+1) + 1] then:
          valid := false:
        fi:
      od:
      if valid and floor((k - i + 1) / (j - i + 1)) > rec then:
        cha_i := i:
        cha := curr:
        rec := floor((k - i + 1) / (j - i + 1)):
      fi:
    od:
  od:
  [L[1..cha_i-1], cha]:
end:


#3

#seq(nops(GuessPCF(sqrt(n), 50)[2]), n=2..100) outputs

#1, 2, 0, 1, 2, 4, 2, 0, 1, 2, 2, 5, 4, 2, 0, 1, 2, 6, 2, 6, 6, 4, 2, 0, 1, 2, 4, 5, 2, 8, 4, 4, 4, 2, 0, 1, 2, 2, 2, 3, 2, 10, 8, 6, 12, 4, 2, 0, 1, 2, 6, 5, 6, 4, 2, 6, 7, 6, 4, 11, 4, 2, 0, 1, 2, 10, 2, 8, 6, 8, 2, 7, 5, 4, 12, 6, 4, 4, 2, 0, 1, 2, 2, 5, 10, 2, 6, 5, 2, 8, 8, 10, 16, 4, 4, 11, 4, 2, 0

#which matches the first entries of https://oeis.org/A003285

#The largest period is 16


#4

FindRationalApproximation := proc(x, d) local L, curr, prev, k:
  prev := 0:
  k := 1:
  L := CFx(x, k):
  curr := EvalCF(L, k):
  while denom(curr) <= d do:
    prev := curr:
    k++:
    L := CFx(x, k):
    curr := EvalCF(L, k):
  od:
  prev:
end:

#Maple outputs:

#FindRationalApproximation(Pi, 10000000) = 5419351/1725033
#FindRationalApproximation(exp(1), 10000000) = 14665106/5394991