0
$\begingroup$

Looking at partitions of the natural number line of the form $P=[a,b)$, I noted that

  • if $a$ and $b$ are multiples of $6$, there exist at least $2$ numbers in the partition which are not divisible by $2$ or $3$
  • if $a$ and $b$ are multiples of $30$, there exist $8$ numbers in the partition which are not divisible by $2, 3$ or $5$
  • if $a$ and $b$ are multiples of $210$, there exist $54$ numbers in the partition which are not divisible by $2,3,5$ or $7$.

This leads me to guess that if $a$ and $b$ are multiples of $2310$, there exist $592$ numbers in the partition which are not divisible by $2,3,5,7$ or $11$. Is this true?

(I arrived at $592$ because it is equal to $54 \times 11 - 2$ and $2310$ because it is equal to $210 \times 11$.)

$\endgroup$
  • 1
    $\begingroup$ Use en.wikipedia.org/wiki/Inclusion%E2%80%93exclusion_principle $\endgroup$ – vadim123 Mar 16 '14 at 14:43
  • 3
    $\begingroup$ Good work! I believe you will find that for $210$ it is $48$, not $54$. You are in the process of discovering the Euler $\varphi$ function. $\endgroup$ – André Nicolas Mar 16 '14 at 14:48
  • $\begingroup$ @Andre Thank you! I noted that are 35 primes between 210 and 420 as well as 8 numbers whose lowest divisor is 11, 6 with ld=13, 3 with ld=17 and 2 with ld=19, hence the 54...? $\endgroup$ – Brad Graham Mar 16 '14 at 14:56
  • 1
    $\begingroup$ You have done some "double-counting." $\endgroup$ – André Nicolas Mar 16 '14 at 15:32
  • $\begingroup$ I'll double check cheers $\endgroup$ – Brad Graham Mar 16 '14 at 15:33
2
$\begingroup$

Use chinese remainder representation with basis $[2,3,5,7,11]$.

Given a CRR basis $[a,b,c,d,e]$ with $M = abcde = 2\times 3 \times 5 \times 7 \times 11 = 2310$, each valid tuple represents exactly 1 number from $0$ to $M - 1 \pmod M$. So you want the number of tuples that don't contain a zero, or $(a - 1)(b - 1)(c - 1)(d - 1)(e - 1)$ or $1 \times 2 \times 4 \times 6 \times 10 = 480$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.