MODULE DuffinianNumbers;
FROM InOut IMPORT WriteCard, WriteString, WriteLn;

CONST
    MaxSigma = 10000;

VAR
    seen, cur: CARDINAL;
    sigma: ARRAY [1..MaxSigma] OF CARDINAL;

PROCEDURE CalculateSigmaTable;
    VAR i, j: CARDINAL;
BEGIN
    FOR i := 1 TO MaxSigma DO
        sigma[i] := 0
    END;
    FOR i := 1 TO MaxSigma DO
        j := i;
        WHILE j <= MaxSigma DO
            INC(sigma[j], i);
            INC(j, i);
        END
    END
END CalculateSigmaTable;

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 IsDuffinian(n: CARDINAL): BOOLEAN;
BEGIN
    RETURN (sigma[n] > n+1) AND (GCD(n, sigma[n]) = 1)
END IsDuffinian;

PROCEDURE IsDuffinianTriple(n: CARDINAL): BOOLEAN;
BEGIN
    RETURN IsDuffinian(n) AND IsDuffinian(n+1) AND IsDuffinian(n+2)
END IsDuffinianTriple;

BEGIN
    CalculateSigmaTable;
    WriteString("First 50 Duffinian numbers:");
    WriteLn;
    cur := 0;
    FOR seen := 1 TO 50 DO
        REPEAT INC(cur) UNTIL IsDuffinian(cur);
        WriteCard(cur, 4);
        IF seen MOD 10 = 0 THEN WriteLn END
    END;

    WriteLn;
    WriteString("First 15 Duffinian triples:");
    WriteLn;
    cur := 0;
    FOR seen := 1 TO 15 DO
        REPEAT INC(cur) UNTIL IsDuffinianTriple(cur);
        WriteCard(cur, 6);
        WriteCard(cur+1, 6);
        WriteCard(cur+2, 6);
        WriteLn
    END
END DuffinianNumbers.