Project Euler Problem 19

I've been solving these in order of ascending difficulty, but when sorting by problem number, I noticed that Problem 19 was the most difficult (according to the number of people who've solved it) within the first 20 problems. I was surprised because I thought this would be really easy, and it was. The code pasted below took me only 10 minutes to write, and was correct on the first try.

/*
 * Problem 19
 * 14 June 2002
 *
 * How many Sundays fell on the first of the month during the twentieth century
 * (1 Jan 1901 to 31 Dec 2000)?
 */

import org.joda.time.DateTime;

public class PE0019
{
 public static void main(String[] args)
 {
  int numberOfSundays = 0;
  int monthCounter = 0;
  
  DateTime startDate = new DateTime(1901, 1, 1, 0, 0, 0, 0);
  DateTime endDate = new DateTime(2000, 12, 31, 0, 0, 0, 0);
  
  DateTime currentDate = startDate;
  
  while (currentDate.getMillis() < endDate.getMillis())
  {
   currentDate = startDate.plusMonths(monthCounter++);
   if (currentDate.getDayOfWeek() == 7)
    numberOfSundays++;
  }
  
  System.out.println(numberOfSundays);
 }
}

Project Euler Problem 4

Rather than figuring out how to do looping and conditional statements in Mathematica, I just used Java for this one. I got the answer right on the first try, but did not try to optimize my code, so it's a bit clunky. The most difficult part of this problem was to do some string manipulation to determine whether the product was a palindromic number.

/*
 * Problem 4
 * 16 November 2001
 *
 * A palindromic number reads the same both ways. The largest palindrome made
 * from the product of two 2-digit numbers is 9009 = 91 × 99.
 *
 * Find the largest palindrome made from the product of two 3-digit numbers.
 */

public class PE0004
{
 public static void main(String[] args)
 {
  long largestPalindrome = 0;
  
  for (int i = 100; i < 1000; i++)
  {
   for (int j = 100; j < 1000; j++)
   {
    largestPalindrome = (isPalindrome(i, j) > largestPalindrome) ? i * j : largestPalindrome;
   }
  }
  
  System.out.println(largestPalindrome);
 }

 private static long isPalindrome(int i, int j)
 {
  boolean isAPalindrome = false;
  String potentialPalindrome = i * j + "";
  
  int length = potentialPalindrome.length();
  
  for (int k = 0; k < length / 2; k++)
  {
   if (potentialPalindrome.charAt(k) == potentialPalindrome.charAt(length - k - 1))
   {
    isAPalindrome = true;
   }
   else
   {
    isAPalindrome = false;
    return 0l;
   }
  }
  
  if (isAPalindrome)
  {
   return i * j;
  }
  
  return 0l;
 }
}

Project Euler Problem 3

At this point, it's only a matter of figuring out which function to use.

Problem 3
02 November 2001

The prime factors of 13195 are 5, 7, 13 and 29.

What is the largest prime factor of the number 600851475143 ?

FactorInteger[13195]

{{5, 1}, {7, 1}, {13, 1}, {29, 1}}

Max[FactorInteger[600851475143]]

6857

Project Euler Problem 7

Using Mathematica, this one was way too easy.

Problem 7
28 December 2001
By listing the first six prime numbers : 
  2, 3, 5, 7, 11, and 13, we can see that the 6^(th) prime is 13.
What is the 10001^(st) prime number?

In[1]:= Prime[6]

Out[1]= 13

In[2]:= Prime[10001]

Out[2]= 104743

I think the point of these earlier ones is that you need to be able to easily come up with building blocks for later problems. If that's the case, I won't feel robbed of having written an algorithm to do this.

Project Euler Problem 20

n! means n × (n − 1) × ... × 3 × 2 × 1

Find the sum of the digits in the number 100!

Since it had been a little while since my last Project Euler post, I decided I would do an easy problem. Even though it was further down the list (there were other easier ones than this), I thought I could quickly come up with a solution in Java. That's where I was wrong.

Using the primitive data types in Java, the precision needed to compute the values for 100! did not exist. I experimented with using the BigInteger class, but the code was clunky. I have been considering doing these with a more mathematically based language, and made the leap to Mathematica tonight. At $2500 per license, it wouldn't be possible for me to use it, but fortunately I downloaded a version using a student license before I graduated from CU.

I am completely unfamiliar with using this software, and since I couldn't find a good function for summing the digits of a number, I did it manually. I'm sure there are more efficient ways of calculating the answer, but since this was my first Mathematica program, I'm ok with getting the answer, which was right on the first try.

In[1]:= 100!

Out[1]= 93326215443944152681699238856266700490715968264381621468592963\
8952175999932299156089414639761565182862536979208272237582511852109168\
64000000000000000000000000

In[2]:= 
9 + 3 + 3 + 2 + 6 + 2 + 1 + 5 + 4 + 4 + 3 + 9 + 4 + 4 + 1 + 5 + 2 + 6 \
+ 8 + 1 + 6 + 9 + 9 + 2 + 3 + 8 + 8 + 5 + 6 + 2 + 6 + 6 + 7 + 4 + 9 + \
7 + 1 + 5 + 9 + 6 + 8 + 2 + 6 + 4 + 3 + 8 + 1 + 6 + 2 + 1 + 4 + 6 + 8 \
+ 5 + 9 + 2 + 9 + 6 + 3 + 8 + 9 + 5 + 2 + 1 + 7 + 5 + 9 + 9 + 9 + 9 + \
3 + 2 + 2 + 9 + 9 + 1 + 5 + 6 + 8 + 9 + 4 + 1 + 4 + 6 + 3 + 9 + 7 + 6 \
+ 1 + 5 + 6 + 5 + 1 + 8 + 2 + 8 + 6 + 2 + 5 + 3 + 6 + 9 + 7 + 9 + 2 + \
8 + 2 + 7 + 2 + 2 + 3 + 7 + 5 + 8 + 2 + 5 + 1 + 1 + 8 + 5 + 2 + 1 + 9 \
+ 1 + 6 + 8 + 6 + 4

Out[2]= 648

Project Euler Problem 5

I'd like to post two solutions to this problem. The problem listed below took 2 hours and 20 minutes to run on my antiquated machine. Project Euler says optimized solutions take less than a minute on a modern machine. I can already see ways to optimize my solution, even though I got this one right on the first try.

/*
 * 2520 is the smallest number that can be divided by each of the numbers from
 * 1 to 10 without any remainder.
 *
 * What is the smallest number that is evenly divisible by all of the numbers
 * from 1 to 20?
 */

public class PE0005
{
 public static void main(String[] args)
 {
  long currentNumber = 0;
  boolean foundAnswer = false;

  while (!foundAnswer)
   foundAnswer = checkDivisibility(++currentNumber) ? true : false;
  
  System.out.println(currentNumber);
 }
 
 private static boolean checkDivisibility(long currentNumber)
 {
  for (int i = 2; i <= 20; i++)
   if (currentNumber % i != 0)
    return false;
  
  return true;
 }
}

Project Euler Problem 6

I didn't get this on the first try because I initially tried to use i^2 and sum^2 to perform the squares, and rashly submitted my answer without stepping through using a debugger first.

After I was denied on my first attempt, I replaced i^2 with i*i and sum^2 with sum*sum. I'm probably going to have to start using some sort of numerical package if I continue to program these in Java. Octave (the language I used to do my Numerical Computation assignments at CU) was not listed in the preferred language section of the profile, but since I only need to submit answers for these, I may switch to using Octave soon.

These have been way too easy so far. I'm looking forward to when they get harder.

Solution for Problem 6 below:

/*
 * 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) = 55^(2) = 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.
 *
 */

public class PE0006
{
 public static void main(String[] args)
 {
  int sumOfTheSquares = 0;
  int sum = 0;
  
  for (int i = 1; i <= 100; i++)
  {
   sumOfTheSquares += i * i;
   sum += i;
  }
  
  System.out.println(sum * sum - sumOfTheSquares);
 }
}

On a different note, my Hibernate book is at the Loveland post office and should be delivered soon. I'll probably take a break from Project Euler and make posts related to the things I learn in Hibernate. I know the basics, and can get by with what I know for work, but I'm really interested in learning the more arcane aspects of Hibernate...

Project Euler Problem 2

Woohoo! I was able to get the second problem right on the first try as well.

/* 
 * Each new term in the Fibonacci sequence is generated by adding the previous
 * two terms. By starting with 1 and 2, the first 10 terms will be:
 *
 * 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, ...
 *
 * Find the sum of all the even-valued terms in the sequence which do not
 * exceed four million.
 */

public class PE0002
{
 public static void main(String[] args)
 {
  long[] fibonacciSequence = createFibonacciSequence();
  long sum = 0;
  
  for (Long currentNumberInSequence : fibonacciSequence)
   if (isEven(currentNumberInSequence))
    sum += currentNumberInSequence;
  
  System.out.println(sum);
 }

 private static long[] createFibonacciSequence()
 {
  long[] fibonacciSequence = new long[33]; // originally set to 100000
  
  fibonacciSequence[0] = 1l;
  fibonacciSequence[1] = 2l;

  int index = 2;
  long currentNumberInSequence = 2l;
  
  while (currentNumberInSequence <= 4000000)
  {
   fibonacciSequence[index] = fibonacciSequence[index - 1] + fibonacciSequence[index - 2];
   currentNumberInSequence = fibonacciSequence[index];
   index++;
  }
  
  return fibonacciSequence;
 }

 private static boolean isEven(long number)
 {
  return number % 2 == 0;
 }
}

Project Euler Problem 1

A colleague of mine (Steve) let me know about a web site known as Project Euler. I signed up today and took a quick crack at problem 1. I knew I could optimize this to iterate through multiples of 3 and 5 instead of iterating through all numbers and checking if each was a multiple of 3 or 5, but I wanted to quickly get an answer so I took the brute-force route, which I won't do in the future.

My solution, which was correct on the first try, is listed below:

/*
* Problem 1
* 05 October 2001
*
* If we list all the natural numbers below 10 that are multiples of 3 or 5, we
* get 3, 5, 6 and 9. The sum of these multiples is 23.
*
* Find the sum of all the multiples of 3 or 5 below 1000.
*
*/

public class PE0001
{
  public static void main(String[] args)
  {
      long sum = 0;
      for (int i = 0; i < 1000; i++)
          if (isMultipleOf3Or5(i))
              sum += i;
   
      System.out.println(sum);
  }

  private static boolean isMultipleOf3Or5(int i)
  {
      if (i % 3 == 0 || i % 5 == 0)
          return true;
      return false;
  }
}