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 5 years, 1 month ago

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

Link | Reply## New Comment