a question about president's names

In a Facebook conversation, a friend* posed the following question:

How many Presidential names can form a relatively prime group? That is, no letters in a President's name occur in any of the Presidents' names in the group. I've come up with several groups of three, but no groups of four so far.

Now, that's the kind of pointless thing that really appeals to me, so I had to work it out. Spoiler alert: Three is the maximum.

For reference, I have listed the presidential last names below. There are only 39 of them (despite there having been 45 presidents) because six last names -- Adams, Harrison, Johnson, Cleveland, Roosevelt and Bush) have been repeated.

Here's how I worked it out:

First, for simplicity, I am going to use the initialism, "RPG" to mean "relatively prime group," meaning (as described above) a group of names, no two of which have any letters in common.

I didn't want brute force this, so I started by considering vowels.** There are five vowels, not counting Y, and each presidential name has at least one. That means that, before going on, we know that the maximum size of an RPG is five or less. Assuming there is an RPG of five, it has to consist of the following:

1. A name with one or more A, but no other vowels
2. A name with one or more E, but no other vowels
3. A name with one or more I, but no other vowels
4. A name with one or more O, but no other vowels
5. A name with one or more U, but no other vowels

Before going on, let me note that that is a necessary condition, but not sufficient. If, for example, you put together such a group, but two of the names have Ns in them, then that group is still not an RPG.

But examination of the presidential last names (listed below) reveals that there are no presidential last names that have I's but no other vowels. Which means there is no RPG of size five. So now the question is, are there any RPGs of size four?

Repeating the same line of reasoning above, we know that every president's last name has an A, an E, an O or a U. If there is an RPG of size four, it must consist of the following:

1. A name with one or more A, but no E, O or U
2. A name with one or more E, but no A, O or U
3. A name with one or more O, but no A, E or U
4. A name with one or more U, but no A, E or O

From this point on, I brute forced it. Let's see what there is:

Let's call the names that satisfy condition 1, "set A." Set A consists of Adams, Grant, Taft and Harding

Let's call the names that satisfy condition 2, "set E." Set E consists of Tyler, Pierce, McKinley and Kennedy

Let's call the names that satisfy condition 3, "set O." Set O consists of Polk, Lincoln, Johnson, Wilson, Nixon, Ford and Clinton.

Let's call the names that satisfy condition 4, "set U." Set U consists of Bush and Trump.

Simple examination shows us that Adams is not relatively prime with either element of Set U. Neither Grant nor Harding is relatively prime with any element of Set E. So if there is an RPG of size four, it must contain Taft.

The only element of Set U that Taft is relatively prime with is Bush. So if there is an RPG  of size four, it must contain Taft and Bush.

Turning to the elements of Set E, we can confirm that an RPG of size four can't contain Tyler (since Tyler is not relatively prime with Taft, which must be in the RPG of size four. So an RPG of size four must consist of:

• Bush
• Taft
• either Pierce, McKinley or Kennedy
• an element of Set O.

Now, which element of Set O could be that fourth item?

• It can't be Polk because Polk is not relatively prime with Pierce, Kennedy or McKinley
• It can't be Lincoln because Lincoln is not relatively prime with Pierce, Kennedy or McKinley
• It can't be Johnson because Johnson is not relatively prime with Bush
• It can't be Wilson because Wilson is not relatively prime with Bush
• It can't be Nixon because Nixon is not relatively prime with Pierce, Kennedy or McKinley
• It can't be Ford because Ford is not relatively prime with Taft
• It can't be Clinton because Clinton is not relatively prime with Pierce, Kennedy or McKinley

Therefore no element of Set O can be in the RPG of size four, so there does not exist an RPG of size four.

There are, however, several RPG's of size three, including (Bush, Taft, Pierce).

So the maximum size of an RPG is three.

QED.

As an aside, I note that Washington is not relatively prime with any other president's name. FWIW.

Presidential last names (in alphabetical order)

1. Adams
2. Arthur
3. Buchanan
4. Bush
5. Carter
6. Cleveland
7. Clinton
8. Coolidge
9. Eisenhower
10. Fillmore
11. Ford
12. Garfield
13. Grant
14. Harding
15. Harrison
16. Hayes
17. Hoover
18. Jackson
19. Jefferson
20. Johnson
21. Kennedy
22. Lincoln
23. Madison
24. McKinley
25. Monroe
26. Nixon
27. Obama
28. Pierce
29. Polk
30. Reagan
31. Roosevelt
32. Taft
33. Taylor
34. Truman
35. Trump
36. Tyler
37. Van Buren
38. Washington
39. Wilson

*I won't share his name, but it has letters in it
**Credit where due: Blair suggested I look at vowels