## 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(*n*^{2}) 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(*n*^{2} / 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/.

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