I've previously written a nice word puzzle script, which takes in a huge list of words, and creates a list of anagram "siblings". One of the special functions is to find, for each word length, the largest anagram set of siblings.
OK, I thought that would be a good little puzzle program to write. I'm sure there's an easier way to figure this on paper though, waiting for y'all to clue me in. The first few elements led me to the following:
Just for fun, I programmed up a little script. Using a suitable underlying GMP library for Euler's totient function, it checked up to 10 million in 13 seconds, with a result of 60.793% distinct pairs relatively prime.