The fastest way to check if a number is a vampire?

Question

The number of vampires is here https://en.wikipedia.org/wiki/Vampire_number . The 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 and Y must not have trailing zeros
• X and Y together must 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 rearrange the line represented by V and split it into half and check if its vampire number is. Which one is the best way to do this?

Answer 1

In pseudo code:

 if digitcount is odd return false if digitcount is 2 return false for A = each permutation of length digitcount/2 selected from all the digits, for B = each permutation of the remaining digits, if either A or B starts with a zero, continue if both A and B end in a zero, continue if A*B == the number, return true 

There are a number of optimizations that can still be done here, mainly in terms of ensuring that every possible pair of factors is checked only once. In other words, what is the best way to check the repetition of numbers when choosing permutations?

But this is the essence of the algorithm that I would use.

PS: You are not looking for prime numbers, so why use a primary test? You just need to know if these numbers are vampires; there are only a few possible factors. No need to check all numbers before sqrt (number).

Answer 2

The algorithm proposed here will not go through all permutations of numbers. This will allow eliminating the possibilities as quickly as possible so that only a part of the permutations is actually checked.

Algorithm Explained by Example

Here's how it works with number 125460 as an example. If you are good at reading the code directly, you can skip this (long) part:

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

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

For the leftmost digit of the first factor (indicated by ? ), We can choose any digit 0,1,2,5,4 or 6. But with a closer analysis, 0 will not be a viable opportunity, since the product will never reach more than a 5-digit number. Thus, it would be a waste of time to go through all the permutations of numbers starting from zero.

For the leftmost digit of the second factor (also marked ? ), The same is true. However, looking at the combinations, we can again filter out some pairs that cannot contribute to the achievement of the target product. For example, this combination should be discarded:

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

The largest number that can be achieved using these numbers is 199x299 = 59501 (ignoring the fact that we don’t even have 9), which does not even make up half the desired number. Therefore, we must abandon the combination (1, 2). For the same reason, the pair (1, 5) can be discarded for these positions. Similarly, pairs (4, 5), (4, 6) and (5, 6) can also be dropped because they produce too much product (> = 200000). I will call this type of test - where it will be determined whether the target number is within reach for a specific selected pair of digits, the "range test".

At this stage, there is no difference between the first and second fangs, so we also do not need to examine pairs where the second digit is less than the first, since they reflect a pair that has already 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), you only need to examine the following 4:

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

In more detailed notations, this means that we restrict the search for these number patterns:

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

It is clear that this reduction in opportunities, even if you look at other positions, significantly reduces the search tree.

The algorithm takes each of these 4 possibilities in order, and each of them checks the possibilities for the next digit position. Therefore, the first configuration A is analyzed:

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

Couples available for line items with ? -markets are the following 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 the pairs by applying a range test. Take, for example, a pair (5, 4). This would mean that we had the coefficients 15 * and 64 * (where * is an unknown figure at this point). The product of these two will be maximum with 159 * 649, i.e. 103191 (again ignoring the fact that we don’t even have 9 available): this is too little to achieve the goal, so this pair can be ignored. With further use of the range test, all of these 12 pairs can be discarded, and therefore the search in configuration A stops here: there is no solution.

Then the algorithm goes to configuration B:

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

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

Then the algorithm goes to option C:

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

Of all 12 possible pairs, only the following tests survive: (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 

There is no pair in the Ca configuration that passes the range test.

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

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

At this point, the algorithm stops the search. The result is clear. In general, the number of configurations considered is very small compared with the brute force permutation verification algorithm. Here's a visualization 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 options below / are intended only to show what else the algorithm would do if a solution were not found. But in this actual case, this part of the search tree was not actually executed.

I don’t have a clear idea of ​​time complexity, but it seems to work well for large numbers, showing that removing digits at an early stage makes the width of the search tree pretty narrow.

Here is a real JavaScript implementation that also runs some test cases when it is activated (and has several other optimizations - 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 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 AB 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> 

Because JavaScript uses a 64-bit floating-point representation, the above snippet accepts only numbers up to 2 ⁵³ -1. Above this limit, there will be a loss of accuracy and therefore unreliable results.

Since Python has no such restriction, I also add a Python implementation to eval.in. This site has a run time limit, so you have to run it elsewhere if this becomes a problem.

Answer 3

Here are some suggestions:

• First, a simple improvement: if the number of digits is <4 or the odd return is false (or v is also negative).

• You do not need to sort v , just count how many times each digit O (n) occurs.

• You do not need to check each number, only combinations that are possible with numbers. This can be done by backtracking and significantly reduces the number of rooms that need to be checked.

• The last sort, to check whether all the numbers were used, is also not needed, just add the used numbers of both numbers and compare with the entries in v .

Here is the code for a JS-like language with integers that never overflow, the v parameter is a whole line without a leading 0s:

Edit: As it turns out, the code is not only JS-like, but also a valid JS-code, and he had no problem deciding that 1047527295416280 is really a vampire number ( jsfiddle ).

 var V, v, isVmp, digits, len; function isVampire(numberString) { V = numberString; if (V.length < 4 || V.length % 2 == 1 ) return false; v = parseInt(V); if (v < 0) return false; digits = countDigits(V); len = V.length / 2; isVmp = false; checkNumbers(); return isVmp; } function countDigits(s) { var offset = "0".charCodeAt(0); var ret = [0,0,0,0,0,0,0,0,0,0]; for (var i = 0; i < s.length; i++) ret[s.charCodeAt(i) - offset]++; return ret; } function checkNumbers(number, depth) { if (isVmp) return; if (typeof number == 'undefined') { for (var i = 1; i < 10; i++) { if (digits[i] > 0) { digits[i]--; checkNumbers(i, len - 1); digits[i]++; } } } else if (depth == 0) { if (v % number == 0) { var b = v / number; if (number % 10 != 0 || b % 10 != 0) { var d = countDigits('' + b); if (d[0] == digits[0] && d[1] == digits[1] && d[2] == digits[2] && d[3] == digits[3] && d[4] == digits[4] && d[5] == digits[5] && d[6] == digits[6] && d[7] == digits[7] && d[8] == digits[8] && d[9] == digits[9]) isVmp = true; } } } else { for (var i = 0; i < 10; i++) { if (digits[i] > 0) { digits[i]--; checkNumbers(number * 10 + i, depth - 1); digits[i]++; } } } }