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