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.
Programming Praxis 
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*yA 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 >>>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);
if (DoesHaveSameNumbers (vNumbers, xNumbers, yNumbers))
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[10];
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++;
}
}
}
@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.
Java:
@eupraxia
Ah, I didn’t think of that. Good catch!
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()a haskell solution
————————————————–
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
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);
}
}
}
}
}
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*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 minutesProgram 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.”);
}
}