Re: Project Euler (a series of challenging mathematical/computer programming problems)
by GrandFather (Saint) on Feb 03, 2006 at 11:15 UTC

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
 [reply] 
Re: Project Euler (a series of challenging mathematical/computer programming problems)
by negation (Beadle) on Feb 03, 2006 at 10:58 UTC

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.
spikydragon.fi  tshirts for Coders, engineers, roleplayers, scientists, jugglers and nerds
 [reply] 
Re: Project Euler (a series of challenging mathematical/computer programming problems)
by mpolo (Chaplain) on Feb 04, 2006 at 20:36 UTC

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. :)
 [reply] 

O.K. I was totally stupid on #48. I've solved it now (without even needing BigInt).
 [reply] 
Re: Project Euler (a series of challenging mathematical/computer programming problems)
by dragonchild (Archbishop) on Feb 05, 2006 at 03:33 UTC

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.
My criteria for good software:
 Does it work?
 Can someone else come in, make a change, and be reasonably certain no bugs were introduced?
 [reply] 
Re: Project Euler (a series of challenging mathematical/computer programming problems)
by GrandFather (Saint) on Feb 04, 2006 at 08:50 UTC

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
 [reply] 

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;
Examine what is said, not who speaks  Silence betokens consent  Love the truth but pardon error.
Lingua non convalesco, consenesco et abolesco.  Rule 1 has a caveat!  Who broke the cabal?
"Science is about questioning the status quo. Questioning authority".
In the absence of evidence, opinion is indistinguishable from prejudice.
 [reply] [d/l] 

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
 [reply] 




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 = ?
 [reply] [d/l] [select] 
Re: Project Euler (a series of challenging mathematical/computer programming problems)
by Anonymous Monk on Feb 05, 2006 at 12:18 UTC

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 selftaught, 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
 [reply] 

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.
 [reply] 

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.
 [reply] 



 [reply] 

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 realworld problems. Cryptography uses a lot of group theory and advanced math to develop hard to break crytosystems; 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)
 [reply] 
Re: Project Euler (a series of challenging mathematical/computer programming problems)
by rhesa (Vicar) on Feb 14, 2006 at 20:09 UTC

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^1001");
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
 [reply] [d/l] 
Re: Project Euler (a series of challenging mathematical/computer programming problems)
by Anonymous Monk on Feb 07, 2006 at 12:53 UTC

people joke about perl being line noise, but the solutions in the J and K languages are incomprehensible to me.  [reply] 
Re: Project Euler (a series of challenging mathematical/computer programming problems)
by Anonymous Monk on Feb 11, 2006 at 21:36 UTC

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<@d1; $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;
}
 [reply] [d/l] 

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
 [reply] 

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 numbercrunching solution...
 [reply] [d/l] 
Re: Project Euler (a series of challenging mathematical/computer programming problems)
by Anonymous Monk on Feb 11, 2006 at 21:56 UTC

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;
}
 [reply] [d/l] 