Finding when list of numbers reach periodicity given known values

Question

I'm trying to figure out when numbers reach "periodicity" given known values. I've included an example below with image:

I have known sizes (100, 75, and 50) that I would like to know how many times I would need to repeat each item for all the sizes to line up or be periodic. Does anyone know of a formula for this or how I can go about figuring this out?

As you can see to reach periodicity: 
I need to repeat 100 3 times 
I need to repeat 75 4 times 
I need to repeat 50 6 times 

PS: This is just a simple example the numbers could be decimals like 1.29. and include several more numbers. I will also be converting the formula to octave which is like matlab.

Answer 1

It is called LCM - Least Common Multiplier.

In your example, $LCM(50,75,100)=300$, hence:

• $ 50$ needs to repeat $\frac{300}{ 50}=6$ times
• $ 75$ needs to repeat $\frac{300}{ 75}=4$ times
• $100$ needs to repeat $\frac{300}{100}=3$ times

In order to compute $LCM(50,75,100)$:

• $50=2\cdot5\cdot5$
• $75=3\cdot5\cdot5$
• $100=2\cdot2\cdot5\cdot5$

Of each prime factor, we need to take an amount equivalent to the maximum number of times it occurs in any of the given numbers:

• $\color\red2$ appears at most $\color\green2$ times
• $\color\red3$ appears at most $\color\green1$ time
• $\color\red5$ appears at most $\color\green2$ times

Hence $LCM(50,75,100)=\color\red2^\color\green2\cdot\color\red3^\color\green1\cdot\color\red5^\color\green2=300$.

Answer 2

The answer is to find the least common multiple of your given numbers. For instance, in the case of $100, 75, 50$, the least common multiple is $300$. Since $300/100 = 3$, you need $3$ lots of $100$. Since $300/75 = 4$, you need $4$ lots of $75$, etc.

This cannot be done in general. For instance, $1$ and $\pi$ have no common multiple. If all of your numbers are rational, however, then they will have a least common multiple. I'm not sure what the most efficient algorithm for finding the LCM is. Try consulting the CS stack exchange or Wikipedia for more information.

Answer 3

note that both Matlab and Octave have a lcm function, but the Matlab version only accepts a pair of values, while the Octave one supports a list of inputs. The function only accepts integers, however, as it likely makes use of the simplest direct algorithm LCM(a,b) = a*b/gcd(a,b). in fact if you call lcm with decimal valued numbers in Octave, you get an error in a sub-call to gcd.

>> lcm(1.4,6)
error: gcd: all values must be integers
error: called from
lcm at line 49 column 7

depending on types of numbers you'll be dealing with, and the type of precision you're going for, it is possible to run gcd on decimals by 'scaling them to integers', as found here. this works well for 'small' decimals with only a few digits. i.e.,

>> lcm(10*1.4,10*6)/10
ans =  42

>> c= 1e3;
>> lcm(c*1.424,c*5.432)/c
ans =  966.896000000000

note that you can run into data limits if you try to go to an arbitrary number of decimal places, and you must have rational numbers. That said, at least Octave appears to be using double precision arithmetic to calculate things, even though it checks for integers on the input. It 'works' for values larger than you'd be able to store in an int32:

>> intmax('uint32')
ans = 4294967295

>> c=1e12
c =  1000000000000

>> a1 = 6*c
a1 = 6000000000000

>> a2 = 4*c
a2 = 4000000000000

>> lcm(a1,a2)
ans = 12000000000000

>> a1=floor(pi*c)
a1 =  3141592653589

>> a2=floor((pi+1)*c)
a2 =  4141592653589

>> lcm(a1,a2)
ans =   1.30111970546734e+025

>> ans/a1
ans =  4141592653589

note that you will eventually run into some limit of double precision arithmetic:

>> c = 1e60;
>> a1=floor(pi*1e60)
a1 =   3.14159265358979e+060

>> a2=floor(5*pi*1e60+1)
a2 =   1.57079632679490e+061

>> lcm(a1,a2)
ans =   1.57079632679490e+061

>> ans/a2
ans = 1

Finally, it is worth pointing out that this shifts the problem to knowing apriori or calculating how many significant digits are present in the numbers you're working with. this is a non-trivial problem to solve efficiently, especially working with double precision numbers. A good discussion can be found over at Matlab Central