## Vampire numbers

Richard Suchenwirth 2012-11-01 - It has been a long time since my last fun project, but on the day after Halloween, which is a holiday in my part of the country, I finally did it again - some code to research vampire numbers.

"In mathematics, a vampire number (or true vampire number) is a composite natural number v, with an even number of digits n, that can be factored into two integers x and y each with n/2 digits and not both with trailing zeroes, where v contains precisely all the digits from x and from y, in any order, counting multiplicity. x and y are called the fangs.

For example: 1260 is a vampire number, with 21 and 60 as fangs, since 21 × 60 = 1260." Quote from [http://en.wikipedia.org/wiki/Vampire_number]

Here is what I coded:

```#!/usr/bin/env tclsh
set usage {
usage: vampire.tcl max ?p?
list all true vampire numbers with factors < max to stdout.
If second argument is "p", also list pseudovampire numbers.
}
proc main argv {
set max [lindex \$argv 0]
if {\$max eq ""} {puts stderr \$::usage; exit 1}
set popt [string equal [lindex \$argv 1] p]
for {set i 2} {\$i < \$max} {incr i} {
for {set j \$i} {\$j < \$max} {incr j} {
if {[vampire \$i \$j \$popt]} {
set p [expr {\$i * \$j}]
puts [format "%8d = %4d * %4d" \$p \$i \$j]
}
}
}
}
proc vampire {i j popt} {
if {!\$popt && [string length \$i] != [string length \$j]} {
return 0
}
if {[string index \$i end] eq "0" && [string index \$j end] eq "0"} {
return 0
}
set p [expr {\$i * \$j}]
if {[lsort [split \$p ""]] eq [lsort [split \$i\$j ""]]} {return 1}
return 0
}
main \$argv```

Usage examples:

``` ~ \$ ./vampire.tcl 100
1395 =   15 *   93
1260 =   21 *   60
1827 =   21 *   87
2187 =   27 *   81
1530 =   30 *   51
1435 =   35 *   41
6880 =   80 *   86
~ \$ ./vampire.tcl 100 p # also show pseudo-vampire numbers, where factors may be of unequal length
153 =    3 *   51
126 =    6 *   21
688 =    8 *   86
1395 =   15 *   93
1260 =   21 *   60
1827 =   21 *   87
2187 =   27 *   81
1530 =   30 *   51
1435 =   35 *   41
6880 =   80 *   86
~ \$```

The code is not blindingly fast, with max=1000 it takes about 15 sec on my netbook. I tried to optimize it by avoiding the shimmering of i and j in the vampire function, by using extra local variables for string operations only, but it had no big effect (somewhat 14.5 sec for max=1000), so I reverted the code back to the simple way it is now.

arjen - 2012-11-01 12:13:49

On my laptop "vampire.tcl 1000" took some 3.3 seconds only, not all that bad.

AMG: 2.17 seconds here on my laptop. :^) I don't think having a 64-bit CPU or multiple cores would help with this task, simply fast RAM and CPU clock.

AM It is after all some 1/2 million pairs of numbers you are testing.

HolgerJ

``` real 0m6.022s
user 0m6.000s
sys  0m0.012s```

on my desktop computer which is not very fast.

JM Nice to hear from you Richard! I was missing you here on the wiki.

RS Hi to all, and thanks for joining in the benchmarking! I have just now found an optimization that makes both the code simpler (9 "words" instead of 13), and faster (from 15.565 sec to 14.760 sec): I changed

`    if {[string index \$i end] eq "0" && [string index \$j end] eq "0"} {`

to

`    if {[string match *0 \$i] && [string match *0 \$j]} {`

This is how I like it ;^)

Oh, and I haven't dropped out of the Tcl scene - at work, I still use Tcl almost every day, and check the Wiki whenever I need something special...

 Category Mathematics