## 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.

Quick and dirty: :)

A faster one-liner:

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.

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?

*Minor correction at method #is_not_divisible_by?

changed it to #is_divisible_by?

Sorry for the clutter