OKlibrary  0.2.1.6
CalkinWilf.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 3.9.2012 (Swansea) */
00002 /* Copyright 2012 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00023 oklib_include("OKlib/ComputerAlgebra/DataStructures/Lisp/Lists.mac")$
00024 oklib_include("OKlib/ComputerAlgebra/NumberTheory/Lisp/Auxiliary.mac")$
00025 
00026 
00027 /* **********
00028    * Basics *
00029    **********
00030 */
00031 
00032 /* For a positive rational number r, its left and right successor (as a pair):
00033 */
00034 calkinwilf_expand(r) := [r/(r+1), 1+r]$
00035 /* Alternatively:
00036 block([p,q], [p,q] : [num(r), denom(r)], [p/(p+q),(p+q)/q])
00037 Note also that r/(r+1) = hmean([r,1])/2.
00038 */
00039 
00040 /* In the other direction, the parent of a positive rational number r # 1
00041    in the tree:
00042 */
00043 calkinwilf_reduce(r) := if r>1 then r-1 else r/(1-r)$
00044 /* Alternatively:
00045 block([p,q], [p,q] : [num(r), denom(r)], if r>1 then (p-q)/q else p/(q-p)
00046 */
00047 
00048 /* The Calkin-Wilf tree of height k, with root r, a positive rational number,
00049    as perfect labelled root tree: */
00050 calkinwilfg_lrt(k,r) := if k=0 then [r] else block([e : calkinwilf_expand(r)],
00051  [r, calkinwilfg_lrt(k-1, first(e)), calkinwilfg_lrt(k-1, second(e))])$
00052 /* The full Calkin-Wilf tree of height k: */
00053 calkinwilf_lrt(k) := calkinwilfg_lrt(k,1)$
00054 
00055 /* The path from the root to r in the Calkin-Wilf tree, as a list of 1's and
00056    2's (the node representation of the node of r according to
00057    ComputerAlgebra/Trees/Lisp/Basics.mac):
00058 */
00059 calkinwilf_path(r) := if r=1 then [] else
00060  if r<1 then endcons(1, calkinwilf_path(r/(1-r)))
00061  else endcons(2, calkinwilf_path(r-1))$
00062 
00063 /* Remark:
00064    That calkinwilf_path is a bijection from the positive rational numbers
00065    to the set of words over {1,2}, and thus the Calkin-Wilf tree enumerates
00066    the positive rational numbers, is easily seen:
00067     - calkinwilf_path(r) is well-defined, since the sum of numerator and
00068       denominator decreases via calkinwilf_reduce(r).
00069     - The map is a bijection since calkinwilf_reduce(r) is the inverse,
00070       for both children, of calkinwilf_expand(r).
00071 */
00072 
00073 
00074 /* The levels of the Calkin-Wilf tree: */
00075 calkinwilf_levels(k) := if k=0 then [1] else
00076  lappend(map(lambda([r],calkinwilf_expand(r)), calkinwilf_levels(k-1)))$
00077 
00078 /* The n-th element (n >= 0) of the Calkin-Wilf enumeration of the positive
00079    rational numbers (enumerating the levels):
00080 */
00081 calkinwilf_recursion(n) := block([res : 1],
00082  while n>0 do (res : 1/(1+floor(res) - fractional_part(res)), n:n-1),
00083  res)$
00084