Project Euler/6

Project Euler Problem 6

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

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

Their difference is y-x.

Find this for the first 100 integers.

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

Link to solution, git.charlesreid1.com: https://charlesreid1.com:3000/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} $

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;
	}