/usr/share/doc/axiom-doc/hypertex/numproblems.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">Problems</div>
  <hr/>
One can show that if an integer of the form 2**k-1 is prime then
k must be prime. 
<br/>
<b>Proof</b>
Suppose that k=m*n is a non-trivial factorization. Then
<pre>
       2^m = 1 (mod (2^m-1))
   2^(m*n) = 1 (mod (2^m-1))
  so 2^m-1 is a non-trivial factor of 2^k-1
</pre>

<b>Problem</b> Find the smallest prime p such that 2**p-1 is not prime
<br/>
<b>Answer</b>
<br/>
First, define a function:
<ul>
 <li>
  <input type="submit" id="p1" class="noresult" 
    onclick="makeRequest('p1');"
    value="f(n:NNI):INT == 2^n-1" />
  <div id="ansp1"><div></div></div>
 </li>
</ul>
You can try factoring f(p) as p ranges through the set of primes.
For example,
<ul>
 <li>
  <input type="submit" id="p2" class="subbut" 
    onclick="handleFree(['p1','p2']);"
    value="factor f(7)" />
  <div id="ansp2"><div></div></div>
 </li>
</ul>
This gets tedious after a while, so let's use Axiom's stream facility.
A streamm is essentially an infinite sequence. First, we create a stream
consisting of the positive integers:
<ul>
 <li>
  <input type="submit" id="p3" class="subbut" 
    onclick="makeRequest('p3');"
    value="ints:=[n for n in 1..]" />
  <div id="ansp3"><div></div></div>
 </li>
</ul>
Now, we create a stream consisting of the primes:
<ul>
 <li>
  <input type="submit" id="p4" class="subbut" 
    onclick="handleFree(['p2','p4']);"
    value="primes:=[x for x in ints | prime? x]" />
  <div id="ansp4"><div></div></div>
 </li>
</ul>
Here is the 25th prime:
<ul>
 <li>
  <input type="submit" id="p5" class="subbut" 
    onclick="handleFree(['p2','p5']);"
    value="primes.25" />
  <div id="ansp5"><div></div></div>
 </li>
</ul>
Next, create the stream of numbers of the form 2**p-1 with p prime:
<ul>
 <li>
  <input type="submit" id="p6" class="subbut" 
    onclick="handleFree(['p1','p2','p3','p4','p6']);"
    value="numbers:=[f(n) for n in primes]" />
  <div id="ansp6"><div></div></div>
 </li>
</ul>
Finally, form the stream of factorizations of the elements of numbers:
<ul>
 <li>
  <input type="submit" id="p7" class="subbut" 
    onclick="handleFree(['p1','p2','p3','p4','p6','p7']);"
    value="factors:=[factor n for n in numbers]" />
  <div id="ansp7"><div></div></div>
 </li>
</ul>
You can see that the fifth number in the stream (2047=23*89) is the first
one that has a non-trivial factorization. Since 2**11=2048, the solution
to the problem is 11.

Here is another way to see that 2047 is the first number in the stream
that is composite:
<ul>
 <li>
  <input type="submit" id="p8" class="subbut" 
    onclick="handleFree(['p3','p4','p6','p8']);"
    value="nums:=[x for x in numbers | not prime? x]" />
  <div id="ansp8"><div></div></div>
 </li>
</ul>
<br/><br/>
<b>Problem</b>: Find the smallest positive integer n such that 
n**2-n+41 is not prime.
<br/>
<b>Answer</b>: When n=41, n**2-n+41=41**2, which certainly isn't prime.
Is there any smaller integer that works? Here are the first 40 values:
<ul>
 <li>
  <input type="submit" id="p9" class="subbut" 
    onclick="makeRequest('p9');"
    value="numbs:=[n**2-n+41 for n in 0..40]" />
  <div id="ansp9"><div></div></div>
 </li>
</ul>
Now have Axiom factor the numbers on this list:
<ul>
 <li>
  <input type="submit" id="p10" class="subbut" 
    onclick="handleFree(['p9','p10']);"
    value="[factor n for n in numbs]" />
  <div id="ansp10"><div></div></div>
 </li>
</ul>
You can see that 41 is the smallest positive integer n such that
n**2-n+41 is not prime.
 </body>
</html>
axiom-hypertex-data 20120501-8 / usr / share / doc / axiom-doc / hypertex / numproblems.xhtml
