Sum square difference
Problem 006: 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 = 552 = 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:
>$.@ ^ p01< ^ p01+1g01 < 0
> v
|!:\<|p01-1:g01<$$_v#!:g+6/+:5\%+:5:g01 :< p01"c"+<_v#!p01:-1g01<p01:g0<
\ ^< >` > #v_v
> v v-g+6/+:5\%+:5:g01< >00g ^
##########> ^
########## >010g:5:+%\5:+/6+pv
##########
########## ^ < <
##########
##########
##########
##########
##########
##########
Explanation:
My solution here is far more complex than necessary, mostly because I thought the temporary numbers would get too big for int32 to handle (especially sum(1,100)^2). Later I found out I could just calculate the sum of the squares and the square of the sum and subtract them ...
But I like my solution so I'll leave it here. While I calculate the the second value (using the distributive property), I subtract in every step as much parts of the first value (the single elements of the addition) as I can (without going negative).
That way my temporary values never greatly exceed the final result.
| Interpreter steps: | 18 897 151 |
| Execution time (BefunExec): | 7.35s (2.57 MHz) |
| Program size: | 72 x 16 (fully conform befunge-93) |
| Solution: | 25164150 |
| Solved at: | 2014-09-11 |