Program computing the Hirzebruch-Jung continued fraction

Question

For relatively prime positive integers $a>b>1$, it is known that there are uniquely determined integers $a_1,\dots,a_n\geq2$ such that $$\frac{a}{b}=a_1-\frac{1}{a_2-\frac{1}{\cdots-\frac{1}{a_n}}}=:[a_1,\dots,a_n],$$ and this is called the Hirzebruch-Jung continued fraction of $a/b$.

These integers are determined as follows: First write $a=q_1b+r_1$ with $0<r_1<b$ (division algorithm), and put $a_1:=q_1+1$. Now $\frac{a}{b}=a_1-\frac{b-r_1}{b}$. If $b-r_1=1$, then put $a_2=b$ and we are done. Otherwise, continue the process with the pair $(b,b-r_1)$ instead of $(a,b)$.

I was looking for a program / online calculator for computing this, but I couldn't find any Hirzebruch-Jung continued fraction calculators online. (I've only found https://mathoverflow.net/questions/89529/reference-request-program-to-work-with-cyclic-quotient-singularities, but the link in the answer does not work.) I don't know how to code (using matlab, etc.), but I expect that this can be algorithmized to make a program that outputs the integers $a_1,\dots,a_n$ if we input $a$ and $b$. Is there any such program about this?

Answer 1

C++, using ordinary size integers

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

#include <iostream>
#include <stdlib.h>
#include <fstream>
#include <strstream>
#include <list>
#include <set>
#include <math.h>
#include <iomanip>
#include <string>
#include <algorithm>
#include <iterator>
#include <gmp.h>
#include <gmpxx.h>

using namespace std;

//   g++  -o Hirzebruch_Jung  Hirzebruch_Jung.cc  -lgmp -lgmpxx

 //    ./Hirzebruch_Jung  

int par( int n, int d)
{
  int q = n/d;  if( n % d != 0)  ++q;
  int r = q*d - n;
  cout << " $$ \\frac{ " << n << " }{ " << d << " } = " << q << " -  \\frac{ " << r << " }{ " <<  d << " } $$ " << endl;
  return q;
}

  int main(int argc, char *argv[])
{
  if ( argc != 3) cout << "Usage: ./Hirzebruch_Jung  Big   Little   " << endl;
  else {
  
    
    int p = atoi(argv[1]);
      int q = atoi(argv[2]);

  int ppp = p;
  int qqq = q;
    
  int gcd ;
  int a[46];
  for(int i = 0; i < 46; ++i) a[i] = 0;
    cout << endl <<  " $$  \\gcd( " << ppp << ", " << qqq << " ) = ???  "  << "  $$  " << endl << endl;

  int step = 0;
 while ( q != 0)
 {
    int r = par(p,q);
    a[step] = r;
    ++step;
    int pp = q;
     q = q*r - p;
     p = pp;
 }


 cout << " Simple continued fraction tableau:  "  << endl;

  cout << " $$ " << endl;
  cout << " \\begin{array}{";
   for( int j = 0; j <= step; ++j)
 {
  cout  << "cc" ;
 }
 cout << "}" << endl;
  int n[ 5 + step];
  int d[ 5 + step];
  n[0] = 0;  n[1] = 1;
  d[0] = -1; d[1] = 0;
 for( int j = 0; j < step; ++j)
 {
  cout  << " & & "<< a[j] ;
   n[j+2] = - n[j] + a[j] * n[j+1];
   d[j+2] = - d[j] + a[j] * d[j+1];
 }
  cout << " & \\\\ " << endl;
  for( int j = 0; j <= step + 1; ++j)
 {
 cout << "  \\frac{ " << n[j] << " }{ " << d[j] << " }  ";
   if( j == 0 ) cout << " & ";
   else if ( j < step + 1) cout << " & & " ;
 }
  cout << endl << " \\end{array}" << endl;
  cout << " $$ " << endl;
  cout << " $$  $$ " << endl;

  if(step > 12) {
  cout << " $$ " << endl;
  cout << " \\begin{array}{ccc}" << endl;
 
   for(int i = 1; i <= 1+ step; ++i)
   cout << "  \\frac{ " << n[i] << " }{ " << d[i] << " }  "  << " &     \\mbox{digit}  &  " << a[i-1] << "  \\\\  " << endl;
    
  
  cout <<  " \\end{array}" << endl;
  cout << " $$ " << endl << endl ;
  cout << endl << endl;
  } // if 0

  mpz_class final_num =  n[1 +step ];
  mpz_class penultimate_num = n[step];
  mpz_class final_den =  d[1 +step ];
  mpz_class penultimate_den = d[step];
  mpz_class cross = final_num * penultimate_den - final_den * penultimate_num;
  cout  << " $$ " << final_num << " \\cdot " << penultimate_den << " - " << final_den   << " \\cdot " << penultimate_num << " = " << cross  << " $$ " << endl;
  gcd = ppp / n[1+step] ;
  if ( gcd > 1 ) 
  {
    cout << endl <<  " $$  \\gcd( " << ppp << ", " << qqq << " ) = " << gcd << "  $$  " << endl;
  cout  << " $$ " << gcd * final_num << " \\cdot " << penultimate_den << " - " << gcd * final_den   << " \\cdot " << penultimate_num << " = " << gcd * cross  << " $$ " << endl << endl;
  }
  } // else
  return 0;
}
 

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

Answer 2

found my program for gcd, it writes the fraction as the usual continued fraction. Your thing should be a small tweak, just the calculation steps.

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

H-J

$$ \gcd( 5, 4 ) = ??? $$

$$ \frac{ 5 }{ 4 } = 2 - \frac{ 3 }{ 4 } $$ $$ \frac{ 4 }{ 3 } = 2 - \frac{ 2 }{ 3 } $$ $$ \frac{ 3 }{ 2 } = 2 - \frac{ 1 }{ 2 } $$ $$ \frac{ 2 }{ 1 } = 2 - \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccc} & & 2 & & 2 & & 2 & & 2 & \\ \frac{ 0 }{ -1 } & \frac{ 1 }{ 0 } & & \frac{ 2 }{ 1 } & & \frac{ 3 }{ 2 } & & \frac{ 4 }{ 3 } & & \frac{ 5 }{ 4 } \end{array} $$ $$ $$ $$ 5 \cdot 3 - 4 \cdot 4 = -1 $$

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

$$ \gcd( 12345, 401 ) = ??? $$

$$ \frac{ 12345 }{ 401 } = 31 - \frac{ 86 }{ 401 } $$ $$ \frac{ 401 }{ 86 } = 5 - \frac{ 29 }{ 86 } $$ $$ \frac{ 86 }{ 29 } = 3 - \frac{ 1 }{ 29 } $$ $$ \frac{ 29 }{ 1 } = 29 - \frac{ 0 }{ 1 } $$ Simple continued fraction tableau:
$$ \begin{array}{cccccccccc} & & 31 & & 5 & & 3 & & 29 & \\ \frac{ 0 }{ -1 } & \frac{ 1 }{ 0 } & & \frac{ 31 }{ 1 } & & \frac{ 154 }{ 5 } & & \frac{ 431 }{ 14 } & & \frac{ 12345 }{ 401 } \end{array} $$ $$ $$ $$ 12345 \cdot 14 - 401 \cdot 431 = -1 $$ 1 1

$$ \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc \bigcirc $$

jagy@gost:~/Desktop/Cplusplus$ ./Hirzebruch_Jung 1073741824 663608943

$$ \gcd( 1073741824, 663608943 ) = ??? $$

$$ \frac{ 1073741824 }{ 663608943 } = 2 - \frac{ 253476062 }{ 663608943 } $$ $$ \frac{ 663608943 }{ 253476062 } = 3 - \frac{ 96819243 }{ 253476062 } $$ $$ \frac{ 253476062 }{ 96819243 } = 3 - \frac{ 36981667 }{ 96819243 } $$ $$ \frac{ 96819243 }{ 36981667 } = 3 - \frac{ 14125758 }{ 36981667 } $$ $$ \frac{ 36981667 }{ 14125758 } = 3 - \frac{ 5395607 }{ 14125758 } $$ $$ \frac{ 14125758 }{ 5395607 } = 3 - \frac{ 2061063 }{ 5395607 } $$ $$ \frac{ 5395607 }{ 2061063 } = 3 - \frac{ 787582 }{ 2061063 } $$ $$ \frac{ 2061063 }{ 787582 } = 3 - \frac{ 301683 }{ 787582 } $$ $$ \frac{ 787582 }{ 301683 } = 3 - \frac{ 117467 }{ 301683 } $$ $$ \frac{ 301683 }{ 117467 } = 3 - \frac{ 50718 }{ 117467 } $$ $$ \frac{ 117467 }{ 50718 } = 3 - \frac{ 34687 }{ 50718 } $$ $$ \frac{ 50718 }{ 34687 } = 2 - \frac{ 18656 }{ 34687 } $$ $$ \frac{ 34687 }{ 18656 } = 2 - \frac{ 2625 }{ 18656 } $$ $$ \frac{ 18656 }{ 2625 } = 8 - \frac{ 2344 }{ 2625 } $$ $$ \frac{ 2625 }{ 2344 } = 2 - \frac{ 2063 }{ 2344 } $$ $$ \frac{ 2344 }{ 2063 } = 2 - \frac{ 1782 }{ 2063 } $$ $$ \frac{ 2063 }{ 1782 } = 2 - \frac{ 1501 }{ 1782 } $$ $$ \frac{ 1782 }{ 1501 } = 2 - \frac{ 1220 }{ 1501 } $$ $$ \frac{ 1501 }{ 1220 } = 2 - \frac{ 939 }{ 1220 } $$ $$ \frac{ 1220 }{ 939 } = 2 - \frac{ 658 }{ 939 } $$ $$ \frac{ 939 }{ 658 } = 2 - \frac{ 377 }{ 658 } $$ $$ \frac{ 658 }{ 377 } = 2 - \frac{ 96 }{ 377 } $$ $$ \frac{ 377 }{ 96 } = 4 - \frac{ 7 }{ 96 } $$ $$ \frac{ 96 }{ 7 } = 14 - \frac{ 2 }{ 7 } $$ $$ \frac{ 7 }{ 2 } = 4 - \frac{ 1 }{ 2 } $$ $$ \frac{ 2 }{ 1 } = 2 - \frac{ 0 }{ 1 } $$ Hirzebruch_Jung continued fraction tableau:
$$ \begin{array}{cccccccccccccccccccccccccccccccccccccccccccccccccccccc} & & 2 & & 3 & & 3 & & 3 & & 3 & & 3 & & 3 & & 3 & & 3 & & 3 & & 3 & & 2 & & 2 & & 8 & & 2 & & 2 & & 2 & & 2 & & 2 & & 2 & & 2 & & 2 & & 4 & & 14 & & 4 & & 2 & \\ \frac{ 0 }{ -1 } & \frac{ 1 }{ 0 } & & \frac{ 2 }{ 1 } & & \frac{ 5 }{ 3 } & & \frac{ 13 }{ 8 } & & \frac{ 34 }{ 21 } & & \frac{ 89 }{ 55 } & & \frac{ 233 }{ 144 } & & \frac{ 610 }{ 377 } & & \frac{ 1597 }{ 987 } & & \frac{ 4181 }{ 2584 } & & \frac{ 10946 }{ 6765 } & & \frac{ 28657 }{ 17711 } & & \frac{ 46368 }{ 28657 } & & \frac{ 64079 }{ 39603 } & & \frac{ 466264 }{ 288167 } & & \frac{ 868449 }{ 536731 } & & \frac{ 1270634 }{ 785295 } & & \frac{ 1672819 }{ 1033859 } & & \frac{ 2075004 }{ 1282423 } & & \frac{ 2477189 }{ 1530987 } & & \frac{ 2879374 }{ 1779551 } & & \frac{ 3281559 }{ 2028115 } & & \frac{ 3683744 }{ 2276679 } & & \frac{ 11453417 }{ 7078601 } & & \frac{ 156664094 }{ 96823735 } & & \frac{ 615202959 }{ 380216339 } & & \frac{ 1073741824 }{ 663608943 } \end{array} $$ $$ $$

$$ $$ $$ \begin{array}{ccc} \frac{ 1 }{ 0 } & \mbox{digit} & 2 \\ \frac{ 2 }{ 1 } & \mbox{digit} & 3 \\ \frac{ 5 }{ 3 } & \mbox{digit} & 3 \\ \frac{ 13 }{ 8 } & \mbox{digit} & 3 \\ \frac{ 34 }{ 21 } & \mbox{digit} & 3 \\ \frac{ 89 }{ 55 } & \mbox{digit} & 3 \\ \frac{ 233 }{ 144 } & \mbox{digit} & 3 \\ \frac{ 610 }{ 377 } & \mbox{digit} & 3 \\ \frac{ 1597 }{ 987 } & \mbox{digit} & 3 \\ \frac{ 4181 }{ 2584 } & \mbox{digit} & 3 \\ \frac{ 10946 }{ 6765 } & \mbox{digit} & 3 \\ \frac{ 28657 }{ 17711 } & \mbox{digit} & 2 \\ \frac{ 46368 }{ 28657 } & \mbox{digit} & 2 \\ \frac{ 64079 }{ 39603 } & \mbox{digit} & 8 \\ \frac{ 466264 }{ 288167 } & \mbox{digit} & 2 \\ \frac{ 868449 }{ 536731 } & \mbox{digit} & 2 \\ \frac{ 1270634 }{ 785295 } & \mbox{digit} & 2 \\ \frac{ 1672819 }{ 1033859 } & \mbox{digit} & 2 \\ \frac{ 2075004 }{ 1282423 } & \mbox{digit} & 2 \\ \frac{ 2477189 }{ 1530987 } & \mbox{digit} & 2 \\ \frac{ 2879374 }{ 1779551 } & \mbox{digit} & 2 \\ \frac{ 3281559 }{ 2028115 } & \mbox{digit} & 2 \\ \frac{ 3683744 }{ 2276679 } & \mbox{digit} & 4 \\ \frac{ 11453417 }{ 7078601 } & \mbox{digit} & 14 \\ \frac{ 156664094 }{ 96823735 } & \mbox{digit} & 4 \\ \frac{ 615202959 }{ 380216339 } & \mbox{digit} & 2 \\ \frac{ 1073741824 }{ 663608943 } & \mbox{digit} & 0 \\ \end{array} $$

$$ 1073741824 \cdot 380216339 - 663608943 \cdot 615202959 = -1 $$