求满足正方形顶点数约束的4个不同正整数的最小和

你举的例子6、14、35、15确实完全符合要求！咱们先验证一下：

• 相邻顶点：6&14（gcd=2≠1）、14&35（gcd=7≠1）、35&15（gcd=5≠1）、15&6（gcd=3≠1），全满足不互质；
• 对顶点：6&35（gcd=1）、14&15（gcd=1），全满足互质；
  而且四个数都是不同的正整数，没问题。不过这个组合的总和是70，我们可以找到更小的总和~

寻找最小总和的思路 #

要满足题目的条件，四个数必须都是合数（如果是质数的话，相邻数必须包含这个质数作为因子，但对顶点的数要和它互质就不能包含这个质数，这会导致相邻的两个数都含该质数，它们作为对顶点时gcd≥该质数，矛盾），而且每个数最好是两个不同小质数的乘积——小质数的乘积能让数本身更小，总和也更容易压低。

我们可以用四个最小的质数：2、3、5、7，构造出这样的最优组合：
比如 10（2×5）、15（3×5）、21（3×7）、14（2×7），验证如下：

• 相邻顶点：10&15（gcd=5≠1）、15&21（gcd=3≠1）、21&14（gcd=7≠1）、14&10（gcd=2≠1），全符合不互质要求；
• 对顶点：10&21（gcd=1）、15&14（gcd=1），全符合互质要求；
  四个数都是不同的正整数，总和是 10+15+21+14=60，比你举的例子小10。

为什么这是最小的？ #

如果只用2、3、5三个质数，构造出来的四个数必然会出现对顶点共享质数的情况（比如6、10、15、9，对顶点6和15的gcd=3≠1，不符合要求），所以必须引入第四个质数，而7是最小的可选第四个质数，用它构造的组合已经是最小的可能了。

再尝试替换其中任何一个数为更小的数，要么会破坏相邻不互质的条件，要么会破坏对顶点互质的条件：

• 把21换成9：9和14的gcd=1，相邻互质，不符合；
• 把21换成12：12和10的gcd=2，作为对顶点的12和10不互质，不符合；
• 替换其他数也会出现类似的矛盾。

所以目前能找到的最小总和就是60，对应的四个数可以是10、15、21、14（或者其他满足条件的排列）。

内容的提问来源于stack exchange，提问作者Tom Galle