Encontrar la cantidad de números menos que otro número que son múltiplos de un conjunto

Question

Un Ejemplo Para Ilustrar

• Encontrar la cantidad de números de menos de 30 que son múltiplos de un conjunto de números [2,3,5]

- Claro que podemos encontrar el número de múltiplos de un número menor que otro número a través de esta ecuación:

$$ numberOfMultiplesLessThan =\lceil\frac {numberToFindMultiplessLessThan}{numberToFindMultiplesOf}\rceil - 1 $$

Así que en este caso tenemos:

1. Número de Múltiplos de 2: $$\frac {30} 2 - 1 = 15 -1 = 14$$
2. Número de Múltiplos de 3: $$\frac {30} 3 - 1 = 10 -1 = 9$$
3. Número de Múltiplos de 5: $$\frac {30} 5 - 1 = 6 - 1 = 5$$

- Pero ahora tenemos que comprobar para los casos en los que un número es un múltiplo de más de uno de estos números:

1. Número de Múltiplos de 2 & 3: $$\frac {30} {2*3} - 1 = 30/6 - 1 = 5 - 1 = 4$$
2. Número de Múltiplos de 2 & 5: $$\frac {30} {2*5} - 1 = 30/10 - 1 = 3 - 1 = 2 $$
3. Número de Múltiplos de 3 & 5: $$\frac {30} {3*5} - 1 = 30/15 - 1 = 2 - 1 = 2 $$

Por suerte,ya $2*3*5 = 30$ no hay número menor de treinta que es un múltiplo de tres, así que no tenemos que comprobar que el conjunto. Por desgracia, para los grandes conjuntos (y dependiendo del número que es el elegido para ser menos que) puede haber muchas intersecciones para comprobar.

De todos modos, ahora podemos encontrar la cantidad de números que están a menos de 30 y son múltiplos de 2, 3, o 5:

1. $$Multiples Less than 30 = Number of Multiples of 2 + Number of Multiples of 3 + Number of Multiples of 5 - Number of Multiples of 2 & 3 - Number of Multiples of 2 & 5 - Number of Multiples of 3 & 5$$
2. $$Multiples Less than 30 = 14 + 9 + 5 - 4 - 2 - 2 = 21$$

Notas sobre el Problema

1. Aunque en este caso yo seleccione un número (30), que hizo de los resultados de las múltiples ecuación resultan muy bien, la verdad es que el actual número elegido no ser tan agradable. Así, en los casos en que el techo de la función debe ser invocada.
2. No es una coincidencia que los números en el conjunto de todos los primos. Mi aplicación específica es un poco extraño, ya que sólo seleccione los números primos y que también, por la elección de un primer número debe de incluir todos los números primos por debajo de ella (ej: [11,7,5,3,2] es un conjunto válido pero [11,5,3,2] no es). No estoy seguro de cómo esta nota va a afectar a la respuesta, pero he pensado que me gustaría incluir.

Mi Problema

Este algoritmo, si bien es relativamente sencillo, se vuelve un poco tedioso con números extremadamente grandes y extremadamente grandes conjuntos. Examinar el problema de nuevo, he encontrado que hay una enorme cantidad de simplificación que se pueden hacer con la ecuación total. Por ejemplo:

Tener en cuenta (de nuevo) en el caso de encontrar la cantidad de números de menos de 30 que son Múltiplos de 2, 3 o 5. El general de la ecuación es este.

1. $$ Multiples Less than 30 = Number of Multiples of 2 + Number of Multiples of 3 + Number of Multiples of 5 - Number of Multiples of 2 & 3 - Number of Multiples of 2 & 5 - Number of Multiples of 3 & 5 $$

2. Múltiplos Menos De $$ 30 = 29 - (\frac {30} 2 -1) - (\frac {30} 3 - 1) - (\frac {30} 5 - 1) + (\frac {30}{2*3} - 1) + (\frac{30} {2*5} -1) + (\frac{30} {3*5} - 1) $$

3. $$Multiples Less Than 30 = 29 - (\frac {30} 2) - (3\frac {30} 3) - (\frac {30} 5) + (\frac {30}{2*3}) + (\frac{30} {2*5}) + (\frac{30} {3*5}) + 3 - 3 $$

   
   
   [Nota: es común pero no es necesario que el -1 es cancelada]
   

4. $$Multiples Less Than 30 = 29 - (\frac {30} 2) - (\frac {30} 3) - (\frac {30} 5) + (\frac {30}{2*3}) + (\frac{30} {2*5}) + (\frac{30} {3*5}) $$

5. $$Multiples Less Than 30 = 29 - 30*(\frac12 + \frac 13 + \frac 15 - \frac 1 {2*3} - \frac 1 {2*5} - \frac 1 {(3*5)} )$$

6. $$Multiples Less Than 30 = 29 - 2*3*5*(\frac12 + \frac 13 + \frac 15 - \frac 1 {2*3} - \frac 1 {2*5} - \frac 1 {(3*5)} )$$

7. $$Multiples Less Than 30 = 29 - (3*5 + 2*5 + 2*3 - 5 - 3 - 2 )$$
   
   [Nota: En los casos que no involucran el primorial ( 3*2 o 5*3*2 o 7*5*3*2 o 11*7*5*3*2), tendrías que múltiples ambos lados por el primorial a ser capaz de limpiar las fracciones]

8. $$Multiples Less Than 30 = 29 - (3*5 + 2*5 + 2*3 - 5 - 3 - 2 )$$
9. $$Multiples Less Than 30 = 29 - (3*4 + 5 + 2*2) $$
   
   [Nota: Como se puede ver (Paso 9) la duración relativamente larga de la ecuación se ha convertido en algo simple. Yo lo he hecho con un par de números, y sin hacer ningún cálculo, aparte de factoring y la combinación de términos semejantes -- siempre se trata de algo relativamente simple.]

La Pregunta!

Entonces, mi pregunta es: Usando el tipo de simplificación que se muestra arriba (o cualquier otro sistema, para el caso), ¿hay alguna manera generalizada para encontrar cuántos múltiplos de un primer conjunto, como se discutió anteriormente están por debajo de un número que es más fácil o más rápido que el algoritmo que he descrito?

P. S. Estoy disculpas de antemano por el formato y el aspecto visual de la pregunta. Yo he tratado de hacer es tan legible como sea posible, pero aún siento que es voluminoso y un poco desorganizada. Además, no pude averiguar cómo hacer que las matemáticas se ven bien (como 3*5)

Answer 1

Usted puede escribir lo que está después como

$$\lfloor{29\over2} \rfloor+\lfloor{29\over3} \rfloor+\lfloor{29\over5} \rfloor-\lfloor{29\over6} \rfloor-\lfloor{29\over10} \rfloor-\lfloor{29\over15} \rfloor+\lfloor{29\over30} \rfloor=14+9+5-4-2-1+0=21$$

En general, si usted tiene un conjunto de pares de primos relativos (positivo) enteros $a_1,a_2,\ldots,a_n$, y se desea saber cuántos múltiplos de uno de estos hay menos de un cierto número $N$, la respuesta es

$$\lfloor{N-1\over a_1} \rfloor+\cdots+\lfloor{N-1\over a_n} \rfloor-\lfloor{N-1\over a_1a_2} \rfloor-\cdots-\lfloor{N-1\over a_{n-1}a_n} \rfloor+\cdots+(-1)^{n+1}\lfloor{N-1\over a_1\cdots a_n} \rfloor$$

por la inclusión-exclusión, como JMac31 mencionado en los comentarios. En general, esto le da $2^n-1$ números para calcular. Yo creo que no se puede hacer nada mejor que que si usted desea conseguir el número exacto.

Por otro lado, si (como es el caso de la OP ejemplo), el $a_i$'s son distintos de los números primos y $N$ es su producto, entonces la respuesta es

$$N-1-(a_1-1)(a_2-1)\cdots(a_n-1)$$

Esto se debe principalmente a la propiedad multiplicativa de la phi de Euler de la función.