Programming Praxis

11 Responses to “Vampire Numbers”

1. Josh said

   July 17, 2013 at 9:49 AM

   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

   July 17, 2013 at 10:25 AM

   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

   July 17, 2013 at 6:13 PM

   @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. Dan said

   July 18, 2013 at 2:05 AM

   Java:
5. Josh said

   July 18, 2013 at 8:57 AM

   @eupraxia

   Ah, I didn’t think of that. Good catch!
6. Skuba said

   July 19, 2013 at 5:31 PM

   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()
   
   
7. Gaurav Abbi said

   July 24, 2013 at 4:24 PM

   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
8. Victor said

   August 6, 2013 at 2:55 PM

   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);
   }
   }
   }
   }
   }
9. George said

   January 23, 2014 at 5:51 AM

   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
   
   
10. George said

    January 23, 2014 at 6:02 AM

    *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
    
    
11. Sam Biba said

    October 1, 2019 at 10:50 AM

    Program to check if a number is a Vampire number or not…..

    import java.util.*;
    class Vampire_no
    {
    public static void main(String args[])
    {
    Scanner sc=new Scanner(System.in);
    System.out.print(“\nEnter a number: “);
    int n=sc.nextInt();
    String s=n+””;
    String arr[]=s.split(“”);
    Arrays.sort(arr);
    String arr_[]=new String[arr.length];
    int i=0;
    if(s.length()%2==0)
    {
    for(i=1;i<n;i++)
    {
    if(n%i==0)
    {
    if((i+””).length()==(n/i+””).length())
    {
    arr_=((i+””)+(n/i+””)).split(“”);
    Arrays.sort(arr_);
    if(Arrays.equals(arr,arr_))
    break;
    }
    }
    }
    }
    if(Arrays.equals(arr,arr_))
    System.out.print(“\nIt is a Vampire number.\nFirst fang= “+i+”\tSecond fang= “+n/i);
    else
    System.out.print(“\nIt is not a Vampire number.”);
    }
    }

Leave a Reply

Enter your comment here...

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

Email (required) (Address never made public)

Name (required)

Website

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

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

Cancel

Connecting to %s

Notify me of new comments via email.

Notify me of new posts via email.

Δ