Fortune Cookie Says

You will have a long and wealthy life.

Project Euler problems 6 - 10

I finally found some time to sit down and do problems 6 through 10 on Project Euler.

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

def euler6()
  (1..100).inject(0){|val,k| val += k} ** 2 -
  (1..100).inject(0){|val,k| val += k**2}
end

Problem 7: What is the 10001st prime number?

def euler7()
  myprime = Prime.new
  (1..10000).each{ myprime.next}
  myprime.next
end

Problem 8: Find the greatest product of five consecutive digits in the 1000-digit number.

The 1000 digit number is a string in my code.

def euler8(bigNum)
  len = bigNum.size
  stopAt = len - 5
  sliceStart = 0
  res = 0
  while sliceStart < stopAt do
      val = 1
      s = bigNum.slice(sliceStart, 5)
      s.each_char{|x| val *= x.to_i}
      res = val if res < val
      sliceStart += 1
  end
  res
end

Problem 9: There exists exactly one Pythagorean triplet for which a + b + c = 1000. Find the product abc.

def euler9()
  val = 0
  (1..500).each{ |a|
      (a..500).each{ |b|
          c = (a**2 + b**2)**0.5
          next unless c == c.to_i # continue unless c is an integer
          val = a + b + c
          return a * b * c if val == 1000
          break if val > 1000
      } 
  } 

end

Project 10: Find the sum of all the primes below two million.

This was the only really challenging problem in this set. I tried to use Ruby's Prime class in a loop for this. When ran for 50,000 iterations it would return in about 14 seconds. For 2,000,000 I eventually killed the process after 15 minutes. The algorithm used in the Prime class seems to fall down when used to generate large lists of prime numbers.

I did some searching and found that most people were using some type of number sieve to generate the list of prime numbers, see Wikipedia here and here. I found and shamelessly stole a Ruby implementation of the Sieve of Eratosthenes from Paul Callagher. I slightly modified Paul's implementation to make it a standalone function instead of a class method.

# problem 10, find the sum of all primes below 2,000,000.
# prime series up to this limit, using Sieve of Eratosthenes method
# http://en.wikipedia.org/wiki/Sieve_of_Eratosthenes
#
# from http://tardate.blogspot.com/2008/10/rolling-project-euler-on-ruby.html
def sieve_of_eratosthenes( maxVal )
  limit = Math.sqrt(maxVal)                        
  a = (2..maxVal).to_a                             
  n = 2                                            
  while (n < limit) do                             
      x = n*2
      begin                                        
          a[x-2]=2                                 
          x+=n                                     
      end until (x > maxVal )
      begin
          n+=1
      end until ( a[n-2] != 2 )
  end
  a.uniq!
end

def euler10()
  sieve_of_eratosthenes( 2_000_000 ).inject(0){|val, x| val += x }
end

This code returns in about 4 seconds.

Fortune Cookie Says

Good things are being said about you.

Project Euler

I recently found out about Project Euler which has a collection of math/programming problems to solve. I have started working through the problems using Ruby. I have decided on using Ruby in my current project, which I will do some posts on later, but I don't have any real experience using it, so this will give me something to work with while learning the language.

The first problem: Sum all integers less than 1,000 that are multiples of 3 or 5. This is my third version and I have it down to a single line.

(1..999).inject(0){|result, n|
   (0==n%3 or 0==n%5)? result + n : result}

The second problem: Sum all even numbers in the Fibonacci sequence that do not exceed 4,000,000. My first solution uses a recursive algorithm.

def euler2_rec(n1=1, n2=1)
  return 0 if n1 > 4000000
  fib = n1 + n2
  sum = euler2_rec(n2, fib)
  sum += fib if 0 == fib % 2
  return sum
end

Since this is tail recursive and any tail recursive algorithm can be converted to a loop. I decided to create a loop version.

def euler2_loop
n1 = 1 
n2 = 1
sum = 0
begin
    fib = n1 + n2
    sum += fib if 0 == fib % 2
    n1 = n2
    n2 = fib
end while fib < 4000000
return sum
end

The third problem: Find the largest prime factor of 600,851,475,143. For this I used Ruby's Prime class.

def euler3()
  num = 600851475143
  primes = Prime.new
  factor = 0
  while num > 1 do
     factor = primes.next
     num /= factor if 0 == num % factor
  end
  return factor
end

I had originally used num / 2 as my halting condition. But reading the comments after solving the problem I saw that others divided out the factors as they found them. This allows the loop to exit after the largest factor is found, and is rather obvious once you see it.

The fourth problem: Find the largest palindromic number that is made from the product of two 3-digit numbers.

def euler4()
 result = 0
 100.upto(999) { |i|
   i.upto(999) { |j|
     val = i * j
     result = val if result < val and
         val.to_s == val.to_s.reverse
  }}
 return result
end

The fifth problem: Find the smallest number that is evenly divisible by all numbers between 1 and 20.

The easy and obvious approach for this problem is to take each number and test it to see if it evenly divisible by the numbers 2 to 20, all integers being evenly divisible by 1. One can think of some optimization that can be applied to this approach. For example a number must end in a 0 to be evenly divisible by 10. Also any number that is evenly divisible by 20 is also divisible by 10, 5, 4, and 2. Also one can consider that all, non prime, numbers can be factored into prime numbers. So the problem can be reduced to working with a set of prime numbers.

However, I wasn't sure of the correct approach, and being too lazy to get off of the couch to crack open a dusty old math book, I opted for brute force and ignorance and wrote program to iteratively check all numbers. While that was chewing up my CPU in the background I searched for a better solution and found this blog post on the problem. The solution proposed in that post is to find the accumulated least common multiple (LCM) for the numbers 2 to 20. A bit more searching turned up this page which had sample code, in Ruby, which would calculate the LCM and greatest common factor (GCF). So a little bit of time later, and with my original code still running, I had this solution.

require "gcf_lcm.rb"
def euler5()
  lcm = calc_lcm(2,3, calc_gcf(2,3) )
  4.upto(20) { |n|
    lcm = calc_lcm(lcm, n, calc_gcf(lcm, n) ) }
   return lcm
end

This returns almost instantly, and with the correct answer. When looking through the comments on this problem I found a posting with a Ruby solution. It turns out there are library routines in Ruby for LCM and GCF and the solution can be turned into a one liner.

(2..20).inject(1){|res,n| res.lcm n}

Fortune Cookie Says

Tomorrow your friend or partner will tell you some exciting news.

Fortune Cookie Says

You will soon be crossing the great waters.

Project Backup Script

I am using trac and subversion on my current project. I wrote the following script to do a full backup of trac and subversion and burn the results to a CD.

#!/bin/bash

## Backup subversion and trac and burn the backups to a CD.
##

## applications
##
TRACADMIN=/usr/bin/trac-admin
SVNADMIN=/usr/bin/svnadmin
MKISOFS=/usr/bin/mkisofs
CDRECORD=/usr/bin/cdrecord
DATE=/bin/date

## directory and file paths
##
REPO=/opt/repo/tde
TRACPROJ=/opt/trac
BACKUPDIR=/home/steve/backup
TMPDIR=$$
CDDEVICE=/dev/cdrom
SVNDUMPFILE=$BACKUPDIR/$TMPDIR/temp/svn_dump.txt
DATEFILE=$BACKUPDIR/$TMPDIR/temp/backupdate.txt
LOGFILE=$BACKUPDIR/$TMPDIR/backup.log

if [[ $EUID -ne 0 ]]; then
 echo "This script must be run as root"
 exit 1
fi

## check for the directory structure and attempt to create if needed
##
if [[ ! -e $BACKUPDIR ]]; then
 if ! mkdir $BACKUPDIR; then
     exit 1;
 fi
fi

if [[ -e $BACKUPDIR/$TMPDIR ]]; then
 exit 1;  # temp dir already exists
else
 if ! mkdir $BACKUPDIR/$TMPDIR; then
     exit 1
 fi
fi

if ! mkdir $BACKUPDIR/$TMPDIR/iso; then
 echo "Failed to create $BACKUPDIR$TMPDIR/iso" >> $LOGFILE;
 exit 1;
fi

if ! mkdir $BACKUPDIR/$TMPDIR/temp; then
 echo "Failed to create $BACKUPDIR/$TMPDIR/temp" >> $LOGFILE;
 exit 1;
fi

## dump subversionto SVNDUMPFILE
##
echo "Dumping subversion" >>$LOGFILE
echo "" >>$LOGFILE
if ! $SVNADMIN dump $REPO > $SVNDUMPFILE 2>>$LOGFILE; then
 exit 1;
fi

## hot backup trac
##
echo "" >>$LOGFILE
echo "Performing hotcopy of trac" >> $LOGFILE
echo "" >>$LOGFILE
if ! $TRACADMIN $TRACPROJ hotcopy $BACKUPDIR/$TMPDIR/temp/trac \
         1>>$LOGFILE 2>>$LOGFILE; then
 exit 1;
fi

## create a file with the date time the backup was done
##
echo `$DATE` > $DATEFILE

## create iso file
## mkisofs does not seem to return a status value so we dont know if it
## actually succeeded.
##
echo "" >>$LOGFILE
echo "Making ISO file" >> $LOGFILE
echo "" >>$LOGFILE
$MKISOFS -fRrlJ -o $BACKUPDIR/$TMPDIR/iso/backup.iso \
     $BACKUPDIR/$TMPDIR/temp 1>>$LOGFILE 2>>$LOGFILE

## burn the iso file to a cd
## cdrecord does not seem to return a status value so we dont know if it
## actually succeeded.
##
echo "" >>$LOGFILE
echo "Burning the CD" >> $LOGFILE
echo "" >>$LOGFILE
$CDRECORD -eject speed=24 dev=$CDDEVICE $BACKUPDIR/$TMPDIR/iso/backup.iso \
         1>>$LOGFILE 2>>$LOGFILE
#if $CDRECORD speed=24 dev=$CDDEVICE $BACKUPDIR/$TMPDIR/iso/backup.iso \
#            1>>$LOGFILE 2>>$LOGFILE; then
#    exit 1;
#fi

## clean up if everything was OK
## since we don't know if mkisofs or cdrecord succeeded do not
## automatically delete the director.
##
#rm -rf $BACKUPDIR/$TMPDIR

The only thing in this script to make note of is the line TMPDIR=$$. The TMPDIR variable is will be the name of the temporary directory to backup to and this is set to the PID of the process which is returned by $$.

To automate the backup I run the script through cron. To setup the cron entry I ran the following commands as root.

[root@myhost]# export EDITOR=vi
[root@myhost]# crontab -e

This will bring up a vi editor with root's crontab file. I then added the following line and saved the file.

59 23 * * 5 /home/steve/bin/sp_backup.sh

The script will now be run every Friday at 11:59 PM. The only problems that I encountered with this script is that neither mkisofs or cdrecord seem to return the UNIX standard value of 0 for success and non-zero for failure. I was going to have the script delete all of the directories and files that were created. But because I can't determine if the script was successful I decided to leave the files in place and to manually ensure that the backup was successful.