More recreational math here. Again I was reading some
book by Clifford Pickover,
and heard about Vampire Numbers.
A Vampire Number is equal to a product of it's digits
like 1435 = 41 * 35. I think the name comes from a
reference to such a number in an Anne Rice novel.
So I went hunting for more vamps. This program only
looks for products of two factors, it would be interesting
to look for products of more than two factors.
Algorithm is basically to generate a list of orderings
of the digits (1234, 1243, 1342, 1324, ...), not taking
the trouble to eliminate duplicates.
Next each ordering is split at each digit and tested
(1*234, 12*34, 123*4).
Of note is 153. In addition to being a Triangle Number
(1+2+3+...+17), it is also a selfcubereferential number
(1**3 + 5**3 + 3**3), a sum of factorials (1! + 2! + 3! + 4! + 5!),
and a Vampire Number (3 * 51).
VampFoo
Update: The book is 'The Loom of God'. A 40digit Vnum is
listed there: 98765432198765432198 * 98765432198830604534 =
9754610597415368368844499268390128385732, whew!
#!/usr/bin/perl
use strict;
if (@ARGV < 2) {
print STDERR "\nUsage: $0 firstnumber lastnumber\n\n";
}
my ($beg, $end) = @ARGV;
my ($test, $this, $that);
for $test ($beg..$end) {
($this, $that) = factors($test);
if ($this ne '') {
print "$test = $this * $that\n";
}
}
#
sub factors {
my ($target) = @_;
my ($order, $olist);
my ($split, $slist);
$olist = orderings($target);
for $order (@{$olist}) {
#print "$order\n";
$slist = splittings($order);
for $split (@{$slist}) {
#print "$split>[0] $split>[1]\n";
if ($split>[0] * $split>[1] == $target) {
return ($split>[0], $split>[1]);
}
}
}
}
#
sub splittings {
my ($num) = @_;
my (@digits) = split('', $num);
my (@list, @useds);
while (@digits > 1) {
push(@useds, shift(@digits));
push (@list, [join('', @useds), join('', @digits)]);
}
return \@list;
}
#
sub orderings {
my ($num) = @_;
my (@digits) = split('', $num);
my (@list, $sublists, $sub, $this);
if (@digits == 1) { return [$digits[0]]; }
for (1..@digits) {
$this = shift(@digits);
$sublists = orderings(join('', @digits));
for $sub (@{$sublists}) {
push(@list, "$this$sub");
}
push(@digits, $this);
}
return \@list;
}
Re: Vampire Numbers
by AbigailII (Bishop) on Jun 11, 2002 at 08:53 UTC

Here's a piece of code that finds all Vampire numbers with
factors smaller than the argument given:
#!/usr/bin/perl
use strict;
use warnings 'all';
my @vampire;
foreach my $s (1 .. shift) {
LOOP:
foreach my $t (1 .. $s) {
my $prod = $s * $t;
my $cat = "$s$t";
foreach my $d (0 .. 9) {
next LOOP unless eval "\$prod =~ y/$d/$d/ ==
\$cat =~ y/$d/$d/";
}
push @vampire => [$prod, $s, $t];
}
}
@vampire = sort {$a > [0] <=> $b > [0]} @vampire;
foreach my $vamp (@vampire) {
printf "%4d * %4d = %8d\n" => @$vamp [1, 2, 0];
}
Note that if there is one vampire number (and there is),
then we have an infinite number of vampire numbers.
Proof: Suppose V = n * m is a vampire number. Then
10 * V = (10 * n) * m is a vampire number as well. qed.
Abigail
 [reply] [d/l] 

a couple of general formulas such as the the fangs
x = 25.10^k+1
y = 100(10^(k+1)+52)/25
give the vampire
v = xy = (10^(k+1)+52)10^(k+2)+100(10^k+1+52)/25
= x'.10^(k+2)+t
= 8(26+5.10^k)(1+25.10^k)
where x' denotes x with digits reversed
 [reply] 

153 is also a plus perfect number or 'armstrong' number
153=1^3+5^3+3^3=1+125+27
 [reply] 
Re: Vampire Numbers
by particle (Vicar) on Jun 10, 2002 at 21:02 UTC

i love these problems, YuckFoo. i think i should pick up one of these books you've been reading. i keep my skills sharp with martin gardner's puzzlers ( here's a book list. )
okay, so this code's a little evil :P
i should probably document it a bit.... here goes:
#!/usr/bin/perl
use strict;
use warnings;
$++;
# is using Algorithm::FastPermute cheating? i hope not.
use Algorithm::FastPermute qw/ permute /;
## use Data::Dumper; # see what's inside...
( @ARGV == 2 and $ARGV[0] < $ARGV[1] ) # process arguments
? my( $lower, $upper ) = @ARGV
: die 'usage: ' . $0 . ' lower upper' . $/;
NUMBER: for my $try ( $lower..$upper )
{ # try each number within bounds
my @digits = split //, '*' . $try; # makes ( '*', 1, 2, 3, etc )
my @permutations; # holds permutations
# push permutations onto array
# unless the permutation has a '*' on either end
permute {
push @permutations, [ @digits ]
unless @digits>[1] eq '*' or @digits>[0] eq '*';
} @digits;
## # uncomment to see what's inside...
## print Dumper \@permutations;
my %results = # product => operation pairs
map { eval( $_ )  0, $_ } # create pair
map { join( '', @{ $_ } ) } # stringify the array
@permutations; # for each permutation
## # uncomment to see what's inside...
## print Dumper \@permutations;
defined $results{ $try } # if i found one
&& print( $try, # print it
' is vampire (',
$results{ $try }, # and how i got there
')', $/ )
&& next NUMBER;
}
~Particle *accelerates*
 [reply] [d/l] [select] 
Factors
by gumby (Scribe) on Jun 11, 2002 at 14:19 UTC

A more efficient algorithm (of Gauss and later Kraitchik) would be to find solutions to the congruence x^2=y^2 (mod p) e.g.
38^2=3^2 (mod 1435)
It is trivial to then check if the factor (38+3 in this case) is a permutation of n/2 digits from the original number.  [reply] 

I think what is being suggested here is that instead of
creating all possible pairs of numbers (x,y) from the
digits of a number p and testing if x*y == p, it is more
efficient to factor the number p first and and then test
all possible factorizations to see if they are just a
permuation of the digits of p.
Finidng a quadratic residue x^2=y^2 (mod p) is useful,
because then x^2  y^2 = (x+y)*(xy) = 0 (mod p) and
so (x+y) or (xy) may be factors of p.
In practice, one starts with an x that has the smallest
square larger than p, then computes x^2p to see if it
is a perfect square. If not, increment x and repeat.
This is pretty fast relative to testing by division
from 2 to sqrt(p), but there exist even faster methods
based on the quadratic residue. The Quadratic Sieve,
invented by Pomerance in 1981 is a direct derivative
and the Number Field Sieve is a related method.
Getting back to Vampire numbers, what are the relative
efficiencies for a number p with 2d digits? For the first
method, a naive approach generates all permutations of 2*d
digits and splits each into two ddigit numbers to test.
Thus each 2d digit number requires about (2*d)! == (2*log(p))!
tests, or (2*log p)^(2*log p) by Stirling's approximation.
For the second method, a quadratic sieve has running
time of order exp(sqrt(log(p)*log(log(p)))) to find a
single factor of p. So finding a single factor using QS
is more efficient that testing all factors using the
first method. But I don't know the running time for
finding all the factors using the QS and I don't know the
typical multiplier for the scaling result of the QS method.
Anyone?
Mark
 [reply] 

The Quadratic Sieve has running time
O(e^(sqrt(1.125ln(n)ln(ln(n)))))
But with certain improvements (such as using Wiedemann's Gaussian Elimination algorithm over GF(2)), it's running time is given by
O(e^(sqrt(ln(n)ln(ln(n)))))
The Number Field Sieve is better for numbers over 100digits and has running time
O(e^(1.9223((ln(n))^1/3(ln(ln(n))))^2/3))
Excuse my notation (but TeX would be overkill).
Note: O(stuff) means the magnitude of the running time is < A * stuff for some constant A and all values of n.
 [reply] 

It seemed like a good idea so I cooked it up according to
your description. Correct me if I'm wrong but it seems
quadratic residues won't account for all factors.
Program correctly factors 24 to 4*6 and 2*12 but misses
3*8. Program finds no factors for 54.
YuckFoo
Update: With a little thought one can see the
program will only find factor pairs that are both even
or both odd. x+y * xy = p.
#!/usr/bin/perl
use strict;
my ($num) = @ARGV;
my $x = int(sqrt($num)) + 1;
my $y = sqrt($x * $x  $num);
while ($x  $y >= 2) {
if ($y == sprintf("%d", $y)) {
print "Ok $num = ", $x$y, " * ", $y+$x, "\n";
}
else { print "No x = $x, y = $y\n"; }
$x++;
$y = sqrt($x * $x  $num);
}
 [reply] [d/l] 



Re: Vampire Numbers
by gumby (Scribe) on Jun 13, 2002 at 12:19 UTC

You're quite right, Fermat's method will only find two factors: it is important to note that all the fastest factoring algorithms (with the exception of the elliptic curve method) use this as a basis.
The Quadratic Sieve works as follows:
If n is the number to be factored, the QS tries to find x and y such that x^2 = y^2 (mod n) and x is not equal to plus or minus y; this implies that (xy)(x+y)=0 and we compute GCD(xy,n) to see if this is a nontrivial divisor. There is at least a 1/2 chance that the factor will be nontrivial. The first step is to define
Q(x)=(x+floor(sqrt(n)))^2n=x'^2n
and compute Q(x_1),Q(x_2),...,Q(x_k). Determining the x_i requires sieving over a factor base (using primes such that the Legendre symbol (n/p)=1). From the evaluations of Q(x) we want a subset Q(x_i1)Q(x_i2)...Q(x_ir) that is a square, y^2. Then note that for all x, Q(x)=x'^2 (mod n). So what we now have is that
Q(x_i1)Q(x_i2)...Q(x_ir)=(x_i1*x_i2*...*x_ir)^2 (mod n)
Which are the factors of n.  [reply] 

