Exercices (pc1)
Corrigé

1. La procédure suivante calcule les termes de dans .

 procedure Farey (h, k, h1, k1, n: integer);
  var
   h2, k2: integer;
 begin
  h2 := h + h1;
  k2 := k + k1;
  if k2 < n then
   begin
    Farey(h, k, h2, k2, n);
    writeln(h2, k2);
    Farey(h2, k2, h1, k1, n)
   end;
 end;

2. Tout d'abord h'/k' est réduite car

Ensuite, on a par définition

On en déduit que

et

Ainsi h'/k' est dans la suite (parce que h',k'>0 et ) et h''/k'' est le médiant de h/k et de h'/k'.

Le programme est donc :

procedure Farey2(n:integer);
 var h, k, h2, k2, h1, k1, f: integer;
 begin
  h:= 0; k:= 1;
  writeln(0,1);
  h2:= 1;k2:= n;
  writeln(1,n);
  while k2<>1 do begin
   f := (k+n) div k2;
   h1:= f*h2 - h;
   k1:= f*k2 - k;
   writeln(h1,k1);
   h:= h2; k:= k2;
   h2:=h1;k2:=k1;
  end;
end;

• About this document ...