Tina Orooji

http://projecteuler.net/index.php?section=problems&id=1

I mentioned Project Euler to some of my co-workers and one of them, Daniel, is hooked. He came up with a better solution for Problem 1 than I had, but it was still an O(n) algorithm. We talked about it a little and our discussion lead to this constant time solution. Yay for teamwork!

	/* Project Euler - Problem 1 (http://projecteuler.net/index.php?section=problems&id=1)
	 *
	 * Using basic summations, get the sums of all multiples of 3, 5 and 3*5.  Add the
	 * summations for 3 and 5, then subtract the summation for 15.
	 */
	public static void p1(){
		double a = 3, b = 5, n = 999;
		double sum;

		sum = (a*summation(Math.floor(n/a))) + (b*summation(Math.floor(n/b))) - (a*b*summation(Math.floor(n/(a*b))));

		System.out.println((int)sum);
	}

	/* Basic summation function.  Returns the sum from 1 to n */
	public static double summation(double n){
		return n*(n+1)/2;
	}

http://projecteuler.net/index.php?section=problems&id=9

	/* Project Euler - Problem 9 (http://projecteuler.net/index.php?section=problems&id=9)
	 *
	 * Pretty simple brute force method.
	 */
	public static void p9(){
		double a = 0, b = 0, c = 0;

		for(a=0; a<1000; a++){
			for(b=a+1; b<1000; b++){
				c = Math.sqrt(Math.pow(a, 2) + Math.pow(b,2));
				if(b<c && a+b+c == 1000) break;
			}
			if(b<c && a+b+c == 1000) break;
		}

		System.out.println((int)(a*b*c));
	}

Note: After writing this I saw a mathematical solution on the forum. It utilizes stuff I vaguely remember so I’ll have to refresh my Geometry skills and redo this one soon )

http://projecteuler.net/index.php?section=problems&id=5

I’ll be honest, I solved this one on paper first and then figured out how to do it programatically. I don’t mean that I brainstormed a solution for a simpler case and then came up with an algorithm to get a solution for this problem… I mean I did the whole thing on paper and then once I had an answer I figured out how to write the program. Is that cheating? lol

Anyway, my first thought was that I may be able to find a subset of numbers from 1 to 20 whose product will be the solution.  For example, for the simpler solution of 1 to 10, 1*5*7*8*9 yields the solution.  (The 1 is included for completeness…  you’ll see.)  Eventually I realized that it wasn’t those actual values that caused their product to be the solution…  it was the prime factorization of those values.  Take the prime factorization for each number from 1 to 10:
1 = 1^1
2 = 1^1 * 2^1
3 = 1^1 * 3^1
4 = 1^1 * 2^2
5 = 1^1 * 5^1
6 = 1^1 * 2^1 * 3^1
7 = 1^1 * 7^1
8 = 1^1 * 2^3
9 = 1^1 * 3^3
10 = 1^1 * 2^1 * 5^1

The special thing about the values 5, 7, 8 and 9 is that the degrees for each prime number in their factorization are maximums of all other degrees for that prime. The highest degree of 1 is 1, the highest degree of 2 is 3, of 3 is 3, of 5 is 1, and of 7 is 1.

I then went through and figured out the prime factorization for 11 to 20:
11 = 1^1 * 11^1
12 = 1^1 * 2^2 * 3^1
13 = 1^1 * 13^1
14 = 1^1 * 2^1 * 7^1
15 = 1^1 * 3^1 * 5^1
16 = 1^1 * 2^4
17 = 1^1 * 17^1
18 = 1^1 * 2^1 * 9^1
19 = 1^1 * 19^1
20 = 1^1 * 2^2 * 5^1

Following the logic from before, my new set of highest degrees is:
1 – 1
2 – 4
3 – 2
5 – 1
7 – 1
11 – 1
13 – 1
17 – 1
19 – 1

So, this means that 1, 16, 9, 5, 7, 11, 13, 17 and 19 are the numbers that yield the maximum degree for each prime. Multiply them together, and you get the answer.

After I wrote a program to do what I’d done manually, I realized that it would be a lot cleaner to just loop through each number, check the factorization and see if one of the degrees produced is more than a previous degree.

I was a little concerned about the correctness because I need to make sure that if 1 is the highest degree for 5, the 5^1 from 5 is used… not, say, from 20. If I do somehow use the 5^1 from the 20, I want to make sure I don’t also use the 2^2 from 20, since another number had a higher degree for 2. I did a few test causes and I’m fairly confident that this won’t happen since I’m checking each prime individually.

	/* Project Euler - Problem 5 (http://projecteuler.net/index.php?section=problems&id=5)
	 *
	 * Finds the highest degree for each prime number in the prime factorization of
	 * all numbers from 1 to 20.  Each prime is then raised to it's highest degree and
	 * multiplied.
	 */
	public static void p5(){
		/* All primes from 1 to 20 */
		int degrees[][] = {{2,0}, {3,0}, {5,0}, {7,0}, {11,0}, {13,0}, {17,0}, {19,0}};
		int n=1;

		/* For each number, get the prime factorization.  If the degree is
		 * greater than the current degree for any given prime, replace it.
		 */
		for(int i=1; i<=20; i++)
			for(int j=0; j<degrees.length; j++)
				if(getDegree(i, degrees[j][0]) > degrees[j][1])
					degrees[j][1] = getDegree(i,degrees[j][0]);

		/* Get the product of each prime raised to it's highest degree */
		for(int i=0; i<degrees.length; i++)
			n = n * (int)Math.pow(degrees[i][0], degrees[i][1]);

		System.out.println(n);
	}

	public static int getDegree(int num, int prime){
		int count = 0;

		while(num % prime == 0){
			count++;
			num = num/prime;
		}

		return count;
	}

Note: After I wrote this I checked the forum on http://projecteuler.net and it looks like others solved it similarly, but without quite as much running around in circles )  Oops!

http://projecteuler.net/index.php?section=problems&id=4

	/* Project Euler - Problem 4 (http://projecteuler.net/index.php?section=problems&id=4)
	 *
	 * I was able to reduce some of the iterations by setting up the loops to not repeat
	 * computations (ie, don't do 998 x 912 and 912 * 998), but this is basically a
	 * brute force solution.
	 */
	public static void p4(){
		int pal = 0;

		for(int i=1; i<=999; i++)
			for(int j=1; j<=i; j++)
				if(i*j>pal && isPalindrome(Integer.toString(i*j)))
					pal = i*j;

		System.out.println(pal);
	}

	public static boolean isPalindrome(String str){
		int start = 0;
		int end = str.length() - 1;

		while(start < end){
			if(str.charAt(start) == str.charAt(end)){
				start++;
				end--;
			}
			else return false;
		}

		return true;
	}

http://projecteuler.net/index.php?section=problems&id=2

	/* Project Euler - Problem 2 (http://projecteuler.net/index.php?section=problems&id=2)
	 *
	 * I did realize that every 3rd Fibonacci number is even, but I haven't quite come
	 * up with a way to utilize that knowledge to simplify the loop.  I'll keep thinking
	 * about it and see if I come up with something better.
	 */
	public static void p2(){
		int sum = 0;
		int fib1 = 1;
		int fib2 = 1;
		int temp;

		do{
			temp = fib1 + fib2;
			fib1 = fib2;
			fib2 = temp;

			if(fib2 % 2 == 0) sum = sum+fib2;
		} while(fib2<4000000);

		System.out.println(sum);
	}

http://projecteuler.net/index.php?section=problems&id=1

	/* Project Euler - Problem 1 (http://projecteuler.net/index.php?section=problems&id=1)
	 *
	 * This problem is pretty straightforward, however, rather than going the brute-force
	 * route and checking each number from 1 to 999 to see if 3 or 5 is a divsor,
	 * I realized that I can break the numbers up in to groups of 15 (3*5) and find a
	 * pattern within the group.  It is still an O(n) runtime, but with some tweaking I should be able
	 * to get rid of the inner loop.
	 */
	public static void p1(){
		int n = 0;
		int sum = 0;
		int nums[] = {3, 2, 1, 3, 1, 2, 3}; /* Distances between 3, 5, 6, 9, 10, 12, 15 */

		do {
			for(int i=0;i<nums.length;i++){
				n=n+nums[i];
				if(n<1000) sum=sum+n;
				else break;
			}
		} while(n<1000);

		System.out.println(sum);
	}