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 ab 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 langues 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? ;-)
Incidently, 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 rigth direction (without revealing the solution of course).
Happy fun coding!
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.
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 :)
DWIM is Perl's answer to Gödel
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?
DWIM is Perl's answer to Gödel
How many do you want? The [http://primes.utm.edu/lists/small/1000.txt|first 1,000], [http://primes.utm.edu/lists/small/10000.txt|first 10,000] and [http://primes.utm.edu/lists/small/millions/|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;
Humph, that feels like cheating to me :).
Thanks for the links, a solution to the problem though not a answer to the question.
DWIM is Perl's answer to Gödel
Okay. Since none of the math guys have answered, I'll risk telling you my uninformed opinion on the matter. As far as I am aware:
- The most efficient way of generating 'small' primes, defined as < 1e10, is the Sieve of Atkins, which is a kind of variation on the the Sieve of Eratosthenes that uses quadratic forms. I read that. I don't know what it means :)
For this to be efficient for time requires it to be coded in platform specific C (with masses of performance critical bit twiddling), or hand crafted assembler that also requires intimite knowledge of the performance characteristics of the cpu used.
There is also a method known as 'wheel factorisation', but again, you cannot predict how high you would need to go before you will find the N you want. It has the advantage of not requiring the retention of the list of primes so far, but requires more divsions and so is generally slower.
- As with the SoE, there is no exact method of knowing how high to go with the SoA in order to generate the first N primes.
The best you can do is set your upper bound to N log N where N is the number you wish to find. This approximation apparently tends to get more accurate the higher you go?
You could download a good implementation that will generate the list very quickly. Once you've generated the list once, the lookup method is probably quicker.
You could maybe make it quicker still by storing the list in packed binary. You'd only need a 60 MB file instead of 160 MB, and would read less. unpacking to an array may be quicker than conversion from ascii.
For my purposes a while back, I wanted the nearest prime less than a number within the program, so a binary chop lookup with a resonable guess at starting position worked best for me.
I had a go myself to see what was possible with simple code. It doesn't scale well, but is acceptable for the first 100,000 primes.
DWIM is Perl's answer to Gödel
I just saw that and decided to time the mechanism I suggested. At 1/3rd of a second for the first million, it even surprised me :)
#! perl -slw
use strict;
use Devel::Timer;
my $T = new Devel::Timer;
sub firstNprimes {
my $n = shift;
open my $primes, '<:raw', 'primes.all' or die $!;
my @primes = split ' ', do{ local $/ = \( $n * 10 ); <$primes> };
close $primes;
return \@primes;
}
$T->mark( '201' );
my $ref1 = firstNprimes( 201 );
$T->mark( '100,000' );
my $ref2 = firstNprimes( 100_000 );
$T->mark( '1,000,000' );
my $ref3 = firstNprimes( 1_000_000 );
$T->report;
__END__
C:\Perl\test\data>..\junk4
Devel::Timer Report -- Total time: 0.3176 secs
Interval Time Percent
----------------------------------------------
02 -> 03 0.3169 99.78% 100,000 -> 1,000,000
01 -> 02 0.0007 0.21% 201 -> 100,000
00 -> 01 0.0000 0.01% INIT -> 201
That's the ascii version, and it does slow down quite quickly due memory allocation as you go larger; 2 million takes 8 seconds.
I might try the binary file version later.
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','','',{RaiseError=>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 = ?
A collection of thoughts and links from the minds of geeks
The Code that can be seen is not the true Code
I haven't found a problem yet that can't be solved by a well-placed [http://en.wikipedia.org/wiki/Trebuchet|trebuchet]
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. :)
- 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.
My criteria for good software:
- Does it work?
- Can someone else come in, make a change, and be reasonably certain no bugs were introduced?
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
Point is, there's really not much to be gained by posting anonymously if you're also going to say who you are, because if people don't like your post, they'll easily find ways of expressing disapproval on your non-anonymous account. (Unfortunate, but true.)
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)
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 :).
DWIM is Perl's answer to Gödel
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;
}
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
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...
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 what
# 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;
}