1
$\begingroup$

I have found a solution to a basic problem using an algorithm, but I'm having a bit of a hard time expressing this algorithm in terms of discrete math.

for (i=2; i<=2004; i+=2) {     if (i%8 === 0 || i%11 === 0 )  tall.push(i); } 

I'm thinking that something like this would do the trick, but would like to hear other suggestions:

f(n):

if n mod 2 ∧ (n mod 8 ∨ n mod 11): A = A ∪ {n}

The original problem prompts the reader to find the total number of integers from the set of {2, 4, 6, 8, ..., 2004} that are divisible by either 8, 11 or both.

  • 0
    The problem is actually to find out how many elements there are, and not to enumerate all the elements.2012-10-15

1 Answers 1

3

Your algorithm will indeed provide the correct answer. Since you're only asked to find the number of elements and not enumerate them, you're really looking for the size of your set tail. To explain your algorithm, it suffices to convince someone that the algorithm adds a new number, $i$ to the set if (1) $2\le i\le 2004$, (2) $i$ is even, (3) $i$ is divisible by 8 or by 11 (or both). Your algorithm obviously does exactly that, and that proof of correctness suffices.

There's computationally simpler way to do this problem, by the way. Ask the question "How many numbers in $\{2, 4, \dots, 2004\}$ are divisible by 8?" Those will be $\{8, 16, 24, \dots, 2000\}$ and there will be $\lfloor 2004/8\rfloor$ of them, where $\lfloor x\rfloor$ represents the greatest integer less than or equal to $x$.

In a similar way, there will be $\lfloor 2004/22\rfloor$ even numbers in your range divisible by 11. Leading to the conclusion that there will be $ \left\lfloor\frac{2004}{8}\right\rfloor+\left\lfloor\frac{2004}{22}\right\rfloor= 250+91=341 $ numbers in your range divisible by either 8 or 11. However, we've counted the numbers divisible by both 8 and 11 twice, once in each sum, so we have to subtract the numbers divisible by 88, giving us $ \left\lfloor\frac{2004}{8}\right\rfloor+\left\lfloor\frac{2004}{22}\right\rfloor-\left\lfloor\frac{2004}{88}\right\rfloor= 250+91-22=319 $ as expected. This is known as the principle of inclusion/exclusion and is often very useful.

  • 0
    Simple and clever. I tried to get the same result, but $f$orgot to exclude the odd multiples of 11. You gave me both a "confirmation" and a suggestion for improvement! I could not have hoped for a better answer. Thanks a million!2012-10-15