0
$\begingroup$

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?

  • 0
    ok i see the difference now, thanks2011-09-16

1 Answers 1

2

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.

  • 0
    is there a name for this pattern?2011-09-16