Find all the 4 digit vampire numbers

Question

I am solving a problem to find out all the 4 digit Vampire numbers.

A Vampire Number v=x*y is defined as a number with 'n' even number of digits formed by multiplying a pair of 'n/2'-digit numbers (where the digits are taken from the original number in any order)x and y together. If v is a vampire number, then x&y and are called its "fangs."

Examples of vampire numbers are:

    1.    1260=21*60     2.    1395=15*93     3.    1530=30*51 

I have tried the brute force algorithm to combine different digits of a given number and multiply them together . But this method is highly inefficient and takes up a lot of time.

Is there a more efficient algorithmic solution to this problem?

Answer 1

Or you can use a property of vampire numbers described on this page (linked from Wikipedia) :

An important theoretical result found by Pete Hartley:

      If x·y is a vampire number then x·y == x+y (mod 9)  

Proof: Let mod be the binary modulo operator and d(x) the sum of the decimal digits of x. It is well-known that d(x) mod 9 = x mod 9, for all x. Assume x·y is a vampire. Then it contains the same digits as x and y, and in particular d(x·y) = d(x)+d(y). This leads to: (x·y) mod 9 = d(x·y) mod 9 = (d(x)+d(y)) mod 9 = (d(x) mod 9 + d(y) mod 9) mod 9 = (x mod 9 + y mod 9) mod 9 = (x+y) mod 9

The solutions to the congruence are (x mod 9, y mod 9) in {(0,0), (2,2), (3,6), (5,8), (6,3), (8,5)}

So your code could look like this :

for(int i=18; i<100; i=i+9){          // 18 is the first multiple of 9 greater than 10    for(int j=i; j<100; j=j+9){        // Start at i because as @sh1 said it's useless to check both x*y and y*x        checkVampire(i,j);    } }  for(int i=11; i<100; i=i+9){          // 11 is the first number greater than 10 which is = 2 mod 9    for(int j=i; j<100; j=j+9){        checkVampire(i,j);    } }  for(int i=12; i<100; i=i+9){    for(int j=i+3; j<100; j=j+9){        checkVampire(i,j);    } }  for(int i=14; i<100; i=i+9){    for(int j=i+3; j<100; j=j+9){        checkVampire(i,j);    } }  // We don't do the last 2 loops, again for symmetry reasons 

Since they are 40 elements in each of the sets like {(x mod 9, y mod 9) = (0,0); 10 <= x <= y <= 100}, you only do 4*40 = 160 iterations, when a brute-force gives you 10ˆ4 iterations. You can do even less operations if you take into account the >= 1000 constraint, for instance you can avoid checking if j < 1000/i.

Now you can easily scale up to find vampires with more than 4 digits =)

Answer 2

Iterate over all possible fangs (100 x 100 = 10000 possibilities), and find if their product has the same digits as the fangs.