寻求4元Ducci序列最大迭代次数及对应最小和四元组解法

问题定义 #

在正方形（活动正方形）的四个角分配四个非负整数，每一步操作如下：

• 将每条边两端点数字的绝对值差分配给该边中点
• 将四个新中点连接成与原正方形倾斜45度的新正方形，作为新的活动正方形
  重复上述步骤直到活动正方形四个角全为0。

定义f(a,b,c,d)为从顺时针排列的(a,b,c,d)开始，整个过程中绘制的正方形总数：

• 示例：从(10,6,3,1)开始，序列为：

  (4,3,2,9)
  (1,1,7,5)
  (0,6,2,4)
  (6,4,2,4)
  (2,2,2,2)
  (0,0,0,0)
  过程结束，故f(10,6,3,1)=7；显然f(0,0,0,0)=1。

目标任务 #

考虑集合S={(a,b,c,d)|a,b,c,d为整数且0≤a,b,c,d≤10,000,000}，M为f在S上的最大值。需要找到S中满足f(a,b,c,d)=M且a+b+c+d最小的(a,b,c,d)，输出格式为分号分隔的列表（如10;6;3;1）。

当前尝试 #

• 最初用Excel求解器，结果正确但计算量过大，设备无法承受。
• 编写了Python代码生成和验证Ducci序列，但不知如何求解目标问题，代码如下：

def ducci_sequence(*ns):
    while True:
        yield ns
        ns = tuple(abs(ns[i - 1] - ns[i]) for i in range(len(ns)))

def ducci(*ns):
    known = set()
    for ns in ducci_sequence(*ns):
        print(ns)
        if ns in known or set(ns) == {0}:
            break
        known.add(ns)
    return len(known) + 1
print(ducci(0, 24, 68, 149), "steps")

代码输出：

(0, 24, 68, 149)
(149, 24, 44, 81)
(68, 125, 20, 37)
(31, 57, 105, 17)
(14, 26, 48, 88)
(74, 12, 22, 40)
(34, 62, 10, 18)
(16, 28, 52, 8)
(8, 12, 24, 44)
(36, 4, 12, 20)
(16, 32, 8, 8)
(8, 16, 24, 0)
(8, 8, 8, 24)
(16, 0, 0, 16)
(0, 16, 0, 16)
(16, 16, 16, 16)
(0, 0, 0, 0)
17 steps

请求指导 #

希望得到求解该问题的思路和方法，找到满足条件的(a,b,c,d)。

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