What is the general mathematics principle behind the following problem?
Take a vector containing integers e.g. [3, 3, 3, 3, 4, 6, 3, 4, 4, 5], and another vector representing loop indices that all begin at a value less than the first vector e.g. [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]. When each loop index is equal to its corresponding index in the first vector, reset it to one. Program ends when all indices are equal to one.
This seems like integer factorization, but I don't know how to state this generally. What principle is at work here? What is a more computationally efficient way to achieve the same result?
Thanks in advance.
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!")
Expected result: a positive integer value that is less than or equal to the product of the first vector's values.
Experimental result: with the sample values given, the indices converge after 59 loops.
I'm not sure, but it looks like simple modulo arithmetics to me. You can subtract 1 from all vectors (and do resetting to zero) to make it simpler to analyze. You start with counterVec == [a,b,c] == [1,1,1] and calculate in each iteration (where v == littleVec)
[ (a+1)%v[0], (b+1)%v[1], (c+1)%v[1] ]
And you stop when this vector is eqal to [0,0,0].
Clearly, the first component hits zero every time a was incremented an integer multiple of v[0] times (minus one, because you start with all ones). For all elements to hit zero at once, the same statement must be true: integer multiple of the corresponding v[i].
So eventually you end up at
[ (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
Which is true for every choice of the integers (n_a, n_b, n_c). Since you increment all vector components jointly, there must be a smallest number of increments X such that
X = n_a * v[0]
= n_b * v[1]
= n_c * v[2]
for some integers n_i. In other words, there will be a smallest X that is divisible by all of v[i]. As others have pointed out, this must be the least common multiple of all v[i]. For the numbers in your example, it's 60 (you see 59 iterations because you start with 1 and not with 0).
So if you start with
littleVec = ([5, 3, 7, 8, 10, 8, 5, 7, 5, 7])
lcm([5, 3, 7, 8, 10, 8, 5, 7, 5, 7]-1) = 252
minus one iterations until the loop stops.