Using prime numbers to determine if two words are anagrams

(1 comment)

A recent tweet by Fermat's Library noted that the Fundamental theorem of arithmetic provides a novel (if inefficient) way of determining whether two words are anagrams of one another.

The Fundamental theorem of arithmetic states that every integer greater than 1 is either a prime number itself or can be represented as the unique product of prime numbers.

First, one assigns distinct prime numbers to each letter (e.g. a=2, b=3, c=5, ...). Then form the product of the numbers corresponding to each letter in each of the two words. If the two products are equal, the words are anagrams. For example,

'cat': $5 \times 2 \times 71 = 710$

'act': $2 \times 5 \times 71 = 710$

The following code implements and tests this algorithm.

from functools import reduce
a = 'abcdefghijklmnopqrstuvwxyz'
p = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67,
     71, 73, 79, 83, 89, 97, 101]
d = dict(zip(a, p))

def prod(s):
        return reduce((lambda n1, n2: n1*n2), [d[lett] for lett in s])

def is_anagram(s1, s2):
        return prod(s1) == prod(s2)

Here, d is a dictionary mapping the letters to their primes. The functools.reduce method applies a provided function cumulatively to the items of a sequence.

To see that it works, try:

is_anagram('cat', 'act')

is_anagram('tea', 'tee')

Note that for longer words the products formed get quite large:

Current rating: 5


Comments are pre-moderated. Please be patient and your comment will appear soon.

Dominik Stańczak 1 year, 5 months ago

This is utterly dreadful and I love it. Clever idea!

Link | Reply
Currently unrated

New Comment


required (not published)