ðŸŽ‰ Exercism Research is now launched. Help Exercism, help science and have some fun at research.exercism.io ðŸŽ‰

Published at Apr 14 2021
·
0 comments

Instructions

Test suite

Solution

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

The square of the sum of the first ten natural numbers is (1 + 2 + ... + 10)Â² = 55Â² = 3025.

The sum of the squares of the first ten natural numbers is 1Â² + 2Â² + ... + 10Â² = 385.

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

You are not expected to discover an efficient solution to this yourself from first principles; research is allowed, indeed, encouraged. Finding the best algorithm for the problem is a key skill in software engineering.

To compile and run the tests, just run the following in your exercise directory:

```
$ nim c -r test_difference_of_squares.nim
```

Note that, when trying to submit an exercise, make sure the solution is in the `$EXERCISM_WORKSPACE/nim/difference-of-squares`

directory.

You can find your Exercism workspace by running `exercism debug`

and looking for the line that starts with `Exercises Directory`

.

These guides should help you,

Problem 6 at Project Euler http://projecteuler.net/problem=6

It's possible to submit an incomplete solution so you can see how others have completed the exercise.

```
import unittest
import difference_of_squares
suite "Difference of Squares":
test "square of sum 1":
check squareOfSum(1) == 1
test "square of sum 5":
check squareOfSum(5) == 225
test "square of sum 100":
check squareOfSum(100) == 25_502_500
test "sum of squares 1":
check sumOfSquares(1) == 1
test "sum of squares 5":
check sumOfSquares(5) == 55
test "sum of squares 100":
check sumOfSquares(100) == 338_350
test "difference of squares 1":
check difference(1) == 0
test "difference of squares 5":
check difference(5) == 170
test "difference of squares 100":
check difference(100) == 25_164_150
```

```
import math
import sequtils, sugar
proc squareOfSum*(number: uint64): uint64 =
number^2*(number+1)^2 div 4.uint64
proc sumOfSquares*(number: uint64): uint64 =
number*(number+1)*(2*number + 1) div 6.uint64
proc difference*(number: uint): uint =
let poly = [3, 2, -3, -2, 0].map(x => x.uint)
result = poly[0]
for i in 1 ..< poly.len:
result = result*number + poly[i]
result = result div 12
```

The square of the sum for integers from 1 up to n is : (n*(n+1)/2)^2

The sum of squares for integers from 1 up to n is : n*(n+1)*(2*n+1)/6

Hence, the difference is : (3*n^4 + 2*n^3 - 3*n^2 - 2*n) / 12

I have used the Horner's rule to compute the value of P(n) = 3*n^4 + 2*n^3 - 3*n^2 - 2*n

Thus we compute only 4 multiplications and 3 additions, plus 1 division.

Level up your programming skills with 3,450 exercises across 52 languages, and insightful discussion with our volunteer team of welcoming mentors.
Exercism is
**100% free forever**.

## Community comments