From: Phrogz <gavin@...>
Date: 2007-01-12T02:30:05+09:00
Subject: Re: Word Blender (#108)

Martin DeMello wrote:
> On 1/11/07, James Edward Gray II <james@grayproductions.net> wrote:
> > On Jan 11, 2007, at 7:54 AM, Martin DeMello wrote:
> > > I used a different signature method - I mapped each unique letter in
> > > the target word to a prime, and then used the product of the primes of
> > > all the letters in a word as its signature. That way, a is contained
> > > in b if signature(b) % signature(a) == 0, and you can generate the
> > > signatures via each_byte, array lookup and integer multiplication (no
> > > need for split, sort or string deletion).
> >
> > Very interesting.  I've never seen that before.  I like it.
>
> The numbers overflow 32 bits in the general case, I think, but for
> this restricted problem it works very nicely.

Specifically (I was wondering) you can use 9 primes and still be under
32 bits, 15 primes and still be under 64 bits.

module Enumerable
  def product; inject(){ |n,p| p*n }; end
end

first9 = primes[0..8]
puts "First 9 primes:\n%s\nproduct: %d (%d bits)" %
  [
    first9.inspect,
    first9.product,
    first9.product.to_s(2).length
  ]

first15 = primes[0..14]
puts "\nFirst 15 primes:\n%s\nproduct: %d (%d bits)" %
  [
    first15.inspect,
    first15.product,
    first15.product.to_s(2).length
  ]

#=> First 9 primes:
#=> [2, 3, 5, 7, 11, 13, 17, 19, 23]
#=> product: 223092870 (28 bits)

#=> First 15 primes:
#=> [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]
#=> product: 614889782588491410 (60 bits)

25 primes puts you at 121 bits; 26 primes at 128 bits on the nose.