수렴 루프 인덱스 뒤에 수학 원리?

Question

처음으로 포스터 사이트에 있습니다. 내 질문은 다음과 같은 일반적인 수학 원리는 무엇인가?

예를 들어. [3, 3, 3, 3, 4, 6, 3, 4, 4, 5] 및 모두가 제 1 벡터보다 작은 값에서 시작하는 루프 인덱스를 나타내는 다른 벡터. [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!") 

예상 결과 : 제 1 벡터의 값의 곱보다 작거나 같은 양의 정수 값.

실험 결과 : 주어진 샘플 값을 사용하여, 인덱스는 59 루프 후에 수렴한다.

Answer 1

잘 모르겠지만, 단순한 모듈러스 연산처럼 보입니다. 모든 벡터에서 1을 뺄 수 있고 0으로 재설정하면 분석이 더 간단 해집니다. 당신은 counterVec == [a,b,c] == [1,1,1]로 시작하고 각 반복 (v == littleVec)

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

에 계산하고이 벡터는 eqal이 [0,0,0]에 때 중지.

a이 정수 배수 v[0] 번 (모두 1로 시작하므로 -1)이 증가 할 때마다 첫 번째 구성 요소가 0이됩니다. 한 번에 모든 요소가 0이되도록하려면 동일한 문이 참이어야합니다. 해당하는 v[i]의 정수 배가되어야합니다.

그래서 결국은 정수 (n_a, n_b, n_c)의 모든 선택을위한 사실이다

[ (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 

에서 끝낸다. 당신이 공동으로 모든 벡터 성분을 증가하기 때문에, X 등 일부 정수 n_i에 대한

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

것을 단위의 작은 숫자가 있어야합니다. 즉, v[i]으로 나눌 수있는 가장 작은 X이 있습니다. 다른 사람들이 지적했듯이, 이것은 v[i] 중 least common multiple이어야합니다. 귀하의 예제에있는 숫자는 it's 60입니다 (1로 시작하고 0이 아니기 때문에 59 회 반복됩니다). 루프가 멈출 때까지

그래서 당신은

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 

을 뺀 반복으로 시작합니다.