/usr/share/doc/axiom-doc/hypertex/numfunctions.xhtml

<?xml version="1.0" encoding="UTF-8"?>
<html xmlns="http://www.w3.org/1999/xhtml" 
      xmlns:xlink="http://www.w3.org/1999/xlink"
      xmlns:m="http://www.w3.org/1998/Math/MathML">
 <head>
  <meta http-equiv="Content-Type" content="text/html" charset="us-ascii"/>
  <title>Axiom Documentation</title>
  <style>

   html {
     background-color: #ECEA81;
   }

   body { 
     margin: 0px;
     padding: 0px;
   }

   div.command { 
     color:red;
   }

   div.center {
     color:blue;
   }

   div.reset {
     visibility:hidden;
   }

   div.mathml { 
     color:blue;
   }

   input.subbut {
     background-color:#ECEA81;
     border: 0;
     color:green;
     font-family: "Courier New", Courier, monospace;
   }

   input.noresult {
     background-color:#ECEA81;
     border: 0;
     color:black;
     font-family: "Courier New", Courier, monospace;
   }

   span.cmd { 
     color:green;
     font-family: "Courier New", Courier, monospace;
   }

   pre {
     font-family: "Courier New", Courier, monospace;
   }
  </style>
  <script type="text/javascript">
<![CDATA[
     // This is a hash table of the values we've evaluated.
     // This is indexed by a string argument. 
     // A value of 0 means we need to evaluate the expression
     // A value of 1 means we have evaluated the expression
   Evaled = new Array();
     // this says we should modify the page
   hiding = 'show';
     // and this is the id of the div tag to modify (defaulted)
   thediv = 'mathAns';
     // commandline will mark that its arg has been evaled so we don't repeat
   function commandline(arg) {
     Evaled[arg] = 0;  // remember that we have set this value
     thediv='ans'+arg; // mark where we should put the output
     var ans = document.getElementById(arg).value;
     return(ans);
   }
   // the function only modifies the page if when we're showing the
   // final result, otherwise it does nothing.
   function showanswer(mathString,indiv) {
     if (hiding == 'show') { // only do something useful if we're showing
       indiv = thediv;  // override the argument so we can change it
       var mystr = mathString.split("</div>");
       for (var i=0; i < mystr.length; i++) {
         if (mystr[i].indexOf("mathml") > 0) {
           var mymathstr = mystr[i].concat("</div>");
         }
       }
       // this turns the string into a dom fragment
       var mathRange = document.createRange();
       var mathBox=
               document.createElementNS('http://www.w3.org/1999/xhtml','div');
       mathRange.selectNodeContents(mathBox);
       var mymath = mathRange.createContextualFragment(mymathstr);
       mathBox.appendChild(mymath);
       // now we need to format it properly
       // and we stick the result into the requested div block as a child.
       var mathAns = document.getElementById(indiv);
       mathAns.removeChild(mathAns.firstChild);
       mathAns.appendChild(mathBox);
     }
   }
   // this function takes a list of expressions ids to evaluate
   // the list contains a list of "free" expression ids that need to
   // be evaluated before the last expression. 
   // For each expression id, if it has not yet been evaluated we
   // evaluate it "hidden" otherwise we can skip the expression.
   // Once we have evaluated all of the free expressions we can
   // evaluate the final expression and modify the page.
   function handleFree(arg) {
     var placename = arg.pop();      // last array val is real
     var mycnt = arg.length;         // remaining free vars
       // we handle all of the prerequired expressions quietly
     hiding = 'hide';
     for (var i=0; i<mycnt; i++) {   // for each of the free variables
       if (Evaled[arg[i]] == null) { // if we haven't evaled it
         Evaled[arg[i]] = 0;         // remember we evaled it
         makeRequest(arg[i]);        // initialize the free values
       }
     }
       // and now we start talking to the page again
     hiding = 'show';                // we want to show this
     thediv = 'ans'+placename;       // at this div id
     makeRequest(placename);         // and we eval and show it
   }
]]>
<![CDATA[
  function ignoreResponse() {}
  function resetvars() {
    http_request = new XMLHttpRequest();         
    http_request.open('POST', '127.0.0.1:8085', true);
    http_request.onreadystatechange = ignoreResponse;
    http_request.setRequestHeader('Content-Type', 'text/plain');
    http_request.send("command=)clear all");
    return(false);
  }
]]>
 function init() {
 }
 function makeRequest(arg) {
   http_request = new XMLHttpRequest();         
   var command = commandline(arg);
   //alert(command);
   http_request.open('POST', '127.0.0.1:8085', true);
   http_request.onreadystatechange = handleResponse;
   http_request.setRequestHeader('Content-Type', 'text/plain');
   http_request.send("command="+command);
   return(false);
 }
 function lispcall(arg) {
   http_request = new XMLHttpRequest();         
   var command = commandline(arg);
   //alert(command);
   http_request.open('POST', '127.0.0.1:8085', true);
   http_request.onreadystatechange = handleResponse;
   http_request.setRequestHeader('Content-Type', 'text/plain');
   http_request.send("lispcall="+command);
   return(false);
 }
 function showcall(arg) {
   http_request = new XMLHttpRequest();         
   var command = commandline(arg);
   //alert(command);
   http_request.open('POST', '127.0.0.1:8085', true);
   http_request.onreadystatechange = handleResponse;
   http_request.setRequestHeader('Content-Type', 'text/plain');
   http_request.send("showcall="+command);
   return(false);
 }
 function interpcall(arg) {
   http_request = new XMLHttpRequest();         
   var command = commandline(arg);
   //alert(command);
   http_request.open('POST', '127.0.0.1:8085', true);
   http_request.onreadystatechange = handleResponse;
   http_request.setRequestHeader('Content-Type', 'text/plain');
   http_request.send("interpcall="+command);
   return(false);
 }
 function handleResponse() {
  if (http_request.readyState == 4) {
   if (http_request.status == 200) {
    showanswer(http_request.responseText,'mathAns');
   } else
   {
     alert('There was a problem with the request.'+ http_request.statusText);
   }
  }
 }

  </script>
 </head>
 <body>
  <div align="center"><img align="middle" src="doctitle.png"/></div>
  <hr/>
  <div align="center">Integer Number Theory Functions</div>
  <hr/>
The <a href="db.xhtml?IntegerNumberTheoryFunctions">
IntegerNumberTheoryFunctions</a> package contains a variety of
operations of interest to number theorists. Many of these operations
deal with divisibility properties of integers (Recall that an integer
a divides an integer b if there is an integer c such that b=a*c.)

The operation <a href="dbopdivisors.xhtml">divisors</a> returns a list
of the divisors of an integer
<ul>
 <li>
  <input type="submit" id="p1" class="subbut" 
    onclick="makeRequest('p1');"
    value="div144:=divisors(144)" />
  <div id="ansp1"><div></div></div>
 </li>
</ul>
You can now compute the number of divisors of 144 and the sum of the
divisors of 144 by counting and summing the elements of the list we
just created.
<ul>
 <li>
  <input type="submit" id="p2" class="subbut" 
    onclick="handleFree(['p1','p2']);"
    value="#(div144)" />
  <div id="ansp2"><div></div></div>
 </li>
 <li>
  <input type="submit" id="p3" class="subbut" 
    onclick="handleFree(['p1','p3']);"
    value="reduce(+,div144)" />
  <div id="ansp3"><div></div></div>
 </li>
</ul>
Of course, you can compute the number of divisors of an integer n, 
usually denoted d(n), and the sum of the divisors of an integer n,
usually denoted &#x003C2;(n), without ever listing the divisors of n.

In Axiom, you can simply call the operations
<ul>
 <li>
  <input type="submit" id="p4" class="subbut" 
    onclick="makeRequest('p4');"
    value="numberOfDivisors(144)" />
  <div id="ansp4"><div></div></div>
 </li>
 <li>
  <input type="submit" id="p5" class="subbut" 
    onclick="makeRequest('p5');"
    value="sumOfDivisors(144)" />
  <div id="ansp5"><div></div></div>
 </li>
</ul>
The key is that d(n) and &#x003C2;(n) are "multiplicative functions". 
This means that when n and m are relatively prime, that is, when n and
m have no factors in common, then d(nm)=d(n)d(m) and &#x003C2;(nm)=
&#x003C2;(n)&#x003C2;(m). Note that these functions are trivial to 
compute when n is a prime power and are computed for general n from
the prime factorization of n. Other examples of multiplicative functions
are &#x003C2;_k(n), the sum of the k-th powers of the divisors of n and
&#x003C6;(n), the number of integers between 1 and n which are prime to n.
The corresponding Axiom operations are called
<a href="dbopsumofkthpowerdivisors.xhtml">sumOfKthPowerDivisors</a> and
<a href="dbopeulerphi.xhtml">eulerPhi</a>.
<ul>
 <li>
  <input type="submit" id="p6" class="subbut" 
    onclick="makeRequest('p6');"
    value="sumOfKthPowerDivisors(144,2)" />
  <div id="ansp6"><div></div></div>
 </li>
 <li>
  <input type="submit" id="p7" class="subbut" 
    onclick="makeRequest('p7');"
    value="eulerPhi(144)" />
  <div id="ansp7"><div></div></div>
 </li>
</ul>

An interesting function is called &#x003BC;(n), the Moebius mu function,
defined as 
<pre>
        0 if n has a repeated prime factor 
          (i.e. is divisible by a square)
  &#x003BC;(n)= 1 if n is 1
       (-1)^k if n is the product of k distinct primes
</pre>
The corresponding Axiom operation is 
<ul>
 <li>
  <input type="submit" id="p8" class="subbut" 
    onclick="makeRequest('p8');"
    value="moebiusMu(2*2*2)" />
  <div id="ansp8"><div></div></div>
 </li>
 <li>
  <input type="submit" id="p9" class="subbut" 
    onclick="makeRequest('p9');"
    value="moebiusMu(1)" />
  <div id="ansp9"><div></div></div>
 </li>
 <li>
  <input type="submit" id="p10" class="subbut" 
    onclick="makeRequest('p10');"
    value="moebiusMu(5*7*13)" />
  <div id="ansp10"><div></div></div>
 </li>
</ul>
This function occurs in the following theorem:
<br/>
<b>Theorem</b>(Moebius Inversion Formula):<br/>
Let f(n) be a function on the positive integers and let F(n) be defined
by F(n)=sum of f(n) over d | n where the sum is taken over the positive
divisors of n. Then the values of f(n) can be recovered from the values
of F(n):f(n) = sum of &#x003BC;F(n/d) over d|n, where the sum is taken
over the positive divisors of n.

When f(n)=1, the F(n)=d(n). Thus, if you sum &#x003BC;(d)*d(n/d) over 
the positive divisors of d of n, you should always get 1.
<ul>
 <li>
  <input type="submit" id="p11" class="noresult" 
    onclick="makeRequest('p11');"
    value="f1(n)==reduce(+,[moebiusMu(d)*numberOfDivisors(quo(n,d)) for d in divisors(n)])" />
  <div id="ansp11"><div></div></div>
 </li>
 <li>
  <input type="submit" id="p12" class="subbut" 
    onclick="handleFree(['p11','p12']);"
    value="f1(200)" />
  <div id="ansp12"><div></div></div>
 </li>
 <li>
  <input type="submit" id="p13" class="subbut" 
    onclick="handleFree(['p11','p13']);"
    value="f1(846)" />
  <div id="ansp13"><div></div></div>
 </li>
</ul>
Similarly, when f(n)=n, then F(n)=&#x003C2;(n). Thus, if you sum 
&#x003BC;(d)*&#x003C2;(n/d) over the positive divisors d of n, you
should always get n.
<ul>
 <li>
  <input type="submit" id="p14" class="noresult" 
    onclick="makeRequest('p14');"
    value="f2(n)==reduce(+,[moebiusMu(d)*sumOfDivisors(quo(n,d)) for d in divisors(n)])" />
  <div id="ansp14"><div></div></div>
 </li>
 <li>
  <input type="submit" id="p15" class="subbut" 
    onclick="handleFree(['p14','p15']);"
    value="f2(200)" />
  <div id="ansp15"><div></div></div>
 </li>
 <li>
  <input type="submit" id="p16" class="subbut" 
    onclick="handleFree(['p14','p16']);"
    value="f2(846)" />
  <div id="ansp16"><div></div></div>
 </li>
</ul>
The Fibonacci numbers are defined by
<pre>
  F(1)=1
  F(2)=1
  F(n)=F(n-1)+F(n-2) for n=3,4,...
</pre>
The operation <a href="dbopfibonacci.xhtml">fibonacci</a> computes the
nth Fibonacci number.
<ul>
 <li>
  <input type="submit" id="p17" class="subbut" 
    onclick="makeRequest('p17');"
    value="fibonacci(25)" />
  <div id="ansp17"><div></div></div>
 </li>
 <li>
  <input type="submit" id="p18" class="subbut" 
    onclick="makeRequest('p18');"
    value="[fibonacci(n) for n in 1..15]" />
  <div id="ansp18"><div></div></div>
 </li>
</ul>
Fibonacci numbers can also be expressed as sums of binomial
coefficients.
<ul>
 <li>
  <input type="submit" id="p19" class="noresult" 
    onclick="makeRequest('p19');"
    value="fib(n)==reduce(+,[binomial(n-1-k,k) for k in 0..quo(n-1,2)])" />
  <div id="ansp19"><div></div></div>
 </li>
 <li>
  <input type="submit" id="p20" class="subbut" 
    onclick="handleFree(['p19','p20']);"
    value="fib(25)" />
  <div id="ansp20"><div></div></div>
 </li>
 <li>
  <input type="submit" id="p21" class="subbut" 
    onclick="handleFree(['p19','p21']);"
    value="[fib(n) for n in 1..15]" />
  <div id="ansp21"><div></div></div>
 </li>
</ul>

Quadratic symbols can be computed with the operations
<a href="dboplegendre.xhtml">legendre</a> and
<a href="dbopjacobi.xhtml">jacobi</a>. The Legendre symbol (a/p) is
defined for integers a and p with p an odd prime number. By definition,
<pre>
        = -1 when a is not a square (mod p)
  (a/p) =  0 when a is divisible by p
        = +1 when a is a square (mod p)
</pre>
You compute (a/p) via the command legendre(a,p)
<ul>
 <li>
  <input type="submit" id="p22" class="subbut" 
    onclick="makeRequest('p22');"
    value="legendre(3,5)" />
  <div id="ansp22"><div></div></div>
 </li>
 <li>
  <input type="submit" id="p23" class="subbut" 
    onclick="makeRequest('p23');"
    value="legendre(23,691)" />
  <div id="ansp23"><div></div></div>
 </li>
</ul>

The Jacobi symbol (a/n) is the usual extension of the Legendre symbol,
where n is an arbitrary integer. The most important property of the
Jacobi symbol is the following: if K is a quadratic field with 
discriminant d and quadratic character &#x003C7;, the &#x003C7;(n)=(d/n).
Thus, you can use the Jacobi symbol to compute, say, the class numbers
of imaginary quadratic fields from a standard class number formula. This
function computes the class number of the imaginary quadratic field with
discriminant d.
<ul>
 <li>
  <input type="submit" id="p24" class="noresult" 
    onclick="makeRequest('p24');"
    value="h(d)==quo(reduce(+,[jacobi(d,k) for k in 1..quo(-d,2)]),2-jacobi(d,2))" />
  <div id="ansp24"><div></div></div>
 </li>
 <li>
  <input type="submit" id="p25" class="subbut" 
    onclick="handleFree(['p24','p25']);"
    value="h(-163)" />
  <div id="ansp25"><div></div></div>
 </li>
 <li>
  <input type="submit" id="p26" class="subbut" 
    onclick="handleFree(['p24','p26']);"
    value="h(-499)" />
  <div id="ansp26"><div></div></div>
 </li>
 <li>
  <input type="submit" id="p27" class="subbut" 
    onclick="handleFree(['p24','p27']);"
    value="h(-1832)" />
  <div id="ansp27"><div></div></div>
 </li>
</ul>

 </body>
</html>
axiom-hypertex-data 20120501-8 / usr / share / doc / axiom-doc / hypertex / numfunctions.xhtml
