¿Cómo encontrar el mínimo número posible de longitud N, que es simultáneamente divisible por el número primo de un solo dígito como 2,3,5,7 ? como de longitud 5 número mínimo posible es 10080.
Respuestas
¿Demasiados anuncios?
Sólo para una solución alternativa, se busca el menor entero no negativo $r_N$ tal que $210\mid 10^{N-1}+r_N$ , es decir, tal que $r_N\equiv -10^{N-1}\pmod {210}$ .
Pero $-10^{N-1}$ es necesariamente cíclico, y como siempre es cero mod $2$ y $5$ y $-1$ mod $3$ para todos $N>1$ el único factor relevante es $7$ y, por tanto, tiene una longitud cíclica de como máximo $6$ .
De hecho, rápidamente conseguimos que $r_2=200,r_3=110,r_4=50,r_5=80,r_6=170, r_7=20$ y luego vuelve al ciclo de $r_8=200$ .
La ventaja de esta versión es que no es necesario dividir $10^{N-1}$ por $210$ para obtener el resultado para grandes $N$ . Por ejemplo, el número más pequeño para $N=62$ es $10^{61}+200$ .
Farkhod Gaziev
Puntos
6
Como el lcm de $2,3,5,7$ es $210,$ necesitamos encontrar el mínimo múltiplo en $N$ dígitos.
Así que, $N$ debe ser $\ge 3$ para admitir la solución.
El mínimo número natural con $N$ dígitos es $M=100\cdots00$ con $(N-1)$ ceros.
Por lo tanto, si $D=\lfloor\frac M {210}\rfloor,$ la respuesta será $210(D+1)$
Por ejemplo, si $N=4,D=\lfloor\frac {1000} {210}\rfloor=4,$ la respuesta será $210(4+1)=1050$
Como señala Thomas en su comentario,
podemos utilizar Función de Carmichael , $\lambda(21)=lcm(\lambda(3), \lambda(7))=lcm(2,6)=6$
Así que, $10^6\equiv1\pmod {21}\implies 10^{6m}\equiv1\pmod {21}$
$\implies 10^{6m+1}\equiv{10}\pmod {210},$ el número mínimo con longitud $(6m+1+1)=6m+2,$ será $10^{6m+1}+(210-10)$
$\implies 10^{6m+2}\equiv{100}\pmod {210},$ el número mínimo con longitud $6m+3,$ será $10^{6m+1}+(210-100)$ y así sucesivamente.
Malu MN
Puntos
11
Lo primero que hay que tener en cuenta es que cualquier número que sea divisible por dicho número tiene que ser de la forma 2*3*7*M = 210 * M, para algún M $\in$ N. Por lo tanto, tales números son de la forma 210*1, 210*2, 210*3, 210*4, y así sucesivamente.
Ahora tenemos que encontrar el primer número de n cifras que sea divisible por 210. El primer número de n cifras es $10^n$ . Para encontrar el número más cercano que sea divisible por 210, tenemos que iterar desde [ $10^n$ , $10^n + 210$ ) para encontrar el número que es divisible por 210. Uno de cada 210 números consecutivos es divisible por 210.
Ej: Para n = 6, el mínimo número posible de 6 dígitos es 100000. Para encontrar el primer número de 6 dígitos que es divisible por 210, iterar desde 100000 hasta 100210 y reportar el número que es divisible por 210. En este caso, ese número es 100170.
A veces, cuando se trata de este tipo de problemas en la programación competitiva, n puede ser muy grande y $10^n$ puede no ser representable como un entero en una máquina. Tenemos que tratarlo como una cadena. Tenemos que averiguar qué número debe añadirse a $10^n$ para que sea divisible por 210.
$10^n$ El mod 210 se puede encontrar representando el número como una cadena. (Existe un método fácil, sólo hay que buscarlo en Google).
Sea k = $10^n$ mod(210). Entonces la respuesta es $10^n$ +210-k porque (210-k) es el menor número que hay que sumar a $10^n$ para que el módulo sea 0.
