Exercices (pc1) Corrigé

1. La procédure suivante calcule les termes de F_{n} dans ]\frac{h}{k}, \frac{h′}{k′} [.

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

k′′h′ − k′h′′ = 1

Ensuite, on a par définition

\frac{k + n}{k′′} − 1 < f ≤ \frac{k + n}{k′′}

On en déduit que

0 ≤ n − k′′ < k′ ≤ n

et

0 < \frac{1 + (n − k′′)h′′}{k′′} < h′

Ainsi h′/k′ est dans la suite F_{n} (parce que h′, k′ > 0 et k ≤ n) 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;