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.

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 574 other followers

%d bloggers like this: