function dig(i){return "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ".charAt(i)};
function digval(c){return "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ".indexOf(c.toUpperCase())};
   
function cnvrt(){
  var bf=document.Fbases.basefr[document.Fbases.basefr.selectedIndex].value;
  var bt=document.Fbases.baseto[document.Fbases.baseto.selectedIndex].value;
  var i,j,n=document.Fbases.fr.value.toUpperCase(),v=0,p,c="";
  for(j=n.length-1,p=1;j>=0;j--,p=p*bf)
	{var d=n.charAt(j);
	 if(digval(d)<0 || digval(d)>=bf)
	     {alert("Character '"+document.Fbases.fr.value.charAt(j)+"' is illegal in your base "+bf+" value to convert.");ERROR()};
     v=v+digval(d)*p
     if(v!=Math.round(v)){alert("The number to convert is too big");ERROR()};
    };
  if(bt==1 && v>50){c="111...111"}
  else while(v>0){ c= (bt==1?"1":dig(v%bt))+c;v=(bt==1?v-1:Math.floor(v/bt)) };
  document.FbasesR.res.value=document.FbasesR.res.value
     +n+"(base "+bf+") = " +(c==""?"0":c)+"("+"base "+bt+")\r"
}



function sayFrep(msg){
  document.FrepR.res.value=document.FrepR.res.value+msg+"\r"};

function showlists(seqs){var a="";
  for(var i=0;i<seqs.length;i++)
     {a=a+" {";
      for(var j=0;j<seqs[i].length;j++)a=a+seqs[i][j]+(j<seqs[i].length-1?",":"");
      a=a+"}"};
  return a};

function fibsets(n){
   var todo=new Array(),j,s,t;todo[0]=revzeck(n);
   for(var i=0;i<todo.length;i++)
     {s=todo[i];
      for(j=2;j<s.length;j++)
         if(s.charAt(j)=="1" && s.charAt(j-1)=="0" && s.charAt(j-2)=="0")
          {t=s.substring(0,j-2)+"110"+(j<s.length?s.substring(j+1):"");
           var known=false;
           for(var k=0;k<todo.length;k++)if(todo[k]==t){known=true;break};
           if(!known)todo[todo.length]=t;
         };
      };
  return todo
};
function bitstoseq(bits){var set=new Array();
      for(var j=0;j<bits.length;j++)
         if(bits.charAt(j)=="1")set[set.length]=fibmemo[j+2];
     return set};
function fibsumSETS(n){
  var s=fibsets(n),sets=new Array(),set=new Array();
  for(var i=0;i<s.length;i++)sets[i]=bitstoseq(s[i]);
  return sets};
  
function r(n){  //the number of Fib sets with sum n; see fibrepALL.pl 
  if(n<=2)return 1;
  var i=2,nn;while(i<=FibMAXINTi&&fibmemo[i]<n){i++};
  if(i>FibMAXINTi){alert("OOps - too big!");ERROR()};
  var nn=(fibmemo[i]==n?i:i-1);
  var k=n-fibmemo[nn];
  if(0<=k&&k<fibmemo[nn-3])return r(fibmemo[nn-2]+k)+r(k);
  if(fibmemo[nn-3]<=k&&k<fibmemo[nn-2])return 2*r(k);
  return r(fibmemo[nn+1]-2-k)
};
function findsets(showthem){
    var n=getInput(document.Frep.inp.value,"the sum","Z+"),all;
    if(n>fibmemo[FibMAXINTi]){alert("Sorry -- the sum is too large");ERROR()};
    //switch(document.Frep.sb[document.Frep.sb.selectedIndex].value){
    //case "sets":
                var c=r(n);
                if(showthem && c>100)
                   if(! confirm("There are "+c+" sets.  Do you want to see this many?"))return;
                  sayFrep(c+" set"+(c>1?"s":"")+" with a sum of "
                      +n+(showthem?": "+showlists(fibsumSETS(n)):""));
    //            break;
    //case "bags":all=fibsumBAGS(n);
    //            sayFrep(all.length+" fib bags for "+n+(showthem?": "+showlists(all):""));
    //            break;}
};
function showzeck(){
  var n=getInput(document.Frep.inp.value,"input","Z+");
  sayFrep("The smallest set with a sum of "+n+" is "+"{"+bitstoseq(revzeck(n))+"}");
};
function givenR(howmany){
  var R=getInput(document.Frep.Rinp.value,"the number of sets","Z+"),
      lo=getInput(document.Frep.loN.value,"the start of the range","Z+"),
      hi=getInput(document.Frep.hiN.value,"the end of the range","Z+");
  if(R==0){
     document.FrepR.res.value=document.FrepR.res.value
        +"All numbers are the sum of at least one Fibonacci set\r";return};
  if(lo>hi){alert("The start of the  range ("+lo+") is bigger than the end of the range ("+hi+")");ERROR()};
  document.FrepR.res.value=document.FrepR.res.value+"In range "
      +lo+".."+hi+(howmany=='all'?" these are the":" the first number that is a")
        +" sum of "+R+" Fibonacci sets"+(howmany=='all'?":\r":" is  ");
        +(howmany=='all'?"\r":"");
  var first=true,ct=0;
  for(i=lo;i<=hi;i++)
     if(r(i)==R){ct++;document.FrepR.res.value=document.FrepR.res.value+(first?"":",")+i; 
          if(first && howmany=='first'){
            document.FrepR.res.value=document.FrepR.res.value+"\r";
           return}; 
           first=false}
  document.FrepR.res.value=document.FrepR.res.value+(ct==0?"[None found]\r":"\r"+ct+" found\r");
};





function z(){
   var n0=getInput(document.Fz.inp.value,"your input number","Z+");
   var nmax=getInput(document.Fz.max.value,"your 'up to' value","Z+");
   if(nmax<n0){alert("Your maximum value must exceed the starting value");return};
   for(var n=n0;n<=nmax;n++)
   {var zr=revzeck(n),nb1s=0;
    for(var i=0;i<zr.length;i++)if(zr.charAt(i)=="1")nb1s++;
    document.FzR.res.value+="The Zeckendorf representation of "+n+" is "+revstr(zr)
       +" with "+nb1s+" ones\r"
   };
 };
 
 
 
 
 
 function thinkcards(){var card=new Array(),c,s;
  var m=getInput(document.thinkofF.max.value,"largest number to choose");
  if(isNaN(m))return;
  if(m<1)halt("The range of numbers must be at least 1");
  s="Think of a number between 1 and "+m+":<br><table cellspacing=0 cellpadding=3 border=1 bgcolor=white>";
  for(var c=0;fibmemo[c+2]<m;c++)
  { s=s+"<tr valign=top><td>";
    for(var i = 1;i<=m;i++) if(revzeck(i).charAt(c)=="1")s=s+i+" ";
    s=s+"</"+"td></"+"tr>";   // to get round validator bug
    c
  }
  s=s+"</"+"tr></"+"table>";  //to get round validator bug
  putmsg(s)
 };
 
 
 
 
 
 
function fibsumBAGS(n){ var bags=new Array(),curbag=new Array();
     function fibbagfrom(ind,n,at){
       //document.FrepR.res.value=document.FrepR.res.value+"fbf "+ind+" "+n+"\r";
       if(n==0){bags[bags.length]=new Array(at);
                for(var i=0;i<at;i++)bags[bags.length-1][i]=curbag[i];
                return};
       while(fibmemo[ind]>n && ind>2)ind--;
       if(ind>=2){fibbagfrom(ind-1,n,at);
                  for(var k=1;n>=k*fibmemo[ind];k++)
                    {curbag[at+k-1]=ind;
                     fibbagfrom(ind-1,n-k*fibmemo[ind],at+k);
                    };
                 };
       };
     if(n==0){bags[0]=new Array();return bags};
     var i=3;while(fibmemo[i]<=n)i++;i--;
     curset=[];fibbagfrom(i,n,0);
     return bags
 };
 
var fbsc=new Array();
function countbags(n){var i=2;while(fibmemo[i]<=n)i++;  return findfbsc(n,i-1)};

function findfbsc(N,MaxI){var MaxF=fibmemo[MaxI];
  if(MaxF==1)return 1;
  if(MaxF>N)return findfbsc(N,MaxI-1);
  if(fbsc[N]&& fbsc[N][MaxI])return fbsc[N][MaxI];
  if(!fbsc[N])fbsc[N]=new Array();
  var c=findfbsc(N-MaxF,MaxI)+findfbsc(N,MaxI-1);
  if(c!=Math.round(c)){alert("Too many bags to count - sorry!");ERROR()};
  fbsc[N][MaxI]=c;
  return c
};

function showfreqs(seqs){var a="",freqs=new Array();
  for(var i=0;i<seqs.length;i++)
    {var max=1;for(var j=0;j<seqs[i].length;j++)if(seqs[i][j]>max)max=seqs[i][j];
     for(var j=1;j<=max-1;j++)freqs[j]=0;
     for(var j=0;j<seqs[i].length;j++)freqs[seqs[i][j]-1]++;
     a+=" "+freqs.slice(1).reverse().join(" ")+","
    }
  return a.slice(1,a.length-1)
}

function showFparts(seqs){var a="";
  for(var i=0;i<seqs.length;i++)
    {for(var j=0;j<seqs[i].length;j++)a=a+fib(seqs[i][j])+"+";
     a=a.slice(0,a.length-1)+" "
    };
 return a
};

function findbags(showthem,kind){
  if(arguments.length==1)kind='bags';
  var n=checkinput(document.FbgF.inp.value,"the sum"),
      m=checkinput(document.FbgF.upto.value,"'up to'");
  if(m==""||isNaN(m))m=n;
  //alert(n+""+m);
  if(n>m)halt("The 'up to' value must be bigger than the starting value");
  var cts=new Array();
  for(var i=n;i<=m;i++)
  {var c=countbags(i);
    putmsg(countbags(i)+" "+kind+" with sum "+i+(showthem?": ":""));
    if(c>200 && showthem){putmsg("Too many to list");return}
    else if(showthem && (c<=50 || c<=100 && confirm("There are "+c+" "+kind
            +" for "+i+".  List them all?")))
    putmsg(kind=='bags'?showFparts(fibsumBAGS(i)):showfreqs(fibsumBAGS(i)))
    else if(showthem)return
    else cts[i-n]=c
  };
  if(!showthem && m>n)putmsg(cts.join(","))
};


function negfibs(){var s;
  var n=getInput(document.negfibcalcF.N.value,"starting value","Z");
      m=(document.negfibcalcF.Nto.value==""?n:getInput(document.negfibcalcF.Nto.value,"up to value","Z"));
  var inc=(m<n?-1:1);
 //  alert(n+".."+m);
 if(m==n){ putmsg(n+" = "+negfib(n)+"(-Fib)");return};
 s="<table><tr><th>n</th><th>n(-Fib)</th></tr>";
  for(var i=n;(inc>0?i<=m:i>=m);i=i+inc)
    s=s+"<tr align=right><td>"+i+"</td><td>"+negfib(i)+"</td></tr>";
  putmsg(s+"</table>");
}

function negfib(n){var inds=new Array();
  if(n==0)return "0";
  var absn=(n<0?-n:n);
  for(var i=1;! (n>0&&fib(i-1)<n&&n<=fib(i) || n<0&&fib(i-1)<=-n&&-n<fib(i) || fib(-i)==n);i++);
   if(n>0&&i%2==0 ||n<0&&i%2==1){i--}
  

  //putmsg(n+' starts at fib('+ i+")="+fib(i));
  var negfib=new Array(i);
  for(var i=0;i<negfib.length;i++)negfib[i]=0;
  var ok=true;
  while(ok)
  {//putmsg(n+" "+negfib);
   for(var i=1;! (n>0&&fib(i-1)<n&&n<=fib(i) || n<0&&fib(i-1)<=-n&&-n<fib(i) || fib(-i)==n);i++);
   if(n>0&&i%2==0 ||n<0&&i%2==1){i--}

   absn=(n<0?-n:n);
  //putmsg("i="+i+" fib(-i)="+fib(-i)+" n="+n);
 // if(i<0)halt("---");
   
       if(fib(-i)==n){ok=false;}
   else if(n==1){i=1;ok=false;}
   else if(n==-1){i=2;ok=false}
   else if(n>0&&i%2==1 || n<0&&i%2==0)
    {//putmsg("use t fib("+(-i)+")="+fib(-i));
    inds[inds.length]=-i;n-=fib(-i);negfib[i]=1;}
   else {//putmsg("use f fib("+(1-i)+")="+fib(-i+1));
    inds[inds.length]=-i+1;n-=fib(-i+1);negfib[i-1]=1;};
 //  if(!confirm(""))break;
  };
  if(n!=0){//putmsg("end fib("+(-i)+")="+fib(-i));
           inds[inds.length]=i;negfib[i]=1};
  negfib=negfib.slice(1).reverse();
  //fromnegfib(negfib.join(""));
  return negfib.join("");
};
  
function fromnegfib(negf){
  if(arguments.length==0) negf=document.negfibcalcF.NF.value;
  negf=negf.replace(/\s/g,"");
  if(negf.replace(/[01]/g,"")!="")halt("(-Fib) representations can only contains 0s and 1s");
  var v=0,L=negf.length
  for(i=0;i<L;i++)
    if(negf.charAt(L-1-i)=="1")v+=fib(-i-1);
  putmsg(negf+"(-Fib) = "+v);
};