<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN"
"http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
<meta http-equiv="Content-Script-Type" content="text/javascript">
<meta name="description" content="sum of squares script">
<meta name="keywords" lang="en" content="sum,squares">
<title>Sum of two squares - script</title>
<script>
<!--
rmin=""; // valeurs par defaut
rvmin=0;
disp=0; // flag affiche les facteurs complexes
msg=""; // resultat
ex=new Array(); // exposants
uv=new Array(); // facteurs complexes
er=new Array(); // exposants courants pour back-track
me=new Array(); // exposant max pour filtrage
nui=0; // nbre de facteurs complexes d'exposant impair
dp=1; // produit des (exposants+1) des facteurs 4k+1
dq=1; // produit des parites des exposants des facteurs 4k+3
K=[1,0]; // facteur constant complexe
first=1; // flag premier facteur
AB=[0,0]; // valeur actuelle
torun=1; // flag affiche la liste des decompositions
debug=0; // affiche les info de backtrack
s=""+location.href; // convertit location en string
i=s.indexOf("rmi="); // extrait les parametres d'appel
if (i>=0) {
j=(s.substr(i+4)).indexOf("&"); // separateur parametres
if (j<0) j=s.length-i-4; // fin de chaine
rmin=unescape(s.substr(i+4,j));
}
i=s.indexOf("rdi");
if (i>=0) {
disp=1;
}
// calcule la valeur maxi d'un int
rmax=1;
while ((rmax+rmax+1)%2==1) rmax=rmax+rmax+1;
// bouton OK
function reRun() {
rmin=document.f1.rmi.value;
disp=document.f1.rdi.checked;
re=/[^*+%\/()0-9-]/;
if (re.test(rmin)) {
alert("Illegal character '"+RegExp.lastMatch+"'");
return;
}
window.onerror=myerr; // catch syntax errors
rvmin=Math.floor(1*eval(rmin)); // evalue expression
if (!(rvmin>0) || rvmin>rmax) { // rvmin NaN or <=0 or > max
alert("Illegal value : 1 to "+rmax+" please");
return;
}
doit(); // ok
} // reRun()
function myerr(emsg, url, lno) {
alert(emsg);
}
function doit() {
msg="";
msg+="Decomposition of "+rvmin;
// reinit et efface tableaux
ex.length=0; // exposants
uv.length=0; // facteurs complexes
er.length=0; // exposants courants pour back-track
me.length=0; // exposant max pour filtrage
nui=0; // nbre de facteurs complexes d'exposant impair
dp=1; // produit des (exposants+1) des facteurs 4k+1
dq=1; // produit des parites des exposants des facteurs 4k+3
K=[1,0]; // facteur constant complexe
first=1; // flag premier facteur
AB=[0,0]; // valeur actuelle
premier(rvmin); // decompose en nombres premiers
editdp(); // edite le nombre de decompositions
scan(); // edite les solutions
if (document.getElementById)
document.getElementById("res").innerHTML=msg;
else
res.innerHTML=msg;
} // doit()
// affiche un facteur complexe
function xdisp(a) {
if (a[1]==0) { // nombre réel
if (a[0]!=1) msg+=a[0];
}
else if (a[0]==0) { // nombre imaginaire
if (a[1]==1) msg+="i";
else if (a[1]==-1) msg+="-i";
else msg+=a[1]+"i";
}
else {
msg+="("+a[0];
if (a[1]==1) msg+="+i";
else if (a[1]==-1) msg+="-i";
else if (a[1]>0) msg+="+"+a[1]+"i";
else msg+=a[1]+"i";
msg+=")";
}
}
// décomposition en facteurs premiers
// méthode brutale
function premier(n) {
var d=2,dd=1,q=n,r=Math.sqrt(q);
var e;
while (d>1 && d<=r) {
if (q%d==0) { // un facteur premier trouvé
e=0;
while (q%d==0) { q=q/d; e++; }
addit(d,e);
r=Math.sqrt(q);
}
d+=dd; dd=2;
} // autre facteur ?
if (q!=1) { // dernier facteur premier
addit(q,1,first);
}
}
// decomposition en somme de 2 carres d'un nombre premier 4k+1
// par l'algorithme de Lagrange
function primdec(n) {
var a=1, b=0, c=-n, r=Math.floor(Math.sqrt(n));
var aa,bb,cc,m;
while (a+c!=0) {
m=Math.floor((Math.abs(b)+r)/Math.abs(a));
aa=a*m*m+2*b*m+c; bb=a*m+b; cc=a;
a=aa; b=bb; c=cc;
}
return [Math.abs(a),Math.abs(b)];
}
// traite un facteur premier
function addit(n,e,f) {
var i;
// affiche la decomposition en nombres premiers
if (f) msg+=" prime";
else {
if (!first) msg+="×";
else msg+="=";
if (n!=1) msg+=n;
if (e>1) msg+="<sup>"+e+"</sup>";
}
first=0;
// calcule dp dq K [u,v]
if (dq==0 || torun==0 || n==1) return; // rien a faire
if (n==2) { // multiplie par 1+i puissance e
for (i=0; i<e; i++) {
K[0]=K[0]-K[1];
K[1]=K[0]+2*K[1];
}
return;
}
if (n%4==3) {
if (e%2!=0) { dq=0; return; }
for (i=0; i<e/2; i++) {
K[0]*=n;
K[1]*=n;
}
return;
}
// n%4==1
dp*=(e+1);
// trie les exposants impairs d'abord.
if (e%2!=0) {
if (nui<uv.length) { // insert
i=uv.length;
uv[i]=[uv[nui][0],uv[nui][1]];
ex[i]=ex[nui];
uv[nui]=primdec(n);
ex[nui]=e;
nui++;
}
else { // add to uv[nui]
uv[uv.length]=primdec(n);
ex[ex.length]=e;
nui++;
}
}
else { // add
uv[uv.length]=primdec(n);
ex[ex.length]=e;
}
}
// edite le nombre de decompositions
function editdp() {
var i;
dp=Math.floor((dp*dq+1)/2);
if (dp==0) {
msg+="<br>No decomposition as sum of two squares";
i=rmin;
while (i%4==0) i/=4;
if (i%8==7) msg+=" nor three squares.";
else {
msg+=".<br>At least one decomposition as sum of three squares but ";
msg+="this programm is not suitable for finding them.";
}
msg+="<br>Use the brute force <a href='exesumsq4.html'>script</a>";
}
if (dp==1) msg+="<br>Only one decomposition as sum of two squares :<br>";
if (dp>1) msg+="<br>"+dp+" decompositions as sum of two squares :<br>";
}
// balaye toutes les combinaisons
function scan() {
var i,j,nn;
if (dp==0 || !torun) return;
// balayage
i=0; nn=0;
while (i>=0) {
while (i<uv.length) {
er[i]=0;
if (i==0) me[i]=Math.floor(ex[i]/2);
// limite aux decompositions :
// cas particulier tous exposnants pairs, seulement la moitié si tous les précédents sont à 1/2
else if (nui==0 && er[i-1]==me[i-1] && me[i-1]==ex[i-1]/2) me[i]=ex[i]/2;
else me[i]=ex[i];
i++;
}
nn++;
editone(nn);
i--;
// backtrack
while(i>=0 && er[i]>=me[i]) i--;
if (i>=0) {
er[i]++;
i++; }
}
if (nn!=dp) msg+="<br>internal error : only "+nn+" decomposition given !";
}
// affiche une position
function editone(nb) {
var AB=[K[0],K[1]];
var i,j;
msg+="<br>";
if (disp) msg+=nb+" : "; // numerotage.
// affiche les facteurs K et uv[]
if (disp) xdisp(K);
for (i=0;i<uv.length; i++) {
if (ex[i]-er[i]>0 && disp) xdisp(uv[i]);
if (ex[i]-er[i]>1 && disp) msg+="<sup>"+(ex[i]-er[i])+"</sup>";
if (er[i]>0 && disp) xdisp([uv[i][0],-uv[i][1]]);
if (er[i]>1 && disp) msg+="<sup>"+er[i]+"</sup>";
for (j=0; j<ex[i]; j++) {
if (j<er[i]) { // facteur u-iv
re=AB[0]*uv[i][0]+AB[1]*uv[i][1];
im=AB[1]*uv[i][0]-AB[0]*uv[i][1];
AB[0]=re; AB[1]=im;
}
else { // facteur u+iv
re=AB[0]*uv[i][0]-AB[1]*uv[i][1];
im=AB[1]*uv[i][0]+AB[0]*uv[i][1];
AB[0]=re; AB[1]=im;
}
} // for j
} // for i
if (disp) msg+=" : ";
msg+=Math.abs(AB[0])+"²+"+Math.abs(AB[1])+"²";
}
//-->
</script>
</head>
<body>
<div class="contents">
<h1>Decompositions as sum of two squares - script</h1>
<form name="f1" method="get" action="#" onSubmit="return false;">
Number to decompose : <input name="rmi"> <input type="button" value="Ok" onClick="reRun();">
<script>
<!--
// dans un script car rmax calculé
document.write(" (value between 1 and "+rmax+")");
// -->
</script>
<br>Large values of n may result in a warning because of very long calculation time.
<br>Arithmetic expressions using ( ) * + - / allowed.
<br><input type="checkbox" name="rdi" value=0> display values in Z[i]
<p><div id="res"> <!-- resultat --> </div>
<script>
<!--
document.f1.rmi.value=rmin; // mise a jour du formulaire
if (disp) document.f1.rdi.checked=1;
if (rmin) { // valeur à traiter, parametre d'appel
doit();
}
//-->
</script>
</form>
<noscript>
JavaScript mandatory ! na !
</noscript>
<p>
</div>
</body>
</html>
And the answer is:
0
1
0
36
1
2
0
0
20
32
0
0
4
24
2
0
0
0
0
12