I made an optimized version based on some of the suggestions on the web site, such as storing the digit counts in bit fields, unrolling the inner loop, and making use of caching.
It can find the 112,025 ten-digit vampire numbers (duplicated values included) in about an hour and a half on my machine. Since the problem takes about 100 times longer with each digit, going any higher would probably take recoding the inner loops in C.
Note: because of the possibility of overflow in the 3-bit digit bins, there may be some false positives -- they should be screened out with another script. I found none when I tried this.
use strict;
use warnings;
my $digits = 5;
my %cache;
# Keep digits in a shift map - 3 places per digit.
my @digitmap;
$digitmap[$_] = 1 << ($_ * 3) for (0..9);
my @starter;
my $min = 1 . (0 x ($digits-1));
my $max = 9 x $digits;
for (0..8) {
$starter[($_+1) % 9] = $min + $_;
}
# Cache all the digit combinations we will need.
init_cache(0);
init_cache(2);
init_cache(3);
init_cache(5);
init_cache(6);
init_cache(8);
find_vampires(0,0);
find_vampires(2,2);
find_vampires(3,6);
find_vampires(5,8);
find_vampires(6,3);
find_vampires(8,5);
sub init_cache {
my $i = shift;
my ($a, $a_digits);
for ($a = $starter[$i]; $a <= $max; $a += 9) {
$a_digits = 0;
$a_digits += $digitmap[$_] for (split //,$a);
$cache{$a} = $a_digits;
}
}
sub find_vampires {
my ($i, $j) = @_;
my ($a, $b, $a_digits, $b_digits, $prod_digits);
for ($a = $starter[$i]; $a <= $max; $a += 9) {
$a_digits = $cache{$a};
for ($b = $starter[$j]; $b <= $a; $b += 9) {
$b_digits = $cache{$b};
my $prod = $a * $b;
$prod_digits = 0;
$prod_digits += $digitmap[$_] for (split //,$prod);
if ($prod_digits == ($a_digits + $b_digits)) {
print "$a * $b = $prod\n";
}
}
}
}
-
Are you posting in the right place? Check out Where do I post X? to know for sure.
-
Posts may use any of the Perl Monks Approved HTML tags. Currently these include the following:
<code> <a> <b> <big>
<blockquote> <br /> <dd>
<dl> <dt> <em> <font>
<h1> <h2> <h3> <h4>
<h5> <h6> <hr /> <i>
<li> <nbsp> <ol> <p>
<small> <strike> <strong>
<sub> <sup> <table>
<td> <th> <tr> <tt>
<u> <ul>
-
Snippets of code should be wrapped in
<code> tags not
<pre> tags. In fact, <pre>
tags should generally be avoided. If they must
be used, extreme care should be
taken to ensure that their contents do not
have long lines (<70 chars), in order to prevent
horizontal scrolling (and possible janitor
intervention).
-
Want more info? How to link
or How to display code and escape characters
are good places to start.
|