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.

How many positive integers less than $N$ are not divisible by $4$ or $6$ for some $N$?

share|improve this question
    
Will, perhaps you should start by breaking it down into cases of N. What if N itself is divisble by 4? By 6? By lcm(4,6)? –  tacos_tacos_tacos Nov 15 '12 at 2:03
1  
And to follow up on that point, what if you look at 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16... –  tacos_tacos_tacos Nov 15 '12 at 2:07
    
I'm not sure :/ –  Will eastbay Nov 15 '12 at 2:13
    
1/4 of all numbers are divisible by 4, 1/6 of all numbers are divisible by 6, and 1/(lcm 4,6) = 1/12 of all numbers are divisible by 4 and 6... so given a random N, P(divisible by 4 or 6) = P(divisible by 4) + P(divisible by 6) - P(divisible by 12) = 3/12 + 2/12 - 1/12 = 4/12 = 1/3... –  tacos_tacos_tacos Nov 15 '12 at 2:17
    
So N -(1/12)N? Is that it? –  Will eastbay Nov 15 '12 at 2:19

3 Answers 3

Form three arithmetic sequences:

1.- Numbers that are divisible by $\,4\,$ and less or equal than $\,400\,$:

$$4,8,12,...\Longrightarrow a_1=4\,\,,\,d=4\Longrightarrow a_n=a_1+(n-1)d=4+(n-1)4\leq 400\Longrightarrow n\leq 100$$

2.- Numbers that are divisible by $\,6\,$ and less or equal than $\,400\,$:

$$6,12,18,...\Longrightarrow a_1=6\,\,,\,d=6\Longrightarrow a_n=6+(n-1)6\leq 400\Longrightarrow n\leq66$$

3.- Numbers that are divisible by $\,4\,$ and $\,6\,$ and less or equal than $\,400\,$:

$$12,24,36,...\Longrightarrow a_1=12\,\,,\,d=12\Longrightarrow a_n=12+(n-1)12\leq 400\Longrightarrow n\leq 33$$

Well, take it now from here: how many positive integers less than $\,400\,$ are not divisible by $4\,,\,6\,$?

share|improve this answer
1  
I think you mean "4 AND 6" rather than "4 or 6" –  tacos_tacos_tacos Nov 15 '12 at 2:36
    
Yes, sure. Thanks for that. –  DonAntonio Nov 15 '12 at 2:38

One approach:

Count the number of numbers divisible by $4 ([\frac N4] )$, then count the number of numbers divisible by $6(\frac N6] )$, Now during these calculations we've calculated nos divisible by $12 ([\frac N{12} ] )$ twice, so we subtract it thereby giving the number of integers divisible by either $4$ or $6$ as $[ \frac N4 ] + [ \frac N6 ] - [\frac N{12}]$. Now subtract this number from $N$ to get required answer.

Note:

  1. I've used Principle of inclusion exclusion.

  2. $[ \cdot ]$ denote floor function.

share|improve this answer
    
Bah, beat me to it –  user45793 Nov 15 '12 at 2:40
    
lol ;-), happened to me a lot of times.. –  TheJoker Nov 15 '12 at 6:56

A naive and computational answer: look at congruence modulo 12.

  1. Empty (no natural numbers less than 1) = $0$
  2. ${1}$ = $1$
  3. ${1,2}$ = $2$
  4. ${1, 2, 3}$ = $3$
  5. ${1, 2, 3}$ = $3$
  6. ${1, 2, 3, 5}$ = $4$
  7. ${1, 2, 3, 5}$ = $4$
  8. ${1, 2, 3, 5, 7}$ = $5$
  9. ${1, 2, 3, 5, 7}$ = $5$
  10. ${1, 2, 3, 5, 7, 9}$ = $6$
  11. ${1, 2, 3, 5, 7, 9, 10}$ = $7$
  12. ${1, 2, 3, 5, 7, 9, 10, 11}$ = $8$

From here, observe that any $N$ will be congruent to one of these guys, so you add $N \mod 12$ to 8 times the floor of $N/12$; ie $13 = 12 + 1$ so $n(13) = 8 \times 1 + 0 = 8$ and $n(155) = 8 \times 12 + n(11) = 96 + 7 = 103$.

And then see how you can improve my naive method to get a more "general" answer.

share|improve this answer

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.