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...