Descripción del desafío
Para cada número entero positivo n
existe un número que tiene la forma de 111...10...000
que es divisible por n
ej. Un número decimal que comienza con todos 1
y termina con todos 0
. Esto es muy fácil de probar: si tomamos un conjunto de n+1
números diferentes en forma de 111...111
(todos 1
), al menos dos de ellos darán el mismo resto después de la división por n
(según el principio del casillero). La diferencia de estos dos números será divisible por n
y tendrá la forma deseada. Su objetivo es escribir un programa que encuentre este número.
Descripción de entrada
Un entero positivo.
Descripción de salida
Un número p
en forma de 111...10...000
tal que p ≡ 0 (mod n)
. Si encuentra más de uno, muestre cualquiera de ellos (no es necesario que sea el más pequeño).
Notas
Su programa tiene que dar la respuesta en un tiempo razonable. Lo que significa que la fuerza bruta no está permitida:
p = 0
while (p != 11..10.00 and p % n != 0)
p++
Tampoco es esto:
do
p = random_int()
while (p != 11..10.00 and p % n != 0)
Iterar a través de los números en forma de 11..10..00
está permitido.
Su programa no necesita manejar una entrada arbitrariamente grande: el límite superior es el límite superior de su idioma.
Resultados de muestra
2: 10
3: 1110
12: 11100
49: 1111111111111111111111111111111111111111110
102: 1111111111111111111111111111111111111111111111110
fuente
1
y al menos uno0
, de lo contrario0
es una solución para cualquier entrada. (Sería bueno aclarar esto sin embargo.)1
debería funcionar.Respuestas:
Mathematica, 29 bytes
Código de Martin Büttner .
En la entrada
n
, esto genera el número con9*ϕ(n)
unos seguidos den
ceros, dondeϕ
está la función totient de Euler . Con una funciónphi
, esto podría expresarse en Python comoSería suficiente usar el factorial en
n!
lugar deϕ(n)
, pero imprimir que muchos no tiene un tiempo de ejecución razonable.Reclamación:
9*ϕ(n)
unos seguidos den
ceros es un múltiplo den
.Prueba: En primer lugar, vamos a probar esto para el caso de que
n
no es un múltiplo de2
,3
o5
. Mostraremos que el número que consiste enϕ(n)
unos es un múltiplo de `n.El número hecho de
k
unos es igual(10^k-1)/9
. Comon
no es un múltiplo de3
, este es un múltiplo den
mientras10^k-1
sea un factor den
, o equivalentemente, si10^k = 1 (mod n)
. Tenga en cuenta que esta formulación hace evidente que sik
funciona para el número de unidades, entonces también lo hace cualquier múltiplo dek
.Entonces, buscamos
k
ser un múltiplo del orden dek
en el grupo multiplicativo módulo n . Según el teorema de Lagrange , cualquier orden de este tipo es un divisor del tamaño del grupo. Dado que los elementos del grupo son el número de1
an
que son relativamente primos paran
, su tamaño es la función totient Eulerϕ(n)
. Entonces, hemos demostrado eso10^ϕ(n) = 1 (mod n)
, y entonces el número hecho deϕ(n)
unos es un múltiplo de `n.Ahora, manejemos los factores potenciales de
3
inn
. Sabemos que10^ϕ(n)-1
es un múltiplo den
, pero(10^ϕ(n)-1)/9
podría no serlo. Pero,(10^(9*ϕ(n))-1)/9
es un múltiplo de9
porque consiste en9*ϕ(n)
unos, por lo que la suma de sus dígitos es un múltiplo de9
. Y hemos notado que multiplicar el exponentek
por una constante preserva la divisibilidad.Ahora, si
n
tiene factores de2
'sy5
' s, necesitamos agregar ceros al final de la salida. Es mucho más que suficiente usarn
ceros (de hecholog_2(n)
lo haría). Entonces, si nuestra entradan
se divide comon = 2^a * 5^b * m
, es suficiente tener9*ϕ(m)
unos para ser múltiplo den
, multiplicado por10^n
para ser un múltiplo de2^a * 5^b
. Y, dado quen
es un múltiplo dem
, es suficiente usar9*ϕ(n)
unos. Entonces, funciona tener9*ϕ(n)
unos seguidos den
ceros.fuente
EulerPhi
función incorporada. No hay nada alucinante en la implementación real, por lo que lo consideraría completamente su propio trabajo.Python 2, 44 bytes
Cuando
j
es una potencia de 10 como 1000, la división de pisoj/9
da un número compuesto de 1 como 111. Entonces,j/9*j
da 1 seguido de un número igual de 0 como 111000.La función prueba recursivamente números de esta forma, probando potencias cada vez mayores de 10 hasta encontrar uno que sea múltiplo del número deseado.
fuente
Pyth, 11 bytes
Banco de pruebas
Básicamente, solo pone un 1 al frente y un 0 al revés una y otra vez hasta que el número sea divisible por la entrada.
Explicación:
fuente
Haskell, 51 bytes
Usando el enfoque de xnor. nimi guardó un byte!
fuente
CJam,
282519 bytesGuardamos 6 bytes con la observación de xnor de que solo necesitamos mirar los números del formulario .
1n0n
Pruébalo aquí.
Explicación
fuente
Mathematica,
14055 bytesMuchos bytes eliminados gracias al truco 1 ^ n0 ^ n de xnor.
Valor mínimo,
140156 bytes Esto da a la solución más pequeña posible.Calcula cuántos ceros son necesarios y luego verifica todos los
1
recuentos posibles hasta que funcione. Puede generar un número sin 0 pero que se puede solucionar agregando un<>"0"
derecho antes del final&
.fuente
Haskell, 37 bytes
Esto utiliza el hecho de que funciona para tener
9*phi(n)
unos, dondephi
está la función totient de Euler. Aquí, se implementa usandogcd
y filtrando, produciendo un dígito para cada valori
que es relativamente primo en el rango1
y9*n
. También es suficiente usar tantos ceros.fuente
JavaScript (ES6), 65 bytes
Editar 2 bytes guardados gracias a @Neil
Funciona dentro de los límites del tipo numérico javascript, con 17 dígitos significativos. (Muy limitado)
Menos golf
fuente
for(m=n;
?for(m=n;!m[16];)if(!((m+=0)%a))
.Perl 5, 26 bytes
incluye un byte para
-n
(-M5.01
es gratis)fuente
Sabio, 33 bytes
Esto usa el método de xnor para producir la salida.
Pruébalo en línea
fuente
a. C., 58 bytes
Resultados de muestra
fuente
dc, 27 bytes
Esto define una función
f
que espera su argumento en la variablen
. Para usarlo como un programa,?sn lfx p
para leer desde stdin, llame a la función e imprima el resultado en stdout. La variablem
y la parte superior de la pila se deben restablecer a 10 (repitiendoOdsm
) antes de quef
se puedan reutilizar.Resultados:
fuente