Stern-Brocot sequence: Difference between revisions

=={{header|Modula-2}}==

<lang modula2>MODULE SternBrocot;

FROM InOut IMPORT WriteString, WriteCard, WriteLn;

CONST Amount = 1200;

VAR stern: ARRAY [1..Amount] OF CARDINAL;

i: CARDINAL;

PROCEDURE GCD(a,b: CARDINAL): CARDINAL;

VAR c: CARDINAL;

BEGIN

WHILE b # 0 DO

c := a MOD b;

a := b;

b := c;

END;

RETURN a;

END GCD;

PROCEDURE Generate;

VAR i: CARDINAL;

BEGIN

stern[1] := 1;

stern[2] := 1;

FOR i := 2 TO Amount DIV 2 DO

stern[i*2 - 1] := stern[i] + stern[i-1];

stern[i*2] := stern[i];

END;

END Generate;

PROCEDURE FindFirst(n: CARDINAL): CARDINAL;

VAR i: CARDINAL;

BEGIN

FOR i := 1 TO Amount DO

IF stern[i] = n THEN

RETURN i;

END;

END;

END FindFirst;

PROCEDURE ShowFirst(n: CARDINAL);

BEGIN

WriteString("First");

WriteCard(n,4);

WriteString(" at ");

WriteCard(FindFirst(n), 4);

WriteLn;

END ShowFirst;

BEGIN

Generate;

WriteString("First 15 numbers:");

FOR i := 1 TO 15 DO

WriteCard(stern[i], 2);

END;

WriteLn;

FOR i := 1 TO 10 DO

ShowFirst(i);

END;

ShowFirst(100);

WriteLn;

FOR i := 2 TO Amount DO

IF GCD(stern[i-1], stern[i]) # 1 THEN

WriteString("GCD of adjacent elements not 1 at: ");

WriteCard(i-1, 4);

WriteLn;

HALT;

END;

END;

WriteString("The GCD of every pair of adjacent elements is 1.");

WriteLn;

END SternBrocot.</lang>

{{out}}

<pre>First 15 numbers: 1 1 2 1 3 2 3 1 4 3 5 2 5 3 4

First 1 at 1

First 2 at 3

First 3 at 5

First 4 at 9

First 5 at 11

First 6 at 33

First 7 at 19

First 8 at 21

First 9 at 35

First 10 at 39

First 100 at 1179

The GCD of every pair of adjacent elements is 1.</pre>