Project Euler (a series of challenging mathematical/computer programming problems)

[BioGeek]

Hi all,

I just wanted to point out a site I discovered recently, and which has been very helpful in sharping my programming skills. It's called Project Euler and consists of "a series of challenging mathematical/computer programming problems that will require more than just mathematical insights to solve. Although mathematics will help you arrive at elegant and efficient methods, the use of a computer and programming skills will be required to solve most problems."

Some sample problems (only after you have created an account can you see how difficult the problem is rated, and the number of users that have solved each problem):

What is the smallest number divisible by each of the numbers 1 to 20?

How many Sundays fell on the 1st of the month during the twentieth century?

How many distinct terms are in the sequence generated by a^b for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

Find the first four consecutive integers to have four distinct primes factors.

And so on and on (more than 100 such problems are already posted on the site).

A forum is available to discuss strategies used in solving the problems (and you can often find some wonderful elegant or creative code there, in many different programming languages), however access is only granted AFTER you have solved a problem.

After having solved some problems, It seems to me that the most current languages to solve the problems in are either C/C++ or Python, so... do I sense an opportunity here for the Perl community to show off their skills? ;-)

Incidentally, I hope that this thread can become the place for people who get really stuck while trying to solve a problem, where they can get hints and pointers in the right direction (without revealing the solution of course).

Happy fun coding!

[GrandFather]

Nice heads up about an interesting site. The easy problems are pretty quick to solve! Some of the harder ones I suspect I don't even want to think about.

I've been ticking the Perl box for all so far, except problem 5 - most people seem to use pencil and paper for that one :)

[negation]

That sounds like a really great project. I will definitely give it a look during this weekend. And it sure sounds like a nice way to sharpen up my programming skills a bit.

[mpolo]

Well, I've wasted a lot of time with that site now...

I've solved 18 thus far, and have credited perl for all but #5. A very useful resource for a lot of these is one of merlyn's columns, which calculates the primes pretty quickly. And Math::BigInt is your friend for many of these as well.

Currently, #48 has me a little stumped, as it managed to "inf" out BigInt. All the sums from 18 to 143 have the same last 10 digits, but the site claims that these are not the answer. I suppose I'm going to be forced to think about that one some more. :)

[mpolo]

O.K. I was totally stupid on #48. I've solved it now (without even needing BigInt).

[dragonchild]

I've finished 9 so far, including a 15 point problem. A few hints for effective Perl usage:
• bignum is your friend.
• Not every problem is a math problem. (For example, I solved one problem with Date::Calc.)
• Use iterative algorithms - recursion will blow your stack.

[GrandFather]

I notice that a lot of the problems involve prime numbers. Is there an efficient way of generating the first n prime numbers? I know how to sieve for primes in a up to some maximum value, but that doesn't give the first n. Hints?

[BrowserUk]

How many do you want? The first 1,000, first 10,000 and first 1 to 15 million.

Download the list of your choice, reformat it to one/line and a fixed length (9 chars +newline covers the first 15 million), and you can grab as many as you need quickly and cheaply.

my $wanted = 500;
open my $primes, '<', 'primes.txt' or die $!;
my @primes = split "\s+", do{ local $/=\($wanted * 10); <$primes> };
close $primes;

[GrandFather]

Humph, that feels like cheating to me :).

Thanks for the links, a solution to the problem though not a answer to the question.

[radiantmatrix]

No need to reformat, just use the script below to put the large primes file in a DBD::SQLite2 database. First, download and unzip the files that contain the first 15 million primes in chunks of 1 million. You will have primes1.txt through primes15.txt in a directory. Run this there:

#!/bin/perl
use strict; use warnings;

use DBI;
my $dbh = DBI->connect('dbi:SQLite2:dbname=primes.db','','',{RaiseErro
+r=>1});
my $cnt = 0;

# 'number' has to be text because of length
$dbh->do('CREATE TABLE primes (id INTEGER, number TEXT)');

for (1..15) { $cnt = add_primes($dbh,$cnt,"primes$_.txt") }

sub add_primes {
    my ($db, $c, $filename) = @_;

    open my $file, '<', $filename or die("Can't read '$filename': $!")
+;
    print STDERR "Adding primes from $filename\n";
    
    #first two lines are not data, skip them
    for (1..2) { <$file> }

    eval {
        $db->begin_work;
        my $sth = $db->prepare('INSERT INTO primes (id,number) VALUES 
+(?,?)');
        while (<$file>) {
            foreach ( split(/\s+/,$_) ) { $sth->execute(++$cnt,$_) }
        }
        $db->commit;
    };
    if ($@) {
        print STDERR "Died while processing prime #$cnt, with error:\n
+$@";
        exit;
    }

    return $cnt;
}

Then you can always ask for the n'th prime with the SQL (? is n)

SELECT number FROM primes WHERE id = ?

[Anonymous Monk]

I find this fascinating, mostly because I don't understand it even a little.

I am a regular Perl Monk, but I've chosen to post this anonymously because I am certain that it will be voted down many times. In fact, I'm going to vote it down myself after I log back in... I'm such a coward :(

I consider myself a competent programmer. I know several languages and I am able to make a living working freelance. I have no problem with pointers, references, OO, complex regular expressions, etc. I am capable of solving some quite complex problems and I've managed to raise myself to level 6 here on Perl Monks. I even speak three spoken languages... It's just the damn math that I cannot learn.

I have never been competent in mathematics. I lack a formal education, I'm self-taught, and maybe that's the difference. I've tried and failed to work toward a computer science degree at more than one community college because of the mathematics requirements. For me, it takes all of my concentration to barely grasp mathematical concepts beyond the basics. True to my claim, I cannot grasp the use of bitwise operators (&, |, ^) in Perl or their equivalents in other languages.

Why are mathematics and programming so closely related?

--
-- Ghodmode

[rhesa]

Your sig made me laugh so hard! That was about as funny as this cartoon :-)

Update: Seriously though, I would be disappointed if people would downvote you, just because you admit to having a hard time grasping mathematics. I _have_ studied maths (for over 7 years), but I must say that for the majority of my programming work it's completely irrelevant. Text processing, web page generation, database interfacing, report generation etc. are all very common tasks we perform with Perl that don't require maths at all, but are still extremely valuable to our customers. I take enough pride in creating something that my clients want and appreciate. They rarely (if ever!) admire me for my mathematical prowess, but do for solving their problems.

[ikegami]

You're assuming the parent poster wished to be anonymous. The account "Anonymous Monk" is a misnomer, because it's not only used by people who wish to be anonymous. Some people are just too lazy to create an account, or don't want to create an account for for other reasons. I've posted on a number of boards on which I have no account. I typically sign those posts because anonimity is not my intention.

[GrandFather]

Actually for many of the problems there is very little maths required for solving the problem, but most problems require a fair amount of mechanical arithmetic - which is what computers are for :).

[Anonymous Monk]

Why are mathematics and programming so closely related?

Well, because mathematics can be quite all encompassing, depending upon how broadly you choose to define it. One such definition might be "the formal study of patterns": encompassing not only everything that exists, but everything that might exist and remain logically consistent. In that sense, to many mathematicians, the real world is just a special case. :-)

But in a less general sense, there's still a lot of overlap between mathematics and computer science. Mathematicians develop and prove the correctness of various algorithms: computer programmers then use those proven algorithms to solve real-world problems. Cryptography uses a lot of group theory and advanced math to develop hard to break cryto-systems; optimization problems involve a lot of calculus and algebra; neural networks involve a lot of statistics; effective compression algorithms and hashing algorithms involve probability analysis, and so forth. Even engineering problems often involve the use of partial differential equations (which again, requires calculus). Mathematics is the larger framework from which the specific tools for solving a given problem get developed.

You don't need a mathematics degree to do a "Hello, World" program. You don't need one to code up most business logic, either. You might benefit from one when doing research on just about any new thing that computers could be applied to, however.

--
Ytrew Q. Uiop ( who has a B.Math, but never uses it at work)

[rhesa]

I just reached 1000 points :)

Update: And here's my cheat sheet:

use Math::Pari qw/ primes nextprime isprime factor divisors /;

$P = primes(10);
print "First ten primes: @$P$/";

$D = divisors(100);
print "Divisors of 100: @$D$/";

$p = nextprime(100); 
print "next prime greater or equal to 100: $p$/";

$i = isprime(1680588011350901);
print "1680588011350901 is ", ($i?'':'not '), "prime$/";

$F = factor("10^100-1");
print "googol - 1 = ", join( "$/           * " ,
        map( { "$F->[0][$_]^$F->[1][$_]" } 0 .. $#{$F->[0]} )
      ), $/;

__END__
First ten primes: 2 3 5 7 11 13 17 19 23 29
Divisors of 100: 1 2 4 5 10 20 25 50 100
next prime greater or equal to 100: 101
1680588011350901 is  prime
googol - 1 = 3^2
           * 11^1
           * 41^1
           * 101^1
           * 251^1
           * 271^1
           * 3541^1
           * 5051^1
           * 9091^1
           * 21401^1
           * 25601^1
           * 27961^1
           * 60101^1
           * 7019801^1
           * 182521213001^1
           * 14103673319201^1
           * 78875943472201^1
           * 1680588011350901^1

[Anonymous Monk]

people joke about perl being line noise, but the solutions in the J and K languages are incomprehensible to me.

[Anonymous Monk]

i'm pretty sure my answer for 112 is correct, but apparently it's not. anybody see anything wrong with this? it works fine for the two examples (.5->538, .9->21780).

my $max    = .99;
my $bouncy = 0;

for (my $n=1; ; $n++)
{
  my ($inc, $dec) = (0, 0);

  my @d = split //, $n;
  for (my $i=0; $i<@d-1; $i++)
  {
    if    ($d[$i] < $d[$i+1]) { $inc++ }
    elsif ($d[$i] > $d[$i+1]) { $dec++ }
  }
  $bouncy++ if $inc and $dec;

  next if $max > $bouncy/$n;  
  printf "n=%d: %%%f\n", $n, $bouncy/$n;   
  last;
}

[hv]

Even though I can't see it explicitly stated anywhere, I think the intention of the site is that you solve the problems on your own without asking for help.

For what it's worth, while working through the problems I found that at least 75% of the time if my first attempt at an answer was wrong it was because I had misread the question rather than because I had a bug in my code.

Hugo

[mpolo]

Well, I don't think that directly helping would be "ethical", but for what it's worth I (and most of the successful coders from what I remember in the fora) did that one with a rather different approach. One helpful trick is to try the examples in the problem (just insert a print "helpful debugging stuff\n" if $n==number_with_known_property; and see if they get classified correctly by your program. Much more fun is number 113, which has a slick mathematical solution, or my methodical number-crunching solution...

[Anonymous Monk]

here's another one i thought was correct: 77.

my $target = 5_001;  # also tried 5_000
my $max = 1_000_000;

my @primes;
my $sieve = '';

# generate list of primes
for (my $try=2; $try <= $max; $try++)
{
  next if vec($sieve, $try, 1);
  push @primes, $try;
  for (my $mults=$try*$try; $mults <= $max; $mults+=$try)
  {
    vec($sieve, $mults, 1) = 1;
  }
}

# number of composites <= n
# http://research.att.com/~njas/sequences/A065855 
#
# equivalent to number of primes between prime(n) and n, so that's wha
+t 
# i'm doing here
for (my $i=0; $i<@primes; $i++)
{
  my $j = 0;
  $j++ while $primes[$j] <= $i+1;

  my $count = 0;
  $j++ && $count++ while $primes[$j] < $primes[$i];

  next if $count < $target;
  printf "%d: %d\n", $i+1, $count;
  last;
}