 Do you know where your variables are? PerlMonks

Vampire Numbers

by YuckFoo (Abbot)
 on Jun 10, 2002 at 19:25 UTC ( #173273=CUFP: print w/replies, xml ) Need Help??

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 self-cube-referential 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 40-digit V-num 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-> \$split->\n"; if (\$split-> * \$split-> == \$target) { return (\$split->, \$split->); } } } } #----------------------------------------------------------- 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]; } for (1..@digits) { \$this = shift(@digits); \$sublists = orderings(join('', @digits)); for \$sub (@{\$sublists}) { push(@list, "\$this\$sub"); } push(@digits, \$this); } return \@list; }

Replies are listed 'Best First'.
Re: Vampire Numbers
by Abigail-II (Bishop) on Jun 11, 2002 at 12: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 ->  <=> \$b -> } @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

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

153 is also a plus perfect number or 'armstrong' number

153=1^3+5^3+3^3=1+125+27

Re: Vampire Numbers
by particle (Vicar) on Jun 11, 2002 at 01: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 < \$ARGV ) # 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-> 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*

Factors
by gumby (Scribe) on Jun 11, 2002 at 18: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.

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)*(x-y) = 0 (mod p) and so (x+y) or (x-y) may be factors of p.

In practice, one starts with an x that has the smallest square larger than p, then computes x^2-p 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 d-digit 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
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 100-digits 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.

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 * x-y = 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); }
Re: Vampire Numbers
by gumby (Scribe) on Jun 13, 2002 at 16: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 (x-y)(x+y)=0 and we compute GCD(x-y,n) to see if this is a non-trivial divisor. There is at least a 1/2 chance that the factor will be non-trivial. The first step is to define

Q(x)=(x+floor(sqrt(n)))^2-n=x'^2-n

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.

Create A New User
Node Status?
node history
Node Type: CUFP [id://173273]
Approved by FoxtrotUniform
help
Chatterbox?
and the web crawler heard nothing...

How do I use this? | Other CB clients
Other Users?
Others avoiding work at the Monastery: (5)
As of 2019-10-23 02:18 GMT
Sections?
Information?
Find Nodes?
Leftovers?
Voting Booth?
In 2019 the site I miss most is:

Results (57 votes). Check out past polls.

Notices?