Sum square difference


Fork me on GitHub
2014-09-11

Problem 006: Sum square difference

Description:

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:
"d"10p000p>10g:00g+00p1-:#v_$010p>"c"10g::1+:*\:5:+%\5:+/6+p`#v_       v
>$.@      ^            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
##########
##########     ^                         < <
##########
##########
##########
##########
##########
##########
Start
??
Pause
Reset
Output:
Stack:   (0)

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



made with vanilla PHP and MySQL, no frameworks, no bootstrap, no unnecessary* javascript