程序员的算法趣题Q19: 朋友的朋友还是朋友吗？

1. 问题描述

“六度空间理论”非常有名。大概的意思是1个人只需要通过6个中间人就可以和世界上任何1 个人产生间接联系。本题将试着找出数字的好友（这里并不考虑亲密指数）。

假设拥有同样约数（不包括 1）的数字互为“好友”，也就是说，如果两个数字的最大公约数不是 1，那么称这两个数互为好友。

从1~N 中任意选取一个“合数”，求从它开始，要经历几层好友，才能和其他所有的数产生联系（所谓的“合数”是指“有除 1 以及自身以外的约数的自然数”）。

举个例子，N ＝ 10 时，1~10 的合数有4、6、8、9、10这 5 个。

如果选取的是10，那么10的好友数字就是公约数为2的4、6、8这3个。

而9是6的好友数字（公约数为3），所以10只需要经过2层就可以和 9 产生联系。

如果选取的是6，则只需经过1层就可以联系到4、8、9、10这些数字。

因此N＝10时，无论最初选取的合数是什么，最多经过2层就可以与其它所有数产生联系。

问题：求从1~N中选取7个合数时，最多经过6层就可以与其它所有数产生联系的最小的N。

（不知道是原文如此还是翻译不当）本题的背景描述和最后的问题描述（我认为）都是有明显问题的。

1. 以上第3段话中，“。。。才能和其他所有的数产生联系。。。”，从后文来看，这里应该是“。。。才能和其他所有的合数产生联系。。。”。因为一个合数不可能与非自己因子的素数产生联系。
2. 最后的问题。直接从字面理解的话，N=15，比如说{4,6,8,10,12,14,15}就满足条件。因为题目是要求最多经过6层，只要不超过6层（事实上只有7个数要产生联系也不可能超过6层）即可，并没有说一定必须到达6层。

问题描述应该修改如下：从1~N中选取7个合数，每个数字都可以与其它的6个数字建立联系。求使得7个数字中关系最远的两个数字必须经过6层才能产生联系的最小的N。

2. 解题分析

记两个数要产生联系所需经过的层数为两数之间的“距离”，记为dist(x,y)。题目的要求可以改写为：要求满足“从1~N中任选的7个合数中至少存在两个数，它们之间的距离为6”的条件的最小的N。

由于N1和N7之间的距离为6，则N1与其它5个数之间的距离必然分别为1~5，不失一般性，我们假定N1与N2的距离为1，N1与N3的距离为3，余者依此类推。

可以证明如下：

由于dist(N1,N7)=6，则必然存在1个数与N7距离为1，且与N1距离为5，令该数记为N6；

由于dist(N1,N6)=5，则必然存在1个数与N6距离为1，且与N1距离为4，令该数记为N5；。。。

余者依此类推。

满足条件的N的最小值必然是N1~N7中的最大值，即N=max(N1,N2,…,N7).所以寻找满足条件的最小的N，就是寻找满足条件的最小的7个合数。

由于(N1,N2), (N2,N3), …,(N6,N7)的距离分别为1，要使得这些数最小，它们之间分别应该具有(大于1的)为质数的唯一的公约数，分别记为：gcd(N1,N2)=a, gcd(N2,N3)=b, …, gcd(N6,N7)=f（gcd: Greatest Common Divisor, 表示最大公约数）。因此，N2的最小取值为a*b，N3的最小取值为k3*b*c，…，N6的最小取值为e*f，而N1和N7由于分别可能只有一个好友，它们的取值可以写为k1*a和k7*f。

显而易见，将{a,b,c,d,e,f}取最小的6个素数，然后分别令k1=a, k7=f可以满足以上条件（距离条件，且max(N1,…,N7)最小）。

(好吧，承认失败。本来我是想给出一个严格地证明，但是最后看起来如此显而易见的事情真要给出逻辑严谨的证明似乎并不是一件容易的事情，最后还是得靠一个“显而易见”敷衍了事。只叹：书到用时方恨少，数学学得太潦草) 先搁在这里，后面有机会再回头看能不能给出给严谨的说明。

基于以上讨论可得，本题求解流程如下所示：

3. 代码及测试

# -*- coding: utf-8 -*-
"""
Created on Thu Sep  9 08:27:24 2021

@author: chenxy
"""

import sys
import time
import datetime
import math
# import random
from   typing import List
# from   queue import Queue
# from   collections import deque
import itertools as it

prime = [2,3,5,7,11,13]

globalMin = prime[-1]*prime[-1]

for p in it.permutations(prime):     
    # print(p)

    nums   = [p[0]*p[0]]
    curmax = nums[0]
    for k in range(1,len(p)):
        nums.append(p[k-1]*p[k])
        curmax = max(curmax,nums[-1])
    nums.append(p[-1]*p[-1])    
    curmax = max(curmax,nums[-1])
    
    if globalMin >= curmax:
        globalMin = curmax 
        maxNums   = nums
       
print('globalMin = {0}, {1}'.format(globalMin, maxNums))    

运行结果：