No such thing as a small change PerlMonks

### Re^2: Vampire Numbers Revisited

by tall_man (Parson)
 on Mar 24, 2005 at 20:17 UTC ( #442183=note: print w/replies, xml ) Need Help??

in reply to Re: Vampire Numbers Revisited

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";
}
}
}
}

Create A New User
Node Status?
node history
Node Type: note [id://442183]
help
Chatterbox?
and all is quiet...

How do I use this? | Other CB clients
Other Users?
Others having an uproarious good time at the Monastery: (6)
As of 2018-03-20 20:22 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
When I think of a mole I think of:

Results (259 votes). Check out past polls.

Notices?