Google Job Ad Solution

davorg on 2004-07-14T07:41:24

Here's the program I used to solve the first stage of Google's puzzle.

#!/usr/bin/perl
                                                                                
use Net::DNS;
                                                                                
my $res = Net::DNS::Resolver->new;
                                                                                
my $e = '27182818284590452353602874713526624977572470936999'
       .'59574966967627724076630353547594571382178525166427'
       .'42746639193200305992181741359662904357290033429526'
       .'05956307381323286279434907632338298807531952510190'
       .'11573834187930702154089149934884167509244761460668';
                                                                                
foreach (0 .. length $e) {
  my $n = substr $e, $_, 10;
                                                                                
  my $q = $res->search("$n.com");
                                                                                
  if ($q) {
    print $n, "\n";
    last;
  }
}

---

brilliance

petdance on 2004-07-14T15:29:39

That's brilliant. When I saw it, I was thinking about the hassle of determining the primes. Bypass that annoying second step, and go straight to the DNS!

Re:brilliance

davorg on 2004-07-14T15:47:21

Laziness is a virtue :)

Early answer

perlmoth on 2004-07-14T20:20:03

What surprises me is how early in the sequence that the answer occurs. I'd have thought that the first 10-digit prime would have occurred in the umpty-thousandth digit in the sequence, but then again my number theory knowledge is quite hopeless.
Did you realise that the answer was likely to occur within the first 250 digits, or was it a bit of luck?

An early answer is not at all unlikely

btilly on 2004-07-15T22:41:04

From the prime number theorem, the density of primes around n is 1/log(n) where log is the natural log (which just coincidentally is what Perl uses for a log function). Which means that a random string of 10 digits has about 1 chance in 25 or so of being prime.

Therefore the odds of finding one in the first 250 digits are pretty good. And if you don't find one there, you can just add digits.

Incidentally the geeky answer to this question is that the first 10 digit prime in the digits of e is 0000000002. That won't get you a job though. :-(