Task

The objective is to write a function that finds the sum of all positive multiples of 3 or 5 below n.

Show output for n = 1000.

This is is the same as Project Euler problem 1.

Extra credit: do this efficiently for n = 1e20 or higher.




! Find the sum of multiples of two factors below a limit -
! Project Euler problem 1: multiples of 3 or 5 below 1000 & 10**20;
BEGIN
    INTEGER PROCEDURE GCD(a, b); INTEGER a, b;
        GCD := IF b = 0 THEN a ELSE GCD(b, MOD(a, b));
 
    ! sum of multiples of n up to limit;
    INTEGER PROCEDURE multiples(n, limit); INTEGER n, limit;
    BEGIN
        INTEGER m;
        m := limit // n;
    ! moving //2 to sumMultiples() looked just too silly    ;
        multiples := n*((m*(m+1)) // 2) ! and risks overflow;
    END
    ! sum of multiples of n or m below limit;
    INTEGER PROCEDURE sumMultiples(n, m, limit);
        INTEGER n, m, limit;
    BEGIN
        INTEGER LCM;
        LCM:= (n // GCD(n, m)) * m;
        limit := limit-1;
        sumMultiples := multiples(n, limit) + multiples(m, limit)
                        - multiples(LCM, limit)
    END sumMultiples;
 
    ! Extra creditable: math is about avoiding calculation tedium;
    TEXT PROCEDURE repeat(c, n); CHARACTER c; INTEGER n; BEGIN
        TEXT r; r :- BLANKS(n);
        FOR n := n STEP -1 UNTIL 1 DO r.PUTCHAR(c);
        repeat :- r;
    END;
    TEXT PROCEDURE sumOfMultiplesOf3or5below10toThePowerOf(e);
        INTEGER e;
    sumOfMultiplesOf3or5below10toThePowerOf :-
        IF e < 1 THEN "0" ELSE IF e = 1 THEN "23"
        ELSE "23" & repeat('3', e-2)
            & "1" & repeat('6', e-2) & "8";
 
    INTEGER factor, n;
    FOR factor := 5 !, 2, 6;
                    DO BEGIN
        OUTTEXT("sum of positive multiples of 3 and");
        OUTINT(factor, 2); OUTCHAR(':');
        FOR n := ! 1 STEP 1 UNTIL 15, 100,;
                 1000 DO BEGIN
            OUTCHAR(' '); OUTINT(sumMultiples(3, factor, n), 0)
        END;
        OUTIMAGE
    END;
    FOR n := 0, 1, 3, 5, 10, 20, 40 DO BEGIN
        OUTTEXT(sumOfMultiplesOf3or5below10toThePowerOf(n));
        OUTIMAGE
    END
END