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

About these ads

Pages: 1 2

10 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

    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

  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
    
    

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Follow

Get every new post delivered to your Inbox.

Join 635 other followers

%d bloggers like this: