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.

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