Fastest way to check if a number is a vampire number?

Question

A vampire number is defined here https://en.wikipedia.org/wiki/Vampire_number. A number V is a vampire number if:

• It can be expressed as X*Y such that X and Y have N/2 digits each where N is the number of digits in V
• Both X & Y should not have trailing zeros
• X & Y together should have the same digits as V

I came up with a solution,

strV = sort(toString(V))
for factor <- pow(10, N/2) to sqrt(V)
    if factor divides V
        X <- factor
        Y <- V/factor
        if X and Y have trailing zeros
           continue
        checkStr = sort(toString(X) + toString(Y))
        if checkStr equals strV return true

Another possible solution is to permute the string represented by V and split it into half and check if its a vampire number. Which one is the best way to do so?

Answer 1

The algorithm I propose here will not go through all permutations of digits. It will eliminate possibilities as fast as possible so that only a fraction of permutations will actually be tested.

Algorithm explained by example

Here is how it works based on example number 125460. If you are fine with reading the code directly, then you can skip this (long) part:

At first the two fangs (i.e. vampire factors) are obviously not known, and the problem can be represented as follows:

       ?**
   X   ?**
   -------
   =125460

For the left most digit of the first factor (marked with ?) we could choose any of the digits 0,1,2,5,4, or 6. But on closer analysis 0 would not be a viable possibility, as the product would never reach more than a 5-digit number. So it would be a waste of time to go through all permutations of digits that start with a zero.

For the left most digit of the second factor (also marked with ?), the same is true. However, when looking at the combinations, we can again filter out some pairs that cannot contribute to reaching the target product. For instance, this combination should be discarded:

       1**
   X   2**
   -------
   =125460

The greatest number that can be achieved with these digits is 199x299 = 59501 (ignoring the fact that we don't even have a 9), which is not even half of the desired number. So we should reject the combination (1, 2). For the same reason, the pair (1, 5) can be discarded for taking these positions. Similarly, the pairs (4, 5), (4, 6), and (5, 6) can be rejected as well, because they yield a too large product (>= 200000). I will call this kind of a test -- where it is determined whether the target number is within reach for a certain chosen digit pair, the "range test".

At this stage there is no difference between the first and the second fang, so we should also not have to investigate pairs where the second digit is smaller than the first, because they mirror a pair that would already have been investigated (or rejected).

So of all the possible pairs that could take up this first position (there are 30 possibilities to take 2 digits from a set of 6 digits), only the following 4 need to be investigated:

(1, 6), (2, 4), (2, 5), (2, 6)

In a more elaborate notation this means we are limiting the search to these number patterns:

       1**       2**       2**       2**
   X   6**   X   4**   X   5**   X   6**
   -------   -------   -------   -------
   =125460   =125460   =125460   =125460

       A         B         C         D

It is clear that this reduction of possibilities before even looking at the other positions greatly reduces the search tree.

The algorithm will take each of these 4 possibilities in order, and for each will check the possibilities for the next digit position. So first configuration A is analysed:

       1?*
   X   6?*
   -------
   =125460

The pairs that are available for the ?-marked positions are these 12:

(0, 2), (0, 4), (0, 5)
(2, 0), (2, 4), (2, 5)
(4, 0), (4, 2), (4, 5)
(5, 0), (5, 2), (5, 4)

Again, we can eliminate pairs by applying the range test. Let's take for instance the pair (5, 4). This would mean we had factors 15* and 64* (where * is an unknown digit at this point). The product of these two will be maximised with 159 * 649, i.e. 103191 (again ignoring the fact we do not even have a 9 available): this is too low for reaching the target, so this pair can be ignored. By further applying the range test, all these 12 pairs can be discarded, and so the search within configuration A stops here: there is no solution there.

Then the algorithm moves to configuration B:

       2?*
   X   4?*
   -------
   =125460

Again, the range test is applied to the possible pairs for the second position, and again it turns out none of these pairs passes the test: for instance (5, 6) can never represent a greater product than 259 * 469 = 121471, which is (only just) too small.

Then the algorithm moves to option C:

       2?*
   X   5?*
   -------
   =125460

Of all 12 possible pairs, only the following survive the range test: (4, 0), (4, 1), (6, 0), (6, 1). So now we have the following second-level configurations:

       24*       24*       26*       26*
   X   50*   X   51*   X   50*   X   51*
   -------   -------   -------   -------
   =125460   =125460   =125460   =125460

       Ca        Cb        Cc        Cd

In configuration Ca, there is no pair that passes the range test.

In configuration Cb, the pair (6, 0) passes, and leads to a solution:

       246
   X   510
   -------
   =125460

At this point the algorithm stops searching. The outcome is clear. In total the number of configurations looked at is very small compared to a brute force permutation checking algorithm. Here is a visualisation of the search tree:

 *-+-- (1, 6)
   |
   +-- (2, 4)
   |
   +-- (2, 5) -+-- (4, 0)
   |           |
   |           +-- (4, 1) ---- (6, 0) = success: 246 * 510
   /           /
   |           +-- (6, 0)
   |           |
   |           +-- (6, 1)
   |
   +-- (2, 6) ---- (0, 1) ---- (4, 5) = success: 204 * 615

The variants below / are only for showing what else the algorithm would have done, if there had not been a solution found. But in this actual case, that part of the search tree was actually never followed.

I have no clear idea of the time complexity, but it seems to run quite well for larger numbers, showing that the elimination of digits at an early stage makes the width of the search tree quite narrow.

Here is a live JavaScript implementation, which also runs some test cases when it it is activated (and it has a few other optimisations -- see code comments).

/*
    Function: vampireFangs
    Arguments:
        vampire: number to factorise into two fangs, if possible.
    Return value:
        Array with two fangs if indeed the argument is a vampire number.
        Otherwise false (not a vampire number) or null (argument too large to 
        compute) 
*/
function vampireFangs(vampire) {
    /* Function recurse: for the recursive part of the algorithm.
       prevA, prevB: partial, potential fangs based on left-most digits of the given 
                     number
       counts: array of ten numbers representing the occurrence of still 
                     available digits
       divider: power of 100, is divided by 100 each next level in the search tree.
                Determines the number of right-most digits of the given number that 
                are ignored at first in the algorithm. They will be considered in 
                deeper levels of recursion.
    */
    function recurse(vampire, prevA, prevB, counts, divider) {
        if (divider < 1) { // end of recursion
            // Product of fangs must equal original number and fangs must not both 
            // end with a 0.
            return prevA * prevB === vampire && (prevA % 10 + prevB % 10 > 0)
                ? [prevA, prevB] // Solution found
                : false; // It's not a solution
        }
        // Get left-most digits (multiple of 2) of potential vampire number
        var v = Math.floor(vampire/divider);
        // Shift decimal digits of partial fangs to the left to make room for 
        // the next digits
        prevA *= 10;
        prevB *= 10;
        // Calculate the min/max A digit that can potentially contribute to a 
        // solution
        var minDigA = Math.floor(v / (prevB + 10)) - prevA;
        var maxDigA = prevB ? Math.floor((v + 1) / prevB) - prevA : 9;
        if (maxDigA > 9) maxDigA = 9;
        for (var digA = minDigA; digA <= maxDigA; digA++) {
            if (!counts[digA]) continue; // this digit is not available
            var fangA = prevA + digA;
            counts[digA]--;
            // Calculate the min/max B digit that can potentially contribute to 
            // a solution
            var minDigB = Math.floor(v / (fangA + 1)) - prevB;
            var maxDigB = fangA ? (v + 1) / fangA - prevB : 9;
            // Don't search mirrored A-B digits when both fangs are equal until now.
            if (prevA === prevB && digA > minDigB) minDigB = digA;
            if (maxDigB > 9) maxDigB = 9;
            for (var digB = minDigB; digB <= Math.min(maxDigB, 9); digB++) {
                if (!counts[digB]) continue; // this digit is not available
                var fangB = prevB + digB;
                counts[digB]--;
                // Recurse by considering the next two digits of the potential 
                // vampire number, for finding the next digits to append to 
                // both partial fangs.
                var result = recurse(vampire, fangA, fangB, counts, divider / 100);
                // When one solution is found: stop searching & exit search tree.
                if (result) return result; // solution found
                // Restore counts
                counts[digB]++;
            }
            counts[digA]++;
        }
    }


    // Validate argument
    if (typeof vampire !== 'number') return false;
    if (vampire < 0 || vampire % 1 !== 0) return false; // not positive and integer
    if (vampire > 9007199254740991) return null; // beyond JavaScript precision 
    var digits = vampire.toString(10).split('').map(Number);
    // A vampire number has an even number of digits
    if (!digits.length || digits.length % 2 > 0) return false;
    
    // Register per digit (0..9) the frequency of that digit in the argument
    var counts = [0,0,0,0,0,0,0,0,0,0];
    for (var i = 0; i < digits.length; i++) {
        counts[digits[i]]++;
    }
    
    return recurse(vampire, 0, 0, counts, Math.pow(10, digits.length - 2));
}

function Timer() {
    function now() { // try performance object, else use Date
        return performance ? performance.now() : new Date().getTime();
    }
    var start = now();
    this.spent = function () { return Math.round(now() - start); }
}

// I/O
var button = document.querySelector('button');
var input = document.querySelector('input');
var output = document.querySelector('pre');

button.onclick = function () {
    var str = input.value;
    // Convert to number
    var vampire = parseInt(str);
    
    // Measure performance
    var timer = new Timer();

    // Input must be valid number
    var result = vampire.toString(10) !== str ? null 
                 : vampireFangs(vampire);

    output.textContent = (result 
            ? 'Vampire number. Fangs are: ' + result.join(', ') 
            : result === null 
                    ? 'Input is not an integer or too large for JavaScript' 
                    : 'Not a vampire number')
       + '\nTime spent: ' + timer.spent() + 'ms';
}

// Tests (numbers taken from wiki page)

var tests = [
    // Negative test cases:
    [1, 999, 126000, 1023],
    // Positive test cases:
    [1260, 1395, 1435, 1530, 1827, 2187, 6880, 
    102510, 104260, 105210, 105264, 105750, 108135, 
    110758, 115672, 116725, 117067, 118440, 
    120600, 123354, 124483, 125248, 125433, 125460, 125500,
    13078260,
    16758243290880,
    24959017348650]
];
tests.forEach(function (vampires, shouldBeVampire) {
    vampires.forEach(function (vampire) {
        var isVampire = vampireFangs(vampire);
        if (!isVampire !== !shouldBeVampire) {
            output.textContent = 'Unexpected: vampireFangs(' 
                    + vampire + ') returns ' + JSON.stringify(isVampire);
            throw 'Test failed';
        }
    });
});
output.textContent = 'All tests passed.';

N: <input value="1047527295416280"><button>Vampire Check</button>
<pre></pre>

As JavaScript uses 64 bit floating point representation, the above snippet only accepts to numbers up to 2⁵³-1. Above that limit there would be loss of precision and consequently unreliable results.

As Python does not have such limitation, I also put a Python implementation on eval.in. That site has a limitation on execution times, so you'd have to run it elsewhere if that becomes an issue.