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 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.

share|improve this question
1  
Not sure what you're looking for. A computer language is an appropriate way to express an algorithm. If you were looking to write the result of this algorithm; that is, the set that it generates, then you'd use notation something like this $\{n\in{\Bbb N}|2\leq n\leq 2004 \wedge 2 | n \wedge ( 8|n \vee 11|n )\}$. –  user22805 Oct 15 '12 at 2:09
    
@David Wallace The part I'm struggling with, is if I give an answer like that, then I have simply restated the problem in mathematical terms. Giving anything else as an answer, i.e. the whole set or parts of it, seems like an idiotic thing to do because there are 319 elements in it. So I'm thinking I have to explain what algorithm (function) I used to get the set and the formal definition of the set, like you wrote. –  Ярослав Рахматуллин Oct 15 '12 at 2:32
    
Maybe you should ask your teacher what he/she expects to see. Possibly, he/she doesn't realise that there are 319 elements. If there ARE so many elements (I'll take your word for this), then it's unlikely that you are expected to write them all down; so if you just say "I wrote this Java program" and point out that you got 319 elements, that may well be enough. –  user22805 Oct 15 '12 at 2:36
    
is the problem asking u to find the elements, or just asking you how many there are ? –  N. S. Oct 15 '12 at 4:19
    
The problem is actually to find out how many elements there are, and not to enumerate all the elements. –  Ярослав Рахматуллин Oct 15 '12 at 7:10

1 Answer 1

up vote 3 down vote accepted

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.

share|improve this answer
    
Simple and clever. I tried to get the same result, but forgot 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! –  Ярослав Рахматуллин Oct 15 '12 at 22:35

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.