Project Euler Problem 6 Solution

First posted on 16/10/2012

Question

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 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 in Java

// Problem 6:
// Find the difference between the sum of the squares of the first one hundred natural numbers and the square of the sum.

public class multiples {
	public static void main(String[] args) {
		long begin = System.currentTimeMillis();
	
		int sum_1 = 0, sum_2 = 0, sum = 0;
		int n = 100;
		
		// Sum of the first nth integer
		sum_1 = n*(n+1)/2;
		sum_1 *= sum_1;
		
		// Sum of nth squared integers
		sum_2 = (n * (n+1) * (2*n+1))/6;
		
		System.out.println(sum_1 - sum_2);
		
		long end = System.currentTimeMillis();
		System.out.println(end-begin + " ms");
	}

}

Answer: 25164150 (0 ms)

Footnotes

This was my original algorithm. Brute forced.

for(int i = 1; i <= 100; i++){
 prod = i*i;
 sum_1 += prod;
 
 before = i;
 after += before;
}

sum_2 = after*after;
sum = sum_2 - sum_1;

There was a quick solution for this by using Number Series we learned in elementary maths.

To find sum of the first nth integer,
foot1

To find sum of the squared nth integer,
foot2

Show Comments

Get the latest posts delivered right to your inbox.