收敛循环索引背后的数学原理？

Question

下列问题背后的一般数学原理是什么？

取一个包含整数的向量，例如[3, 3, 3, 3, 4, 6, 3, 4, 4, 5] 和另一个表示循环索引的向量，它们都以小于第一个向量的值开始，例如[1, 1, 1, 1, 1, 1, 1, 1, 1, 1]。当每个循环索引等于其在第一个向量中的对应索引时，将其重置为 1。当所有索引都等于 1 时程序结束。

这看起来像是整数分解，但我不知道如何笼统地表述它。什么原则在这里起作用？获得相同结果的计算效率更高的方法是什么？

提前致谢。

import numpy as np

unityVec = np.ones((10), dtype=np.int)  # create a vector of ones
counter = 1                             # initialize counter

counterVec = np.ones((10), dtype=np.int) # initialize counter array
counterVec = counterVec + 1              # make counter array > ones array

littleVec = ([3, 3, 3, 3, 4, 6, 3, 4, 4, 5])   # loop reset values

while not (np.array_equal(unityVec, counterVec)):  # compare counter to ones vector 

    counterVec = counterVec + 1

    for i in range(10):
        if counterVec[i] == littleVec[i]:
            counterVec[i] = 1  # reset counterVec element to 1 once it hits limit
            #print("Counter: ", counter, "\tIndex: ", i, "\tcounterVec: ", counterVec, "\tlittleVec: ", littleVec)

    counter = counter + 1


print("Indices converged after", counter-1, "iterations!")

预期结果：小于或等于第一个向量值的乘积的正整数值。

实验结果：给定样本值，59次循环后指标收敛。

Answer 1

我不确定，但对我来说它看起来像是简单的模运算。您可以从所有向量中减去 1（并重置为零）以使其更易于分析。您从 counterVec == [a,b,c] == [1,1,1] 开始并在每次迭代中计算（其中 v == littleVec）

[ (a+1)%v[0], (b+1)%v[1], (c+1)%v[1] ]

当这个向量等于 [0,0,0] 时你就停止了。

很明显，每次 a 递增 v[0] 的整数倍时，第一个分量都为零（减一，因为你从全 1 开始）。对于所有元素一次归零，相同的语句必须为真：相应 v[i].

的整数倍

所以最终你会在

[ (1 + n_a * v[0] - 1)%v[0],  
  (1 + n_b * v[1] - 1)%v[1],  
  (1 + n_c * v[2] - 1)%v[2] ] == [ 0, 0, 0 ]
#  ^ initial value  ^ correction for the initial value

整数 (n_a, n_b, n_c) 的每个选择都是正确的。由于您联合递增所有矢量分量，因此必须有最小数量的递增 X 使得

X = n_a * v[0]
  = n_b * v[1]
  = n_c * v[2]

对于一些整数 n_i。换句话说，将有一个最小的 X 可以被所有 v[i] 整除。正如其他人指出的那样，这一定是 least common multiple of all v[i]. For the numbers in your example, it's 60（您看到 59 次迭代，因为您从 1 而不是 0 开始）。

所以如果你从

开始

littleVec = ([5, 3, 7, 8, 10, 8, 5, 7, 5, 7])

You will get

lcm([5, 3, 7, 8, 10, 8, 5, 7, 5, 7]-1) = 252

减去一次迭代直到循环停止。

收敛循环索引背后的数学原理？

Math principle behind converging loop indices?

python

numpy

factorization