Problem of the Week 1239

Uniquely Unique Partitions

For a partition p of a positive integer N into k positive integer parts, the "graph" of p has a vertex for each entry in p and an edge between two vertices if the corresponding entries of p have a common divisor greater than 1.

Example: The graph of the partition 10 = 4 + 2 + 2 + 1 + 1 has 5 vertices and 3 edges. A partition of N is "recoverable" if it is determined by N and the number of edges in its graph. For example, 2 + 2 is recoverable because it is the only partition of 4 whose graph has one edge. Also, 2 + 2 is the only recoverable partition of 4, since the edge count is 0 for each of 3 + 1, 2 + 1 + 1, 1 + 1 + 1 + 1, and 4.

What is the largest N for which there is a unique recoverable partition of N?

Source: F. Barrera (Bogota, Colombia), B. Recaman (Bogota, Colombia), and S. Wagon.

[View the solution]