Project Euler 6: Difference between sum of squares and square of sum

Question

I've created a (very) simple solution for Project Euler problem 6:

Project Euler Problem 6: Sum square difference

The sum of the squares of the first ten natural numbers is,

$$ 1^2 + 2^2 + ... + 10^2 = 385 $$

The square of the sum of the first ten natural numbers is,

$$ (1 + 2 + ... + 10)^2 = 55^2 = 3025 $$

Hence the difference between the sum of the squares of the first ten natural numbers and the square of the sum is \$3025 − 385 = 2640\$.

Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

Solution:

\$25164150\$

To solve this in F# was pretty simple: I simply declared a function square which would multiply an x by itself, then a function which would run through a list of numbers and add the square of the sum of them, and subtract the sum of the squares of each.

let square x =
    x * x

let calcDiffSquareSumFromSumSquares list = 
    (list |> List.sum |> square) - (list |> List.sumBy square)

printfn "Solution to Project Euler 6: %i" (calcDiffSquareSumFromSumSquares [ 1 .. 100 ])

On this one, I'm particularly curious if there's a functional way to run through the list only once, calculate the total sum, and calculate the squares of sums so that I wouldn't need to use two sum methods.

Answer 1

Looks good to me.

Couple of things to consider though:

• You could split out two functions, squareOfSum and sumOfSquares. I think that would make it a little easier to read.
• You could make the functions more general by using Seq.sum/Sum.sumBy instead of List.sum/List.sumBy.
• While you could use fold, as joranvar mentioned, I think this would make the program much less clear and I would not recommend it (except as an exercise for learning about folds).
• There is another way to attack the problem, by using the two identities

\begin{align} 1 + 2 + 3 + \cdots + n &= \frac{n(n + 1)}{2}, \quad \text{and} \\ 1^2 + 2^2 + 3^2 + \cdots + n^2 &= \frac{n(n+1)(2n+1)}{6}. \end{align}

Answer 2

F# has an exponentiation operator (**). This means that this function:

let square x =
    x * x

Is extraneous and can be removed. In order to change your code to allow for the use of the exponentiation operator, you need to change the following code:

let calcDiffSquareSumFromSumSquares list = 
    (list |> List.sum |> square) - (list |> List.sumBy square)

To this:

let calcDiffSquareSumFromSquares list =
    ((list |> List.sum) ** 2) - (list |> List.sumBy (fun x -> x * x))

Other than that, there's really not much else to comment on, as the code is rather short. Good job so far! :)

Answer 3

You particularly ask on how to traverse the list only once, calculating the sums whilst you go, before finalising the wanted sum. This is doable, and the trick is to duplicate (and square) elements as the first step of the pipeline. This can be done using Seq.map (fun x -> (x, x*x). Then we can use Seq.reduce to sum up these answers, before passing on to the final function for doing the final equation.

Whilst looking on this I also looked on the aspect of presenting a list (v2) or a sequence from within the function (v3), which seems to reduce the time a little.

I also looked for the optimal solution (v4) as suggested by mjolka on calculating the sums instead of traversing the lists before calculating. This resulted in the following code:

let calcDiffSquareSumFromSumSquaresV2 list = 
    list 
    |> Seq.map (fun x -> (x, x*x) ) 
    |> Seq.reduce (fun (accX, accXX) (elemX, elemXX) -> (accX + elemX, accXX + elemXX))
    |> (fun (x, xx) -> x * x - xx)

let calcDiffSquareSumFromSumSquaresV3 n = 
    seq { 1 .. n } 
    |> Seq.map (fun x -> (x, x*x) ) 
    |> Seq.reduce (fun (accX, accXX) (elemX, elemXX) -> (accX + elemX, accXX + elemXX))
    |> (fun (x, xx) -> x * x - xx)

let calcDiffSquareSumFromSumSquaresV4 n = 
    let sumN = n * (n+1) / 2
    let sumNN = n * (n + 1) * (2*n + 1) / 6
    sumN * sumN - sumNN


let n = 100
let myList = [ 1 .. n ]
printfn "Solution to Project Euler 6:"
printfn "  org: %i" (calcDiffSquareSumFromSumSquares myList)
printfn "  v2 : %i" (calcDiffSquareSumFromSumSquaresV2 myList)
printfn "  v3 : %i" (calcDiffSquareSumFromSumSquaresV3 n)
printfn "  v4 : %i" (calcDiffSquareSumFromSumSquaresV4 n)

All of course reports the correct answer. When timing I still see something strange happening, so I've left out the results of that. But common sense indicates that v4 is by far the fastest, v2 should be a little more expensive as it duplicates the lists and can not take full benefit of optimalised sum functions, v3 slighter faster than v2 due to use of sequence. So timewise, the original is not too far off, but it can't really compete with the optimal solution.

Answer 4

For completeness, I will expand my short answer into a longer one.

As @mjolka already suggests, the code would be cleaner and easier to read if you "extract till you drop", introducing squareOfSum and sumOfSquares. Otherwise, the style is naturally very clear.

A minor readability improvement could be writing short functions like square on one line, but that may be a matter of taste.

As for the question: how to run through the list only once, you could use the mother of List.sum and List.sumBy, List.fold, which might indeed make the code slightly less clear, unless you use some useful functions on 2-tuples with readable names:

let square x = x * x

let first f (a, b) = (f a, b)
let second f (a, b) = (a, f b) // For completeness
let uncurry f (a, b) = f a b

let addAndAddSquared (sum, sumOfSquares) x = (sum + x, sumOfSquares + square x)

let calcDiffSquareSumFromSumSquares' list =
    list |> List.fold addAndAddSquared (0,0) |> first square |> uncurry (-)

Finally, you could remove the list named parameter in that last function if you'd like, and prefer composition over piping, like follows:

let calcDiffSquareSumFromSumSquares'' =
    List.fold addAndAddSquared (0,0) >> first square >> uncurry (-)