# Project Euler #1 in Go (counting multiples of 3 or 5 up to 1000)

I've been working on Project Euler, here was my solution for Problem #1. It gave me the proper answer, but it's egregiously slow. How can I implement this more efficiently? My math skills aren't top-notch, sorry.

package main

import (
"fmt"
)

// Problem1: find the sum of all the multiples of 3 or 5 below 1000.
// x,y: multiples
// z: upper limit
func Problem1(x, y, z int) int {

Multiples := make(map[int]struct{})

var Sum int
for i := 1; i < z; i++ {
XFactor := x * i
YFactor := y * i

if XFactor < z {
Multiples[XFactor] = struct{}{}
}
if YFactor < z {
Multiples[YFactor] = struct{}{}
}
}

for key, _ := range Multiples {
Sum = Sum + key
}

return Sum
}

func main() {
fmt.Println("The answer to problem 1 is: ", Problem1(3,5,1000))
}

• Project Euler is not about implementation, but all about algorithm, if algebra-heavy. (And why does it read answer to problem 2?) – greybeard Sep 2 '16 at 4:42
• Yeah, that's partly what I'm hoping to learn about! I copied it from the wrong line in my program, I fixed it :) – mxplusb Sep 2 '16 at 6:01
• Lookup any PE #1 question here on CR, and you'll find the closed-form solution (which does not require iteration at all). – Martin R Sep 2 '16 at 6:28

## Closed form solution

The problem is basically a sum over an arithmetic sequence, which has the well defined solution (first + last) * count / 2

func ArithmeticSum(first, step, count int) int {
var last int = first + step * (count - 1);
return (first + last) * count / 2;
}


The only difficulty arises from the requirement to sum numbers that are a multiple of both x and y just once. The easiest way to achieve this is to sum x and y independently and subtract the common multiples.

func Problem1(x, y, z int) int {
var sumX int = ArithmeticSum(0, x, (z - 1) / x + 1);
var sumY int = ArithmeticSum(0, y, (z - 1) / y + 1);
var lcm int = Lcm(x, y);
var sumBoth int = ArithmeticSum(0, lcm, (z - 1) / lcm + 1);
return sumX + sumY - sumBoth;
}


Luckily, the common multiples also form an arithmetic series. It's step is the least common multiple of x and y.

func Lcm(a, b int) int {
return a * b  / Gcd(a, b);
}


The least common multiple can be calculated from the greatest common divisor, which itself can be found via Euclid's algorithm.

func Gcd(a, b int) int {
if b == 0 {
return a;
} else {
return Gcd(b, a % b);
}
}

• Ah, cool! These problems are definitely teaching me about a lot of math I've either not used in years or teaching me new algorithms. Thanks! – mxplusb Sep 3 '16 at 20:20