Problem 6 from Project Euler list is so easy, it only requires pen & paper (a pocket calculator would help, maybe) and basic knowledge about series to solve, without writing a single line of code:

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 tvoihe 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.

The quick solution leaves room for a few coding experiments, though: Python (because I am learning and need to practice!) and bash scripting (because… bash scripting). A quite simple script (in any language you like!) would quickly process the small group of numbers (1 to N = 100) to compute the

**Square of Sums**

and the

**Sum of Squares**

or, even better, directly the

**Difference**

All nice and clear, although I already knew that : square it and you’re done. A quick web search eventually brought me on the Wikipedia page listing results for some of the most common series, where I got the solution for . Game, set, match: whatever N is, evaluation of these two simple terms yields the result, no further “optimization” required (or possible), no need to compute long list of terms, in a handful of *teeny-weenyseconds*.

The only risk would be an overflow when N becomes big enough (that is beyond the goal of Problem 6 and into the “Let’s have some fun with numbers” area): Python doesn’t really care about big numbers, bash is a bit more picky (remember 2^{63}-1). Enough with ramblings, let’s list things in order.

**PYTHON**: First, the usual “*brute force*” solution: I was putting together a full script when I came across list comprehensions and built-in functions, that totally made my day. The script soon became a nice one-liner:

sum(range(101))**2 - sum([x**2 for x in range(101)])

It takes about 0.00018s on my PC and scales in direct proportion with range width.

Instead, using the formulas shown above to evaluate the results makes the execution time constant, regardless of `N`

(fluctuations are mostly due to other system loads “interfering” with the calculations). For N=100 the execution time is on average 1/3 compared to the *brute force* version.

That’s it: result is **25164150** and Problem 6 is solved.

**BASH**: The full shell script isn’t bad at all:

part_sum=0 sq_diff=0 for i in {100..2} do part_sum=$((part_sum+i)) sq_diff=$((sq_diff+(part_sum*(i-1)))) done echo $((2*sq_diff))

Considering the term, it can be written in the form

Starting from the last term of the sum and going backwards, the script evaluates the terms 100, (100+99), (100+99+98), … , just by adding the last number in the sequence to the partial sum (`part_sum`

). A mere rearrangement of the terms increases a lot computational efficiency and makes the run quite fast: approximate run times are 0.005 s for N=100, 0.018 s for N=1000, 0.139 s for N=10000 and 1.144 s for N=100000.

A *one-liner* similar to the Python one is not feasible: of course `bash`

has its builtins (see `man bash`

“SHELL BUILTIN COMMANDS” section) such as `cd`

, `time`

or `export`

, but they are meant for very different purposes and absolutely useless for my current task.

Finally, formulas for finite sums can be used straight from the command line: Square of Sums `echo $(((((1+N)*N)/2)**2))`

runs pretty fast even for N=70000 (and overflows for N = 77935), so that `time`

always outputs a 0.000 s measurement. Honestly, I didn’t bother looking at *nanoseconds* to get the real execution time!

Same story for Sum of Squares, that overflows for N ≅ 1664510, far beyond the limits of my patience 😉 .

And here’s the **paper**. See you soon for next… “something” with numbers, Python, bash and more paper!

## 1 Comment

I commenti sono chiusi.