Vampire Numbers! Part 2


How many vampire numbers are there?
How long does it take to find them?
How often do you find them?
How fast does the number of numbers to search through increase?

Thinking about the topic immediately raises a lot of questions. Here is a table that answers some of these questions.

Vampire Numbers - John Childs
Digits in vampire number Numbers in range
(i.e. 10 to 99 = 90 numbers
Number of multiplications to be performed Number of vampire numbers Per cent of total

Multiplication rate
(#'s/hr)*
Time to
search all
possibilities
Time increase factor
4904,09570.229,000,0000.5 sec.
6900405,4501480.0416,000,0001.5 min180x
89,00040,504,50032430.00814,000,0002.5 hours100x
1090,0004,050,045,000108,5770.0036,500,00026 days250x
12900,000405,000,450,000??5,500,0008.4 years120x
149,000,0004.05 E+13..3,600,0001,3000 years150x
1690,000,0004.05 E+15.....
18900,000,0004.05 E +17.....
209,000,000,0004.05 E +19..2,000,0002.3 billion years.
229 E +104.05 E +21.....
249 E +11......
269 E +12......
289 E +13......
309 E + 14......
329 E + 15......
349 E + 16......
369 E + 17......
389 E + 18......
409 E + 19...600,0001 E +30 years.
509 E +24...365,0002 E +40 years.
609 E +29...300,0002 E +50 years.
100 9 E +49...100,0005 E +90 years.

* These times are approximate, and are measured using a Turbo Pascal program running on a Pentium 133 MHz. (IBM ThinkPad 365 XD, 1995 vintage!)

Notice that there is a big drop in the multiplication rate between 4 digits and 6 digits. This is because integer variables can be used to search for 4 digit vampire numbers, and longinteger variables need to be used to search for 6 digit vampire numbers. Integer variables can store numbers in the range -32,768 to + 32,767. (+/- 2 raised to the 15th power - the reason for this number is that the biggest 16 bit binary number you can have is 1111111111111111 which equals 32,768 in decimal, or base 10.) Since a four digit number only goes to 9,999 integer variables are fine, and the computer is very fast in processing them! For 6 digit numbers (largest = 999,999) and 8 digit numbers, (largest = 99,999,999) the longinteger variable stores numbers in the range -2,147,483,648 to + 2,147,483,647. To get larger integer values, two 16 bit binary numbers are used, and 2 raised to the 30th power is 2,147,483,648. Since this is a ten digit number, you might think it could be used to multiply two 5 digit numbers to get a 10 digit result. But notice that it can not store the larger numbers up to 9,999,999,999 since it can't go beyond 2 billion. So it is only useful to get 8 digit products, to a maximum value of 99,999,999.

Notice again, that there is a big drop in the multiplication rate when we move to 10 digit products. At this point, we are using numbers up to 9,999,999,999 which exceeds the computer's integer capacity entirely. At this point, the computer can no longer supply us with numeric variables to do the job, and we have to do it manually. It's not often that the computer actually lets us down! But we really have exceeded the computer's ability to do the arithmetic in which we are interested. At this point, all our nubmers are actually arrays of numbers. A 10, 12 or more digit number is stored with digits, each in its own cell, in an array with 10 or 12 elements.
Such an array can be visualized like so:

Num1( ) 845289035173

The QuickBASIC code to display such a number would look like this:     

FOR N = 1 to 12
  PRINT Num1(N);
NEXT N



To add the results of the individual multiplications,we need
a two dimensional array to store the intermediate results.
You can picture the multiplication job as shown:




Using arrays dimensioned up to large values, we can now work
with numbes up to a size where our next restriction would be
the computers RAM! And we could exceed that by writing our
arrays to disk files. But we are getting ahead of ourselves. :-)








A final array can hold the sum of the vertical columns of the
two dimensional array, just as you would do if you did the
calculation by hand. Don't forget another array to store the
results of whether or not there is a carry and what its value is!


Num1( ) 123456654321


Num2( ) 912345918177


............864196580247
...........8641965802470
..........12345665432100
.........987653234568000
........1234566543210000
......111110988888900000
......617283271605000000
.....4938266172840000000
....37036996296300000000
...246913308642000000000
..1234566543210000000000
111110988888900000000000

















112635174641553239492817


Vampire Numbers - Information Summary


Back