Project Euler Problem 1
Part 1,2
Project Euler problem 1 wants a person to find the sum of all numbers less than 1000 that are divisible by 3 and 5. I was able solve this problem pretty easily in Scala. My solution is very similar to how I would solve the problem in Java. Quickly glancing at the code, you can see there is less of it. Keywords in Java like Public and static aren’t in here. It may not see like much, but it adds up.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | object Euler001 { def main(args: Array[String]) { var a = 0 var sum = 0 while(a < 1000) { if(a%3 == 0 || a%5 == 0) sum = sum + a a = a + 1 } println(sum) } } |
Using a while loop solved the problem. I have more variations of the solution I will post later. If you are trying to learn a new programming language, projects like Euler is a great way to do this. For now just trust me, I will write a follow up article on why.

Colin Dellow 1:24 pm on December 14, 2011 Permalink |
Pfft, that’s far too readable.
def reduce(i: Int) = if(i % 3 == 0 || i % 5 == 0) i else 0
(0 /: (0 until 1000)) { _ + reduce(_) }
Much better!
Xavier 1:36 pm on December 14, 2011 Permalink |
Pfff, that’s far too brutal:
3 * 333 * 334 / 2 + 5 * 199 * 200 / 2 – 15 * 66 * 67 / 2 is much better! =)
Eliot 5:00 pm on December 14, 2011 Permalink |
I never thought about it that way. How did you come up with that approach?
Xavier 6:57 am on December 15, 2011 Permalink |
Well, you don’t need Scala or any other programming language, good old math can do it for you
solution
= sum of multiples of 3 < 1000
+ sum of multiples of 5 < 1000
sum of n first numbers = n*(n+1)/2
sum of n first multiples of x = x*n*(n+1)/2
there are 333 multiples of 3 < 1000 (last one is 333 * 3 = 999)
there are 199 multiples of 5 < 1000 (last one is 199 * 5 = 995)
there are 66 multiples of 15 < 1000 (last one is 66 * 15 = 990)
I know that many people with coding skills will try to brute-force every project-euler problems… but some of those problems actually don't need to be brute-forced.
Eliot 1:23 pm on December 15, 2011 Permalink
Very good point brute force is not needed for this one. Thanks for the explanation.
Didier 11:09 am on January 11, 2013 Permalink
ok for good old math but where your magical numbers 333, 199, 66 are coming from. is there a mathematical formula to calculate how many multiples of x there are between a and b ??
Colin Dellow 1:41 pm on December 14, 2011 Permalink |
To explain my solution, I recast your imperative solution in a functional form. The two mutable variables you used — sum and a — were replaced with a foldLeft and a sequence.
What was a comes from (0 until 1000) — a Seq[Int] that includes the numbers 0 <= i accumulator + reduce(current) }
Which says: Initialize accumulator to 0. Iterate over the numbers for 0 until 1000, updating accumulator as needed.
You can then use Scala’s magic _ syntax sugar to make it more concise. Whenever you’re defining a function whose parameters are known (in this case, the accumulator = accumulator + reduce(current) is actually a function whose type is defined by the foldLeft function), if you use each parameter exactly once, each subsequent use of _ refers to the next parameter.
So, you could rewrite as:
(0 until 1000).foldLeft(0) { _ + reduce(_) }
Kim 2:07 pm on December 14, 2011 Permalink |
noobs…;)
1 to 1000 filter { x => x % 3 == 0 || x % 5 == 0 } sum
ohboy 2:47 pm on December 14, 2011 Permalink |
Please take some time to learn the language before posting these kinds of “solutions”. What you’ve done was just translate a Java solution and say it’s Scala, very very bad coding style. Kim’s solution is how you should be thinking about this in Scala.
ohboy 3:46 pm on December 14, 2011 Permalink |
To elaborate on what is condireded “bad style” in your code:
mutable variables: Scala promotes functional style coding, where everything is immutable
loop over a range/collection: again functional style transformations are preferred, look at reduce, fold, map, filter, sum, etc.
(and lose those semicolons, they’re evil
Eliot 6:21 pm on December 14, 2011 Permalink |
I removed the semi-colons. Thank you for your insight. I appreciate your opinion. I feel that posting Java-Scala hybrid solutions help people understand the new concepts in Scala. I never stated use this code in production, or this is “good style.” I stated this is a solution I came up with.
Chinmay 8:45 pm on April 30, 2013 Permalink |
println((1 until x).filter(a => a % 3 == 0 || a % 5 == 0).foldLeft(0)(_+_))