Project Euler: problem 6

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 12 + 22 +…+ 102 = 385
The square of the sum of the first ten natural numbers is (1 + 2 +…+ 10)2 = 552 = 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 (\displaystyle\sum_{i=1}^{100} i)^2=(1+2+\cdots+100)^2=\\1^2+2^2+\cdots+100^2+2\cdot[(1\cdot2)+\cdots+(1\cdot100)+(2\cdot3)+\cdots+(2\cdot100)+\cdots+(99\cdot100)]

and the

Sum of Squares \displaystyle\sum_{i=1}^{100} i^2=1^2+2^2+\cdots+100^2

or, even better, directly the

Difference 2\cdot[(1\cdot2)+\cdots+(99\cdot100)]

All nice and clear, although I already knew that \displaystyle\sum_{i=1}^{N}i={(1+N)N \over 2}: 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 \displaystyle\sum_{i=1}^{N} i^2={N(N+1)(2N+1) \over 6}. 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 263-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.

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

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

for i in {100..2}
echo $((2*sq_diff))

Considering the 2\cdot[(1\cdot2)+\cdots+(99\cdot100)] term, it can be written in the form

2\cdot[1\cdot(2+3+\cdots+100)+2\cdot(3+4+\cdots+100)+\cdots+99\cdot100]=2 \cdot \displaystyle \sum_{i=1}^{N-1} \bigg( i \cdot \sum_{j=i+1}^{N}j \bigg)

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.