1
$\begingroup$

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

  • 0
    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)?2012-11-15
  • 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_...2012-11-15
  • 0
    I'm not sure :/2012-11-15
  • 0
    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...2012-11-15
  • 0
    So N -(1/12)N? Is that it?2012-11-15
  • 0
    Well, think about it. N/12 is not even a natural number unless 12 | N. The "chance" of a random natural number being divisible by 4 or 6 is 1/3, so the chance of a random natural not being divisible by 4 or 6 is 1 - 1/3 = 2/3, but this still doesn't answer your question, because you have to break N down into cases and then see if you can combine any of the cases into fewer statements. What happens if N = 4k? N = 6k? N = 12k? What happens otherwise? I am sure there are more clever ways to do this, but this is the way I would.2012-11-15
  • 0
    What do you mean here¿2012-11-15
  • 0
    What I mean is what happens for integers 1 - 12 "mirrors" what happens for integers afterwards, so you can consider integers modulo 12 at the very most. For example, for N = 5, we have 1, 2, 3 = 3 numbers. For N = 7 we have 1, 2, 3, 5 = 4 numbers. For N = 12, we have 1, 2, 3, 5, 7, 9, 10, 11 = 8 numbers. What do you think would be true about N = 5 + 12? what about N = 7 + 12?2012-11-15

3 Answers 3

2

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\,$?

  • 1
    I think you mean "4 AND 6" rather than "4 or 6"2012-11-15
  • 0
    Yes, sure. Thanks for that.2012-11-15
0

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.

  • 0
    Bah, beat me to it2012-11-15
  • 0
    lol ;-), happened to me a lot of times..2012-11-15
0

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.