Results 1 to 5 of 5

Thread: Using Prime Numbers to Check if Two Words are Anagrams

  1. #1
    Join Date
    Jun 2008
    Posts
    715

    Thumbs up Using Prime Numbers to Check if Two Words are Anagrams

    Not too long ago I came across a neat (but inefficient) algorithm that uses prime numbers to determine if two words are anagrams. The way it works is simple:

    1. Map each of the 26 English letters to a unique prime number.
    2. Multiply the characters of each word.
    3. Since every integer is either a prime itself OR a unique product of primes, two words are anagrams if their products are the same.

    Example:

    Map A -> 2
    Map E -> 3
    Map R -> 5

    Let's check the two words ear and era:

    For f("ear") = 3 * 2 * 5 = 30, and for f("era") = 3 * 5 * 2 = 30. Since the product is the same, the two words are anagrams. You could try less obvious examples and it will work just the same way.

    Here's my version in Java with more test cases, using my own prime generator.

    Obviously there are more efficient ways of finding anagrams, but I never thought you could use primes to actually make it happen. Regular numbers work on some words but will often give you the wrong answer. With prime numbers, the 'fundamental theorem of arithmetic' necessitates that every time we have an equal product, what we have must be an anagram.

    Pretty cool!
    “Of all the sciences cultivated by mankind, Astronomy is acknowledged to be, and undoubtedly is, the most sublime, the most interesting, and the most useful. For, by knowledge derived from this science, not only the bulk of the Earth is discovered, but our very faculties are enlarged with the grandeur of the ideas it conveys, our minds exalted above their low contracted prejudices.” - James Ferguson

  2. #2
    Join Date
    Feb 2003
    Location
    Depew, NY
    Posts
    11,088
    That is pretty cool.
    Solfe

  3. #3
    Join Date
    Jun 2006
    Posts
    4,652

    Mathematical Games

    Without half trying, I can think of a cryptographic application.

  4. #4
    Join Date
    May 2007
    Location
    Earth
    Posts
    10,036
    Jon Bentley, in Programming Pearls did this by reading the dictionary file, then signing each word. See https://tfetimes.com/wp-content/uplo...nd.pdf#page274

    I'll post my version over the weekend.
    Last edited by swampyankee; 2018-Feb-06 at 09:02 PM.

    Information about American English usage here and here. Floating point issues? Please read this before posting.

    How do things fly? This explains it all.

    Actually they can't: "Heavier-than-air flying machines are impossible." - Lord Kelvin, president, Royal Society, 1895.



  5. #5
    Join Date
    Oct 2009
    Location
    a long way away
    Posts
    10,239
    Quote Originally Posted by John Mendenhall View Post
    Without half trying, I can think of a cryptographic application.
    As long as you don't mind that every word in the decrypted text is an anagram of the original!

    But many encryption techniques do use the fact that it is hard to find the prime factors of large numbers so you may be on to something

Posting Permissions

  • You may not post new threads
  • You may not post replies
  • You may not post attachments
  • You may not edit your posts
  •