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.




implement Sum3and5;
 
include "sys.m"; sys: Sys;
include "draw.m";
include "ipints.m"; ipints: IPints;
	IPint: import ipints;
 
Sum3and5: module {
	init: fn(nil: ref Draw->Context, args: list of string);
};
 
ints: array of ref IPint;
 
init(nil: ref Draw->Context, args: list of string)
{
	sys = load Sys Sys->PATH;
	ipints = load IPints IPints->PATH;
 
	# We use 1, 2, 3, 5, and 15:
	ints = array[16] of ref IPint;
	for(i := 0; i < len ints; i++)
		ints[i] = IPint.inttoip(i);
 
	args = tl args;
	while(args != nil) {
		h := hd args;
		args = tl args;
		# If it's big enough that the result might not
		# fit inside a big, we use the IPint version.
		if(len h > 9) {
			sys->print("%s\n", isum3to5(IPint.strtoip(h, 10)).iptostr(10));
		} else {
			sys->print("%bd\n", sum3to5(big h));
		}
	}
}
 
triangle(n: big): big
{
	return((n * (n + big 1)) / big 2);
}
 
sum_multiples(n: big, limit: big): big
{
	return(n * triangle((limit - big 1) / n));
}
 
sum3to5(limit: big): big
{
	return(
		sum_multiples(big 3, limit) +
		sum_multiples(big 5, limit) -
		sum_multiples(big 15, limit));
}
 
itriangle(n: ref IPint): ref IPint
{
	return n.mul(n.add(ints[1])).div(ints[2]).t0;
}
 
isum_multiples(n: ref IPint, limit: ref IPint): ref IPint
{
	return n.mul(itriangle(limit.sub(ints[1]).div(n).t0));
}
 
isum3to5(limit: ref IPint): ref IPint
{
	return(
		isum_multiples(ints[3], limit).
		add(isum_multiples(ints[5], limit)).
		sub(isum_multiples(ints[15], limit)));
}
 