Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm not sure if there is a given term for this problem but I'm trying to find the number of iterations required to complete this type of pattern:

Consider two patterns/lists: [a,b,c] & [0,1]

The entire pattern would be a0 b1 c0 a1 b0 c1 and the number of iterations would be 6.

I wrote a perl script to calculate several of these patterns:

3 vs. 2:

    1:      1 1
    2:      2 2
    3:      3 1
    4:      1 2
    5:      2 1
    6:      3 2

4 vs. 5:

    1:      1 1
    2:      2 2
    3:      3 3
    4:      4 4
    5:      1 5
    6:      2 1
    7:      3 2
    8:      4 3
    9:      1 4
    10:     2 5
    11:     3 1
    12:     4 2
    13:     1 3
    14:     2 4
    15:     3 5
    16:     4 1
    17:     1 2
    18:     2 3
    19:     3 4
    20:     4 5

6 vs. 4:

    1:      1 1
    2:      2 2
    3:      3 3
    4:      4 4
    5:      5 1
    6:      6 2
    7:      1 3
    8:      2 4
    9:      3 1
    10:     4 2
    11:     5 3
    12:     6 4

12 vs. 9:

    1:      1 1
    2:      2 2
    3:      3 3
    4:      4 4
    5:      5 5
    6:      6 6
    7:      7 7
    8:      8 8
    9:      9 9
    10:     10 1
    11:     11 2
    12:     12 3
    13:     1 4
    14:     2 5
    15:     3 6
    16:     4 7
    17:     5 8
    18:     6 9
    19:     7 1
    20:     8 2
    21:     9 3
    22:     10 4
    23:     11 5
    24:     12 6
    25:     1 7
    26:     2 8
    27:     3 9
    28:     4 1
    29:     5 2
    30:     6 3
    31:     7 4
    32:     8 5
    33:     9 6
    34:     10 7
    35:     11 8
    36:     12 9

Is there a term for this type of "algorithm"? How can I algebraically solve for the number of iterations without going through each one at a time?

Can someone help me derive a formula?

share|improve this question
2  
If given 'x vs. y', looks like it's: $$\frac{x * y}{\text{gcd}\left( x , y \right)}$$? –  Nicolas Villanueva Sep 16 '11 at 15:26
    
please expand... gcd = greated common denomination? –  CheeseConQueso Sep 16 '11 at 15:27
    
gcd($x , y$) typically means 'Greatest Common Divisor of $x$ and $y$' –  Nicolas Villanueva Sep 16 '11 at 15:28
    
wouldn't that resolve to 1 if x & y were 2 & 3, respectively? –  CheeseConQueso Sep 16 '11 at 15:31
    
gcd(2,3) = 1 en.wikipedia.org/wiki/Euclidean_algorithm –  Nicolas Villanueva Sep 16 '11 at 15:33
show 1 more comment

1 Answer 1

up vote 2 down vote accepted

Given two inputs $a$ and $b$ the running time is the least common multiple of $a$ and $b$, which is typically notated ${\rm lcm}(a,b)$.

The least common multiple $m$ is the smallest number you can find so that there are two other numbers $h$ and $k$ which together satisfy

$$ah = bk = m$$

In your case, you are taking two lists $(1,\dots,a)$ and $(1,\dots,b)$ and repeating them side by side, until the lengths of the outputs coincide (I presume that this is exactly what your Perl script does). When you have done this, you will have written the first sequence out $h$ times and the second sequence $k$ times, for a total of $m={\rm lcm}(a,b)$ iterations.

An easy way to calculate the least common multiple is first to calculate the greatest common divisor (using Euclid's algorithm) and then use the relationship

$${\rm lcm}(a,b) = \frac{ab}{{\rm gcd}(a,b)}$$

More information about the least common multiple available on the Wikipedia page.

share|improve this answer
    
Haha, totally forgot that what I wrote down WAS the LCM :P –  Nicolas Villanueva Sep 16 '11 at 15:34
    
that looks good so far using 4 vs 6 –  CheeseConQueso Sep 16 '11 at 15:35
    
thats it... thanks a lot! –  CheeseConQueso Sep 16 '11 at 15:36
    
im using this to write poly-rhythmic music... helps me figure out how many times the drummer needs to repeat a 4/4 bar! –  CheeseConQueso Sep 16 '11 at 15:37
    
@Nicolas sorry, didn't see your comment when I posted this - props to you! –  Chris Taylor Sep 16 '11 at 15:38
show 1 more comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.