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') True is_anagram('tea', 'tee') False

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

prod('floccinaucinihilipilification') 35334111214198884032311058457421182500

## Comments

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## New Comment