# Riddle 6: Sum Square Difference

### [The Task](https://projecteuler.net/problem=6)

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

> ```undefined
1^2 + 2^2 + 3^3 + ... + 10^2 = 385
```

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

> ```undefined
(1 + 2 + 3 + ... + 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:

> ```undefined
3025 - 385 = 2840
```

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

---

There are three solutions to this task: 
- A straightforward one -> 14 lines
- A functional, "lispy" one -> 3 lines
- A mathematical one -> 2 lines.

---

### The straightfoward solution

This one is very simple, because we just do literally what is in the task description. We have three functions: ``sum_squared``, which sums up and squares the result, ``squares_sum``, which forms the square and then sums up, and ``task_6`` which combines it to deliver the solution.

```undefined
(de sum_squared (N)
   (let Sum 0
      (for I N
         (inc 'Sum I) )
   (* Sum Sum)) )

(de squares_sum (N)
   (let Sum 0
      (for I N
         (inc 'Sum (* I I)) )
   Sum ) )

(de task_6 (N)
   (-
      (sum_squared N)
      (squares_sum N)) )
```

---

### The functional solution

The code above smells a little bit like repetition and redundancy. Redundant tasks in ``sum_squared`` and ``squares_sum``:

- In both functions, we use a helper variable ``I`` to sum up from 0 to N.
- in both functions, we increment a variable ``Sum``.

Let's first try to improve the first point. Instead of ``for I N``, we could use a list, because we all know that PicoLisp has powerful list functions. With ``range``, we can create a list from 1 to ``N``.

```undefined
: (setq L (range 1 10))
-> (1 2 3 4 5 6 7 8 9 10)
```

Next, we can use ``apply`` to apply the ``+`` function to *all elements on the list*. 

```undefined
: (apply + L)
-> 55
```
This is equivalent to the first 4 lines of our ``sum_squared`` function above.

---

In the same way, we can use the ``sum`` function to apply the ``*`` function to *each element of a list* and return the numerical sum of the list elements. The syntax is ``(sum 'fun 'lst ...)``:

```undefined
: (sum * L L)
-> 385
```

This single line is equivalent to our ``squares_sum`` function.

--- 

In other words, the above code can be shortened down to:

```undefined
(de task_6 (N)
   (let (L (range 1 N)  S (apply + L))
      (- (* S S) (sum * L L)) ) )
```

Note: Depending on the usecase, you need to cosnider that the ``apply`` function requires a lot of stack space. If you have the latest PicoLisp version installed, you will get a "stack overflow" error message if the numbers get too large.

```undefined
: (task_6 100000)
-> 25000166664166650000


: (task_6 1000000)
!? (apply + L)
Stack overflow
```


---

### The mathematical approach

Now, the "lispy" solution already has many improvements, such as reducing redundancy and repetition. However, internally we still have a lot of looping and iteration going on, which causes some (potential) limitations on the applicable range - depending on the use case of course. So let's look for mathematical approaches to improve our solution further.

There is a famous story about young Gauss who allegedly finished the teacher's task to sum up all numbers from 1 to 100 within minutes. He did that with the so-called "Gaussian Sum Formula": 

![gauss-sum.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1642533886418/QVgG3-UfT.png)

Accordingly, the square of the sum can be expressed as ``((n^2 + n)/2 )^2)``.

---

In order to find the sum of squares, we can use the formula for [square pyramidal numbers](https://en.wikipedia.org/wiki/Square_pyramidal_number):


![pyramidnumber.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1642534229525/iq-ZohXhT.png)

---

Now we bring these two formulas together, extract ``n`` and re-group the factors a little bit to make it more pretty. With some easy calculations, you can form it to the following identity:


![identity.png](https://cdn.hashnode.com/res/hashnode/image/upload/v1642534659049/0aUPNDZBo.png)


In PicoLisp:

```undefined
(de task_6 (N)
   (/ ( * N (- (* N N) 1) (+ (* 3 N) 2)) 12) )
```

This solution don't needs any loops or iterations, which means that the computation time will stay almost constant.


---

You can find the source code of the examples here:
- [straightforward](https://gitlab.com/picolisp-blog/single-plage-scripts/-/blob/main/euler/Task_6_Square_Sum_Difference-straightforward.l)
- [functional](https://gitlab.com/picolisp-blog/single-plage-scripts/-/blob/main/euler/Task_6_Square_Sum_Difference-lispy.l)
- [mathematical](https://gitlab.com/picolisp-blog/single-plage-scripts/-/blob/main/euler/Task_6_Square_Sum_Difference-Mathematical.l)

---

### Sources

- https://software-lab.de/doc/index.html
- https://projecteuler.net/problem=6