euler.pl

#!/usr/bin/env perl -w

# Project Euler in Perl
# John Evans <john@jpevans.com>

use strict;
use POSIX;

# Euler #1
# Answer: 233168
#
# 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.

sub euler1
{
    my $n = 0;
    my $i;
    for ($i=1; $i<1000; $i++) {
        if (($i % 3 == 0) || ($i % 5 == 0)) {
            $n += $i;
        }
    }
    $n;
}


# Euler #2
# Answer: 4613732
#
# 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.

sub euler2
{
    my $n = 2;
    my $a = 1;
    my $b = 2;
    while (1) {
        my $c = $a + $b;
        if ($c > 4000000) {
            last;
        }
        if ($c % 2 == 0) {
            $n = $n + $c;
        }
        $a = $b;
        $b = $c;
    }
    $n;
}


# Euler #3
# Answer: 6857
#
# The prime factors of 13195 are 5, 7, 13 and 29.
#
# What is the largest prime factor of the number 600851475143 ?

sub is_prime
{
    my $n = $_[0];
    if ($n == 2) {
        return 1;
    }
    my $i;
    for ($i=2; $i <= POSIX::ceil(sqrt($n)); $i++) {
        if ($n % $i == 0) {
            return 0;
        }
    }
    return 1;
}


sub euler3
{
    my $target = 600851475143;
    my $i;

    for ($i=POSIX::ceil(sqrt($target)); $i > 2; $i--) {
        if ($target % $i == 0 && is_prime($i)) {
            return $i;
        }
    }
}


# Problem #4
# Answer: 906609
#
# 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.

sub is_palindromic_number
{
    my $n = $_[0];
    my $s = "$n";
    return $s eq reverse($s);
}

sub euler4
{
    my ($i, $j, $p);
    my $result = 0;

    for ($i=100; $i<1000; $i++) {
        for ($j=100; $j<1000; $j++) {
            $p = $i * $j;
            if ($p > $result && is_palindromic_number($p)) {
                $result = $p;
            }
        }
    }

    return $result;
}


# Problem #5
# Answer: 232792560
#
# 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?

sub divisible_by_all
{
    my ($d, $n, @ds, $result);
    $n = shift @_;
    @ds = @_;
    $result = 1;
    foreach $d (@ds) {
        if ($n % $d != 0) {
            $result = 0;
            last;
        }
    }
    $result;
}

sub euler5
{
    my $n = 2520;
    my @ds = (20, 19, 18, 17, 16, 15, 14, 13, 12, 11);
    for (;;) {
        if (divisible_by_all($n, @ds)) {
            return $n;
        }
        $n++;
    }
}


# Problem #6
# Answer: 25164150
#
# The sum of the squares of the first ten natural numbers is,
#     1² + 2² + ... + 10² = 385
# The square of the sum of the first ten natural numbers is,
#     (1 + 2 + ... + 10)² = 55² = 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.

sub euler6
{
    my ($i, $sum, $sum_squares);
    $sum = 0;
    $sum_squares = 0;
    for ($i=1; $i<=100; $i++) {
        $sum += $i;
        $sum_squares += ($i * $i);
    }
    return ($sum * $sum) - $sum_squares;
}


# Problem #7
# Answer: 104743
#
# 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?

# sub euler7 {
#     my @primes = (2);
#     my $i, $j;
#     for (;;) {
#         if ($#primes == 10001) {
#             return @primes[$#primes - 1];
#         }
#         my $next_prime = 0;
#         for ($i = @primes[$#primes - 1]; ;$i++) {
#             foreach $prime (@primes) {
#                 if ($i )
#             }
#
#         }
#     }
# }


sub main {
    my @EULERS = (
        \&euler1,
        \&euler2,
        \&euler3,
        \&euler4,
        \&euler5,
    );

    if (@ARGV) {
        my $arg;
        foreach $arg (@ARGV) {
            my $result = eval("euler$arg");
            print("$arg: $result\n")
        }
    } else {
        my $index;
        foreach $index (0..$#EULERS) {
            my $euler = $EULERS[$index];
            my $n = $index + 1;
            print("$n: " . &$euler() . "\n");
        }
    }
}

main();