Hacker News Reader

Comment by marcodiego | Hacker News Reader

Took a look at the simplest problem:

  Multiples of 3 or 5
  
  Problem 1
  
  If we list all the natural numbers below 10 that are multiples of 3 or 5, we get 3, 5, 6 and 9. The sum of these multiples is 23.
  
  Find the sum of all the multiples of 3 or 5 below 1000.

The naive idea is: iterate from 0 to 1000, test each number, add it to an (initially zeroed) accumulator when adequate. A little bit of thinking... ok, sum the multiples of 3, add the multiples of 5 and subtract multiples of 15. A little more bit of thinking: sum of multiples of 3, 5 and subtract multiples of 15. These can be calculated using an arithmetic progression formula in O(1) and limits can be found using rest of division operation.

Cool! Even a simple problem made me think of a naive solution and how to iteratively improve it.

View on HN

An you explain me the difference between your solution 2 and 3?

As in:

  sum [i | i <- [1..1000], i % 3 == 0 || i % 5 == 0]

  sum [3,6..1000] + sum [5,10..1000] - sum [15,30..1000]

  rsum 3 + rsum 5 - rsum 15 where
    rsum n = let (k,r) = 1000 `divMod` n in rsum' 0 (1000 - r) k
    rsum' f l n = (n*(f + l)) `div` 2

1. is the best solution. That's because it is the only solution that encodes the problem in a way that it is still obvious what is being done. 2. and 3. are incomplete without a pile of documentation to explain why they do what they do and what you'd need to do to modify them in case the inputs change.

The first runs in linear[1] time and the last in constant time. One can write it more readably:

  sum_arithmetic_progression first last length =
    -- to compute S = first + (first+k) + (first+2k) + … + (first+length*k = last)
    -- write it backwards and add corresponding terms:
    -- 2S = (first+last) + ((first+k)+(last-k)) + … + (last+first)
    --    = (first+last) + … + (first+last)
    --      \____ length times ___________/
    (first + last) * length `div` 2

  -- = sum [i | i<- [1..upperBound], i%n == 0] but fast
  sum_multiples n upperBound =
    sum_arithmetic_progression n last count where
      (count,r) = upperBound `divMod` n
      last = upperBound - r

  subsets [] = [[]]
  subsets (x:xs) = [set | sub <- subsets xs, set <- [x:sub,sub]]

  -- given some sets [A,B,…,C] and a function count_intersection which acts like the sum of some function on the elements in the intersection of a list of sets, compute the count of their union using the inclusion–exclusion principle. 
  inclusion_exclusion count_intersection sets =
    sum [count_intersection sub * (if odd (length sub) then 1 else -1) | sub <- subsets sets, sub != []]
  
  answer = inclusion_exclusion sum_multiples' [3,5] where
    sum_multiples' factors =
      -- the sum of the numbers which are multiples of all the numbers in factors is the sum of the multiples of their lowest common multiple
      sum_multiples (foldr lcm 1 factors) 1000

The point of project Euler is not to make you write clean or clear code but rather to make you write code that exploits the mathematical structure of the problem to find the answer with less computation.

Solution 2 is still iterating, once by 3, then by 5 then by 15.

Solution 3 uses the closed-form solutions the the question "what is the sum of the multiples of k between x and y".

If you're not familiar with that last part, it's pretty easy to get there from the formula for the sum of numbers from 1 to n, ie n(n+1)/2 (which is itself ~easy to see by pairing up 1 and n, then 2 and (n-1) and etc.)

Reply on news.ycombinator.com