The challenge:
There is a surprisingly original algorithm for deciding whether two words are anagrams of each other or not, based on prime numbers. Each letter of the alphabet is assigned to a unique prime number, for example A=2, B=3, C=5, D=7, E=11, …, Y=97 and Z=101. The associated prime numbers of each letter are multiplied by each other, from both words. If and only if both multiplications yield the same result, the words are anagrams.

For example:
– DEKIMO = 7x11x31x23x41x47 = 105794227
– MEDIKO = 41x11x7x23x31x47 = 105794227
– MEDEME = 11³x41²x7 = 15661877

It is very easy to prove that this algorithm always works. One direction (“anagrams give the same product”) is obvious because of the commutativity of multiplication. The other direction (“if result is equal means they are anagrams”) follows from the fundamental theorem of arithmetic that every natural number has a unique decomposition into prime factors.

However, for longer words, this algorithm quickly runs into problems. The multiplications lead to large numbers that don’t fit into integer data types in a software implementation. You can delay the problems by associating frequent letters with the smaller prime numbers. Or you can take the logarithm, which turns multiplications into additions and large products into more manageable sums. However, none of these variations leads to a really efficient implementation.

The goal of this contest is to do better than the above, and to design a fast and scalable algorithm to determine whether two long strings of letters are anagrams of each other or not. This algorithm should be implemented on the Arduino that is provided for free by Dekimo.