Problem 9

A Pythagorean triplet is a set of three natural numbers, a b c, for which,

a² + b² = c²

For example, 3² + 4² = 9 + 16 = 25 = 5².

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

Solution

exit = false

for a in 1..999 do

    for b in a..999 do

        c = 1000 – a – b

        if c < b  then break end

         if a**2 + b**2 == c**2

            puts a*b*c

            exit = true

            break

         end

    end

    if exit then break end

end

Discussion

Anybody know the proper way to exit an IronRuby program?  Leave a comment, find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

Problem 8

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

73167176531330624919225119674426574742355349194934
96983520312774506326239578318016984801869478851843
85861560789112949495459501737958331952853208805511
12540698747158523863050715693290963295227443043557
66896648950445244523161731856403098711121722383113
62229893423380308135336276614282806444486645238749
30358907296290491560440772390713810515859307960866
70172427121883998797908792274921901699720888093776
65727333001053367881220235421809751254540594752243
52584907711670556013604839586446706324415722155397
53697817977846174064955149290862569321978468622482
83972241375657056057490261407972968652414535100474
82166370484403199890008895243450658541227588666881
16427171479924442928230863465674813919123162824586
17866458359124566529476545682848912883142607690042
24219022671055626321111109370544217506941658960408
07198403850962455444362981230987879927244284909188
84580156166097919133875499200524063689912560717606
05886116467109405077541002256983155200055935729725
71636269561882670428252483600823257530420752963450

Solution

digits = "73167176531330624919225119674426574742355349194934

96983520312774506326239578318016984801869478851843

85861560789112949495459501737958331952853208805511

12540698747158523863050715693290963295227443043557

66896648950445244523161731856403098711121722383113

62229893423380308135336276614282806444486645238749

30358907296290491560440772390713810515859307960866

70172427121883998797908792274921901699720888093776

65727333001053367881220235421809751254540594752243

52584907711670556013604839586446706324415722155397

53697817977846174064955149290862569321978468622482

83972241375657056057490261407972968652414535100474

82166370484403199890008895243450658541227588666881

16427171479924442928230863465674813919123162824586

17866458359124566529476545682848912883142607690042

24219022671055626321111109370544217506941658960408

07198403850962455444362981230987879927244284909188

84580156166097919133875499200524063689912560717606

05886116467109405077541002256983155200055935729725

71636269561882670428252483600823257530420752963450"

#remove the line breaks again

digits = digits.delete("\r\n");

answer = 0

for i in 0..digits.length – 5 do

        product = Integer(digits[i]) * Integer(digits[i+1]) * Integer(digits[i+2]) * Integer(digits[i+3]) * Integer(digits[i+4])

        if answer < product

                answer = product

        end

end

puts answer

Discussion

Here I used delete to get rid of the line breaks.  Maybe instead of Integer I should have tried the “-‘0’” method described yesterday.

If you have any questions, leave a comment, find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

Problem 7

By listing the first six prime numbers: 2, 3, 5, 7, 11, and 13, we can see that the 6th prime is 13.

What is the 10001st prime number?

Solution

#By listing the first six prime numbers:

#2, 3, 5, 7, 11, and 13, we can see that

#the 6th prime is 13.

#What is the 10001st prime number?

primes = [2,3]

while primes.length < 10001 do

    candidate = primes[primes.length – 1] + 2;

    isPrime = false

    while !isPrime do

        isPrime = true

        for prime in primes

            if candidate % prime == 0 then

                isPrime = false

                break

            end

        end

        if !isPrime then

            candidate += 2

        else

            primes.push(candidate)

        end

    end

end

puts primes[primes.length–1]

Discussion

This is pretty much a straight port of the C# solution.  It turns out to be about an order of magnitude slower than the C# version (IronRuby ~11 seconds, C# ~ 1 second).  It still comes up with the correct answer, and it’s well within the 1 minute rule.

If you have any questions, leave a comment, find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

Problem 5

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 positive number that is evenly divisible by all of the numbers from 1 to 20?

Solution

# 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 positive number

# that is evenly divisible by all of the

# numbers from 1 to 20?

#I had to shorten this to fit on the blog

#correctly so

#r = result

#e = element

answer = [16,9,5,7,11,13,17,19].inject(1) {|r, e| r * e }

puts answer

Discussion

Well, that was easy.  I really enjoy inject style methods for operating on arrays..

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

Problem 4

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.

Solution

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

# placeholder

answer = 0;

#loop through each 3-digit number

for i in 100..999 do

    for j in i..999 do

        product = i*j

        # the palindrome test is simple here

        # since we are using the same technique

        # as the F# and C# functions

        if product.to_s().reverse == product.to_s() &&

            answer < product

                answer = product

        end

    end

end

puts answer

Discussion

I have to admit, Ruby makes this code pretty simple.

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

Problem 3

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

What is the largest prime factor of the number 600851475143 ?

Solution

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

#What is the largest prime factor of the number 600851475143?

def PrimeFactor(number)

    isPrime = true;

    factors = Array.new

    factorCandidate = Math.sqrt(number).floor

    while factorCandidate > 1 do

        if number % factorCandidate == 0  then

            isPrime = false;

            #kinda like the ‘push’ syntax here

            PrimeFactor(factorCandidate).each {|factor| factors << factor }

            PrimeFactor(number / factorCandidate).each {|factor| factors << factor }

        end

        factorCandidate -= 1

    end

    if isPrime then

        factors.Add(number)

    end

    factors

end

factors = PrimeFactor(600851475143)

puts factors.max

Discussion

Even though I copied and pasted my C# solution here it still took me a while to iron out the kinks.  There are some things I really enjoy about the syntax so far, but I still haven’t discovered the virtue of dynamic typing.  Maybe I will as time passes.

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

Problem 2

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, …

By considering the terms in the Fibonacci sequence whose values do not exceed four million, find the sum of the even-valued terms.

Solution

#By considering the terms in the Fibonacci sequence

#whose values do not exceed four million, find the

#sum of the even valued terms.

# this uses the same technique

# as the c# implementation

# I find this initialization

# syntax interesting

answer = 0

fib0, fib1, fib2 = 1, 1, 2;

while fib2 < 4000000

    answer += fib2

    #odd + even = odd

    fib0 = fib1 + fib2;

    #odd + even = odd

    fib1 = fib0 + fib2;

    #odd + odd = even

    fib2 = fib0 + fib1;

end

puts answer

Discussion

This is obviously a port of the C# solution.  The one piece I find interesting is

fib0, fib1, fib2 = 1,1,2;

Seems to be equivalent to

fib0 = 1, fib1 = 1, fib2 = 2;

For cutting and pasting large lists, the first option might be more attractive?  Why not use an array in that case?  I suppose I’ll learn more as I continue down the path.

If you have questions, leave a comment or please find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).

Problem 1

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.

Solution

# Add all the natural numbers below one

# thousand that are multiples of 3 or 5.

# this is interesting

# I wasn’t sure how to create the arrays

# with a step so I just rejected the ones

# I didn’t want.  For small numbers this

# should work fine

threes = (0…1000).reject { |i| i % 3 != 0 }

fives = (0…1000).reject { |i| i % 5 != 0 }

fifteens = (0…1000).reject { |i| i % 15 != 0 }

answer = 0

threes.each { |i| answer += i }

fives.each { |i| answer += i }

fifteens.each { |i| answer -= i }

puts answer

Discussion

Remember, Ruby is brand new to me.  I wasn’t really sure how to create an array with a step so I used the “reject” feature.  It felt pretty natural.

If you have questions, leave a comment or find me on Twitter (@azzlsoft) or email (rich@azzlsoft.com).