## Vampire Numbers

### July 16, 2013

We have today a problem from recreational mathematics.

A vampire number is a number v = x × y such that x and y are not both divisible by 10 and the digits of v consist of the digits of x and the digits of y. The number of digits n in the vampire number must be even, and the number of digits in each of the two fangs x and y must be half the number of digits in v. For instance 1260 = 21 × 60 and 1395 = 15 × 93 are both vampire numbers.

Your task is to write a program that calculates the vampire numbers of n digits. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 11 Responses to “Vampire Numbers”

1. Josh said

Quick and dirty: :)

```def vampire(n):
numbers = xrange(10**(n/2 - 1), 10**(n/2))
for x in numbers:
for y in numbers:
V, X, Y = str(x*y), str(x), str(y)
if X[-1] + Y[-1] != '00' and sorted(V) == sorted(X+Y):
yield x*y
```
```>>> import time
>>> t=time.time();sorted(set(vampire(4)));time.time()-t
[1260, 1395, 1435, 1530, 1827, 2187, 6880]
0.033779144287109375
>>> t=time.time();sorted(set(vampire(6)));time.time()-t
[102510, 104260, 105210, 105264, 105750, 108135, 110758, 115672, 116725, 117067, 118440, 120600, 123354, 124483, 125248, 125433, 125460, 125500, 126027, 126846, 129640, 129775, 131242, 132430, 133245, 134725, 135828, 135837, 136525, 136948, 140350, 145314, 146137, 146952, 150300, 152608, 152685, 153436, 156240, 156289, 156915, 162976, 163944, 172822, 173250, 174370, 175329, 180225, 180297, 182250, 182650, 186624, 190260, 192150, 193257, 193945, 197725, 201852, 205785, 211896, 213466, 215860, 216733, 217638, 218488, 226498, 226872, 229648, 233896, 241564, 245182, 251896, 253750, 254740, 260338, 262984, 263074, 284598, 284760, 286416, 296320, 304717, 312475, 312975, 315594, 315900, 319059, 319536, 326452, 329346, 329656, 336550, 336960, 338296, 341653, 346968, 361989, 362992, 365638, 368550, 369189, 371893, 378400, 378418, 378450, 384912, 386415, 392566, 404968, 414895, 416650, 416988, 428980, 429664, 447916, 456840, 457600, 458640, 475380, 486720, 489159, 489955, 498550, 516879, 529672, 536539, 538650, 559188, 567648, 568750, 629680, 638950, 673920, 679500, 729688, 736695, 738468, 769792, 789250, 789525, 792585, 794088, 809919, 809964, 815958, 829696, 841995, 939658]
3.3001210689544678
>>>
```

A faster one-liner:

```>>> vampire=lambda n: tuple(x*y for x, y in __import__('itertools').combinations(xrange(10**(n/2 - 1), 10**(n/2)), 2) if x%10 + y%10 != 0 and sorted(str(x*y)) == sorted(str(x)+str(y)))
>>> t=time.time();vampire(4);time.time()-t
(1395, 1260, 1827, 2187, 1530, 1435, 6880)
0.020481109619140625
>>> t=time.time();vampire(6);time.time()-t
(108135, ..., 939658)
1.6008110046386719
>>>
```
2. brooknovak said

Here is a brute force C# solution, where a couple of basic tricks have been added to increase efficiency. The mod-9 solution is super smart!

public static void PrintVampireNumbers (int n)
{
if(n <= 0 || n % 2 != 0)
throw new ArgumentException("n");

// Start at max x/y
ulong upperBoundFang = (ulong)Math.Pow (10, n / 2) – 1;
ulong lowerBoundFang = n == 2 ? 0 : (ulong)Math.Pow (10, (n / 2) – 1);

ulong x = upperBoundFang;
ulong y = upperBoundFang;

bool lastLengthTooSmall = false;
bool isXDivisableBy10 = false;
NumberSet xNumbers = new NumberSet(x);
NumberSet yNumbers = new NumberSet();
NumberSet vNumbers = new NumberSet();

while(x >= lowerBoundFang) {
if (y < lowerBoundFang) {
y = upperBoundFang;
x–;
isXDivisableBy10 = x % 10 == 0;
xNumbers.SetNumber (x);
continue;
}
// Ensure both are not devisable
if(isXDivisableBy10) {
if(y % 10 == 0) {
y–;
continue;
}
}

// x and y are not both devisiable by 10
// x and y’s digits are od size n/2
ulong v = x * y;

vNumbers.SetNumber (v);
if(vNumbers.Length != n) {
// Now the vampire number has become too small…
if(lastLengthTooSmall)
break; // last time we reset y and decreased x, doing it again wont achieve anything.
y = 0; // reset y (this will cause x to decrease)
lastLengthTooSmall = true;

} else {
lastLengthTooSmall = false;

yNumbers.SetNumber (y);

Console.WriteLine ("{0} = {1} x {2}", v, x, y);

y–;
}
}
}

private static bool DoesHaveSameNumbers(NumberSet v, NumberSet x, NumberSet y) {
for(int i = 0; i < 10; i++) {
if (v.Numbers [i] != x.Numbers [i] + y.Numbers [i])
return false;
}
return true;
}

private class NumberSet {

private readonly int[] numbers = new int;
private int length;

public int[] Numbers { get { return numbers; } }

public int Length { get { return length; } }

public NumberSet(ulong n = 0) {
SetNumber(n);
}

public void SetNumber(ulong n) {
for (int j = 0; j < 10; j++)
Numbers [j] = 0;
length = 0;

while (n != 0) {
int i = (int)(n % 10);
Numbers[i] ++;
n /= 10;
length++;
}
}
}

3. eupraxia said

@Josh

Your lambda function will fail to find Vampire Numbers where x==y, because itertools.combinations does not generate such pairs.

For example the VN, 165252006144, which is 406512*406512, would be missed.

itertools.combinations_with_replacement should fix the problem, as it allows individual elements to be repeated.

4. Josh said

@eupraxia

Ah, I didn’t think of that. Good catch!

5. Skuba said

Python brute force! 4 digits is quick, 6 takes around 4 minutes, too impatient for anything higher than that.

```#Vampire Numbers

import math
import time

def main():
#Variable Initialization
num_vamp_digits = 0
num_fang_digits = 0
fang1 = 0
fang2 = 0
even_vamp_check = 0
vampire_number = 0
vampire_start = 0
vampire_end = 0
fang_start = 0
fang_end = 0
fang_check = 0
contains = 0
count = 0
start_time = 0

#while loop necessary so if an even number is not entered then a new value can be prompted
while even_vamp_check == 0:

#Get user input
num_vamp_digits = vamp_input()

#Check if entered number is even
even_vamp_check = even_vamp(num_vamp_digits)
start_time = time.time()
print("Calculating...")

#Generate possible vampire numbers
#define range using powers of ten
vampire_start = 10**(num_vamp_digits - 1)
vampire_end = 10**(num_vamp_digits) - 1
vampire_number = vampire_start
num_fang_digits = num_vamp_digits //2
fang_start = 10**(num_fang_digits - 1)

while vampire_number <= vampire_end:
fang1 = fang_start
fang_end = math.sqrt(vampire_number)
while fang1 <= fang_end:
if vampire_number % fang1 == 0:
fang2 = vampire_number // fang1
if len(str(fang2)) == num_fang_digits:
fang_check = divisible(fang1,fang2)
if fang_check == 1:
contains = contains_check(vampire_number,fang1,fang2)
if contains == 1:
print("\nVampire Number:",vampire_number,"\nFang 1:",fang1,"\nFang 2:",fang2)
count = count+1
fang1 = fang1 + 1
vampire_number = vampire_number + 1

print("\nAnalysis Complete\n")
print(count,"vampire numbers were found with",num_vamp_digits,"digits.")

time_total = time.time()-start_time
print("This took",int(time_total//60),"minutes",int(time_total%60),"seconds")

#User Input
#takes in num_vamp_digits
#Returns user defined value to main
def vamp_input():
n=int(input("\n\nHow many digits would you like the vampire number to have?\n"))
return n

#checks if the user entered number of digits is even
#Takes in num_vamp_digits provided by user
#returns 1 if true, 0 if false
def even_vamp(num_vamp_digits):
if num_vamp_digits%2==0:
return 1
else:
print("The number of digits must be even, please enter another value.")
return 0

#Divisibility check (both fang1 and fang 2 can't be divisible by ten)
#Takes in fang 1 and fang 2 values
#returns 1 if both are not divisible by ten, 0 if both are
def divisible(fang1,fang2):

if fang1%10==0:
if fang2%10==0:
return 0
else:
return 1
else:
return 1

#Contains digits check, checks values of each digit in fangs are present in vamp number
#takes in fang 1, fang 2, and vampire number
#returns 1 if true, 0 if false
def contains_check(vampire_number,fang1,fang2):
vamp_list = []
fang_list = []

i=0
j=0

while i < len(str(vampire_number)):
vamp_list.append(str(vampire_number)[i])
i=i+1
vamp_list.sort()
while j < len(str(fang1)):
fang_list.append(str(fang1)[j])
fang_list.append(str(fang2)[j])
j=j+1
fang_list.sort()
k=0
while k < len(str(vampire_number)):
if vamp_list[k]==fang_list[k]:
k=k+1
else:
return 0
return 1

#Run main
main()

```
6. Gaurav Abbi said

————————————————–
import Data.List

vn :: Integer->[(Integer,Integer,Integer)]
vn n = if odd n
then []
else
let split = fromIntegral(n `div` 2)
(start, end) = (10^(split-1), (10^split)-1)
in getVampires [start..end]

getVampires :: [Integer]->[(Integer,Integer,Integer)]
getVampires ns = [(x,y,x*y)|x<-ns,y y , isVampire(x,y)]

isVampire (x,y)
| (x `mod` 10 == 0) && (y `mod` 10 == 0) = False
| sort (show x ++ show y) /= sort (show (x*y)) = False
| otherwise = True

7. Victor said

Quick and dirty solution in C#!

namespace VampireNumbers
{
class Program
{
private static void isVampire(int number, int digits)
{
int start = ((digits + 1) / 2) – 1;

for (int x = (int)Math.Pow(10, start); x < (int)Math.Pow(10, start + 1); ++x)
{
if (number % x == 0)
{
int div = number / x;

if (div.ToString().Length == start + 1 && (div%10 != 0 || x%10 != 0))
{
Console.WriteLine(number + " = " + x + " x " + number / x);
}
}
}
}

static void Main(string[] args)
{
//Must be even.
int n = 4;

//Cycle through all the possible number of digits vampire number can have.
for (int i = 1; i < n; i += 2)
{
for (int v = (int)Math.Pow(10, i); v < (int)Math.Pow(10, i + 1); ++v)
{
isVampire(v, i);
}
}
}
}
}

8. George said

Using Ruby.
With a little monkey patching for legibility

Fun exercise but my code is too slow, any suggestions on how I can make it faster?

```
def digits_of number
number.to_s.chars.map(&:to_i)
end

class Numeric
def has_same_digits_as? number
self.to_s.split('').sort == number.to_s.split('').sort
end

def is_not_divisible_by? number
!(self%number == 0)
end

def possible_fangs
digits = digits_of(self)
fang_size = digits.size/2

digits.permutation(fang_size).to_a.map do |fang_array|
fang_array.join('').to_i
end.keep_if{|fang| fang.to_s.length == fang_size}.uniq
end

def possible_products fangs
fangs.permutation(2).to_a.keep_if do |fang_pair|
digits_in_fangs = fang_pair.join('').to_i

digits_in_fangs.has_same_digits_as?(self) && !fang_pair.all?{|fang| fang.is_not_divisible_by? 10}

end.map{|fang_pair| fang_pair.inject(:*)}
end

def vampire?
return false unless digits_of(self).size.even?
possible_products(possible_fangs).include? self
end

end

def all_vampire_numbers_of_size digits
collection = []
lower_bound = 10**(digits-1)
higher_bound = 10**(digits)
(lower_bound...higher_bound).each do |number|
collection << number if number.vampire?
end
collection
end

```
9. George said

*Minor correction at method #is_not_divisible_by?
changed it to #is_divisible_by?
Sorry for the clutter

```
def digits_of number
number.to_s.chars.map(&:to_i)
end

class Numeric
def has_same_digits_as? number
self.to_s.split('').sort == number.to_s.split('').sort
end

def is_divisible_by? number
self%number == 0
end

def possible_fangs
digits = digits_of(self)
fang_size = digits.size/2

digits.permutation(fang_size).to_a.map do |fang_array|
fang_array.join('').to_i
end.keep_if{|fang| fang.to_s.length == fang_size}.uniq
end

def possible_products fangs
fangs.permutation(2).to_a.keep_if do |fang_pair|
digits_in_fangs = fang_pair.join('').to_i

digits_in_fangs.has_same_digits_as?(self) && !fang_pair.all?{|fang| fang.is_divisible_by? 10}

end.map{|fang_pair| fang_pair.inject(:*)}
end

def vampire?
return false unless digits_of(self).size.even?
possible_products(possible_fangs).include? self
end

end

def all_vampire_numbers_of_size digits
collection = []
lower_bound = 10**(digits-1)
higher_bound = 10**(digits)
(lower_bound...higher_bound).each do |number|
collection << number if number.vampire?
end
collection
end

all_vampire_numbers_of_size 4 #=>[1260, 1395, 1435, 1530, 1827, 2187, 6880] after like 2-3 minutes

```
10. Sam Biba said

Program to check if a number is a Vampire number or not…..

import java.util.*;
class Vampire_no
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
System.out.print(“\nEnter a number: “);
int n=sc.nextInt();
String s=n+””;
String arr[]=s.split(“”);
Arrays.sort(arr);
String arr_[]=new String[arr.length];
int i=0;
if(s.length()%2==0)
{
for(i=1;i<n;i++)
{
if(n%i==0)
{
if((i+””).length()==(n/i+””).length())
{
arr_=((i+””)+(n/i+””)).split(“”);
Arrays.sort(arr_);
if(Arrays.equals(arr,arr_))
break;
}
}
}
}
if(Arrays.equals(arr,arr_))
System.out.print(“\nIt is a Vampire number.\nFirst fang= “+i+”\tSecond fang= “+n/i);
else
System.out.print(“\nIt is not a Vampire number.”);
}
}