## Vampire Numbers

### July 16, 2013

The easy solution simply generates all possible n/2-digit numbers and checks the digits of each; here’s the version for 4-digit vampire numbers, which uses the `digits` function from the Standard Prelude:

```(do ((x 10 (+ x 1))) ((= x 100))   (do ((y x (+ y 1))) ((= y 100))     (when (equal? (sort < (digits (* x y)))                   (sort < (append (digits x) (digits y))))       (display x) (display " ") (display y)       (display " ") (display (* x y)) (newline))))```

That’s an O(n2) algorithm, and while it works fine for 4-digit vampires, it quickly gets slow as n increases. It also doesn’t implement the requirement that both x and y may not be divisible by 10, but that doesn’t matter for 4-digit vampires.

Pete Hartley discovered that if x × y is a vampire number, then x × y = x + y (mod 9). With a little bit of work you can see that the congruence (x mod 9, y mod 9) must be in one of six classes: {(0,0), (2,2), (3,6), (5,8), (6,3), (8,5)}, which greatly reduces the effort needed for the search:

```(define (vampires n)   (define (next-mod n r)     (let ((x (+ n r -1)))       (if (< x n) (+ x 9) x)))   (let ((lo (expt 10 (- (/ n 2) 1)))         (hi (expt 10 (/ n 2)))         (vs (list)))     (do ((i (next-mod lo 0) (+ i 9))) ((<= hi i))       (do ((j i (+ j 9))) ((<= hi j))         (if (vampire? i j) (set! vs (cons (* i j) vs)))))     (do ((i (next-mod lo 2) (+ i 9))) ((<= hi i))       (do ((j i (+ j 9))) ((<= hi j))         (if (vampire? i j) (set! vs (cons (* i j) vs)))))     (do ((i (next-mod lo 3) (+ i 9))) ((<= hi i))       (do ((j (+ i 3) (+ j 9))) ((<= hi j))         (if (vampire? i j) (set! vs (cons (* i j) vs)))))     (do ((i (next-mod lo 5) (+ i 9))) ((<= hi i))       (do ((j (+ i 3) (+ j 9))) ((<= hi j))         (if (vampire? i j) (set! vs (cons (* i j) vs)))))     (do ((i (next-mod lo 6) (+ i 9))) ((<= hi i))       (do ((j (+ i 6) (+ j 9))) ((<= hi j))         (if (vampire? i j) (set! vs (cons (* i j) vs)))))     (do ((i (next-mod lo 8) (+ i 9))) ((<= hi i))       (do ((j (+ i 6) (+ j 9))) ((<= hi j))         (if (vampire? i j) (set! vs (cons (* i j) vs)))))     (unique = (sort < vs))))```

The effort will be reduced by a factor of 9 in both dimensions, so O(n2 / 81). Here’s the `vampire` function:

```(define (vampire? x y)   (let ((z (* x y)))     (if (not (= (modulo (* x y) 9) (modulo (+ x y) 9))) #f       (if (and (zero? (modulo x 10)) (zero? (modulo y 10))) #f         (equal? (sort < (digits z))                 (sort < (append (digits x) (digits y))))))))```

Here are some examples:

```> (vampires 4) (1260 1395 1435 1530 1827 2187 6880) > (vampires 6) (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) > (time (length (vampires 8))) (time (length (vampires 8)))     546 collections     10655 ms elapsed cpu time, including 30 ms collecting     10658 ms elapsed real time, including 40 ms collecting     4596153168 bytes allocated, including 4597278064 bytes reclaimed 3228```

You can run the program at http://programmingpraxis.codepad.org/klfVuDDf. If you are interested in vampire numbers, I recommend Jens Anderson’s page at http://users.cybercity.dk/~dsl522332/math/vampires/.

Pages: 1 2

### 8 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);

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++;
}
}
}

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);
}
}
}
}
}