Project Euler/6

The problem: https://projecteuler.net/problem=6

The solution: https://git.charlesreid1.com/cs/euler/src/master/006/Problem006.java

Project Euler Problem 6

The sum of the squares of the first 10 integers is 385.

The square of the sum of the first 10 integers is 3025.

Their difference is 3025 - 385 = 2640.

Find this for the first 100 integers.

Project Euler Link: https://projecteuler.net/problem=6

Link to solution, git.charlesreid1.com: https://git.charlesreid1.com/cs/euler/src/master/Problem006.java

Principle: this utilizes two summations that are useful to know off the top of your head. If you do, it makes this an O(1) problem. If not, it makes it an O(N) problem.

The two summations are:

$\sum _{i=1}^{n}i={\dfrac {n(n+1)}{2}}$

and

$\sum _{i=1}^{n}i^{2}={\dfrac {n(n+1)(2n+1)}{6}}$

Going a bit further, these two formulas can be combined to get an expression for the difference:

$\left(\sum _{i=1}^{n}i\right)^{2}-\sum _{i=1}^{n}\left(i^{2}\right)=\left({\frac {n(n+1)}{2}}\right)^{2}-\left({\dfrac {n(n+1)(2n+1)}{6}}\right)$

Now this can be written as a single fraction by getting a common denominator of 24, which yields:

${\dfrac {2x(x+1)(3x^{2}-x-2)}{24}}$

This gives a final expression for the difference as:

${\dfrac {x(x+1)(x-1)(3x+2)}{12}}$

Code Implementations

The implementations of the above formulas in Java:

	/** Formula for the sum of the square of integers up to N. */
	public static int sum_of_squares(int n) { 
		int result = (n*(n+1)*(2*n+1))/6;
		return result;
	}

	/** Formula for the sum of the integers up to N, squared. */
	public static int square_of_sum(int n) { 
		int result = (n*(n+1))/2;
		result *= result;
		return result;
	}

The generalization

This exercise links in with the pythagorean theorem, the binomial theorem, and the misconception that many students in algebra have about the rules for distributing exponents.