Dividendo uno cero

28

Descripción del desafío

Para cada número entero positivo nexiste un número que tiene la forma de 111...10...000que es divisible por nej. Un número decimal que comienza con todos 1y termina con todos 0. Esto es muy fácil de probar: si tomamos un conjunto de n+1nú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 ny 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 pen forma de 111...10...000tal 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..00está 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
shooqie
fuente
¿Podemos tener un límite superior razonable a la salida posible? (Algo de menos de 2.400 millones (aproximadamente el valor máximo de un entero con signo) debería estar bien, ya que podrían requerirse matrices o listas para algunas implementaciones)
Tamoghna Chowdhury
@ MartinBüttner Creo que el primer resultado satisfactorio debería ser suficiente (restricción de tiempo razonable)
Tamoghna Chowdhury
El último 0 no es necesario en el caso de prueba 49.
CalculatorFeline
@CatsAreFluffy Creo que todos los números deben contener al menos 1y al menos uno 0, de lo contrario 0es una solución para cualquier entrada. (Sería bueno aclarar esto sin embargo.)
Martin Ender
Solo requerir uno 1debería funcionar.
CalculatorFeline

Respuestas:

22

Mathematica, 29 bytes

⌊10^(9EulerPhi@#)/9⌋10^#&

Código de Martin Büttner .

En la entrada n, esto genera el número con 9*ϕ(n)unos seguidos de nceros, donde ϕestá la función totient de Euler . Con una función phi, esto podría expresarse en Python como

lambda n:'1'*9*phi(n)+'0'*n

Serí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 de nceros es un múltiplo de n.

Prueba: En primer lugar, vamos a probar esto para el caso de que nno es un múltiplo de 2, 3o 5. Mostraremos que el número que consiste en ϕ(n)unos es un múltiplo de `n.

El número hecho de kunos es igual (10^k-1)/9. Como nno es un múltiplo de 3, este es un múltiplo de nmientras 10^k-1sea ​​un factor de n, o equivalentemente, si 10^k = 1 (mod n). Tenga en cuenta que esta formulación hace evidente que si kfunciona para el número de unidades, entonces también lo hace cualquier múltiplo de k.

Entonces, buscamos kser un múltiplo del orden de ken 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 de 1a nque son relativamente primos para n, su tamaño es la función totient Euler ϕ(n) . Entonces, hemos demostrado eso 10^ϕ(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 3in n. Sabemos que 10^ϕ(n)-1es un múltiplo de n, pero (10^ϕ(n)-1)/9podría no serlo. Pero, (10^(9*ϕ(n))-1)/9es un múltiplo de 9porque consiste en 9*ϕ(n)unos, por lo que la suma de sus dígitos es un múltiplo de 9. Y hemos notado que multiplicar el exponente kpor una constante preserva la divisibilidad.

Ahora, si ntiene factores de 2'sy 5' s, necesitamos agregar ceros al final de la salida. Es mucho más que suficiente usar nceros (de hecho log_2(n)lo haría). Entonces, si nuestra entrada nse divide como n = 2^a * 5^b * m, es suficiente tener 9*ϕ(m)unos para ser múltiplo de n, multiplicado por 10^npara ser un múltiplo de 2^a * 5^b. Y, dado que nes un múltiplo de m, es suficiente usar 9*ϕ(n)unos. Entonces, funciona tener 9*ϕ(n)unos seguidos de nceros.

xnor
fuente
12
Solo para asegurarme de que nadie piense que esto fue publicado sin mi permiso: a xnor se le ocurrió el método y la prueba por su cuenta, y simplemente le proporcioné una implementación de Mathematica, porque tiene una EulerPhifunción incorporada. No hay nada alucinante en la implementación real, por lo que lo consideraría completamente su propio trabajo.
Martin Ender
9

Python 2, 44 bytes

f=lambda n,j=1:j/9*j*(j/9*j%n<1)or f(n,j*10)

Cuando jes una potencia de 10 como 1000, la división de piso j/9da un número compuesto de 1 como 111. Entonces, j/9*jda 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.

xnor
fuente
1
Oh, buen punto, solo necesitamos verificar 1 ^ n0 ^ n ...
Martin Ender
@ MartinBüttner Si es más fácil, también es suficiente fijar el número de 0 como valor de entrada. Sin embargo, no sé si cuenta como eficiente imprimir tantos ceros.
xnor
¿Por qué funciona la comprobación de 1 ^ n0 ^ n?
Lynn
55
@Lynn Agregar más ceros no puede hacer daño, y hay infinitos números posibles de unos, algún número tendrá suficientes unos y ceros.
xnor
5

Pyth, 11 bytes

.W%HQsjZ`TT

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:

.W%HQsjZ`TT
                Implicit: Q = eval(input()), T = 10
.W              while loop:
  %HQ           while the current value mod Q is not zero
      jZ`T      Join the string "10" with the current value as the separator.
     s          Convert that to an integer.
          T     Starting value 10.
isaacg
fuente
4

Haskell, 51 bytes

\k->[b|a<-[1..],b<-[div(10^a)9*10^a],b`mod`k<1]!!0

Usando el enfoque de xnor. nimi guardó un byte!

Lynn
fuente
3

CJam, 28 25 19 bytes

Guardamos 6 bytes con la observación de xnor de que solo necesitamos mirar los números del formulario .1n0n

ri:X,:)Asfe*{iX%!}=

Pruébalo aquí.

Explicación

ri:X    e# Read input, convert to integer, store in X.
,:)     e# Get range [1 ... X].
As      e# Push "10". 
fe*     e# For each N in the range, repeat the characters in "10" that many times,
        e# so we get ["10" "1100" "111000" ...].
{iX%!}= e# Select the first element from the list which is divided by X.
Martin Ender
fuente
2

Mathematica, 140 55 bytes

NestWhile["1"<>#<>"0"&,"1",FromDigits@#~Mod~x>0&/.x->#]

Muchos bytes eliminados gracias al truco 1 ^ n0 ^ n de xnor.

Valor mínimo, 140 156 bytes Esto da a la solución más pequeña posible.

NestWhile["1"<>#&,ToString[10^(Length@NestWhileList[If[EvenQ@#,If[10~Mod~#>0,#/2,#/10],#/5]&,#,Divisors@#~ContainsAny~{2, 5}&],FromDigits@#~Mod~m>0&/.m->#]&

Calcula cuántos ceros son necesarios y luego verifica todos los 1recuentos posibles hasta que funcione. Puede generar un número sin 0 pero que se puede solucionar agregando un <>"0"derecho antes del final &.

CalculadoraFeline
fuente
2

Haskell, 37 bytes

f n=[d|d<-"10",i<-[1..n*9],gcd n i<2]

Esto utiliza el hecho de que funciona para tener 9*phi(n)unos, donde phiestá la función totient de Euler. Aquí, se implementa usando gcdy filtrando, produciendo un dígito para cada valor ique es relativamente primo en el rango 1y 9*n. También es suficiente usar tantos ceros.

xnor
fuente
2

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)

a=>{for(n='';!(m=n+=1)[17];)for(;!(m+=0)[17];)if(!(m%a))return+m}  

Menos golf

function (a) {
    for (n = ''; !(m = n += '1')[17]; )
        for (; !(m += '0')[17]; )
            if (!(m % a))
                 return +m;
}
edc65
fuente
1
¿Por qué no for(m=n;?
Neil
@Neil porque necesito al menos un cero. Tal vez pueda encontrar un camino más corto ... (gracias por la edición)
edc65
Oh, eso no estaba claro en la pregunta, pero ahora veo que todas las salidas de muestra tienen al menos un cero. En ese caso, aún puede guardar un byte con for(m=n;!m[16];)if(!((m+=0)%a)).
Neil
1
@Neil o incluso 2 bytes. Thx
edc65
1

Perl 5, 26 bytes

incluye un byte para -n( -M5.01es gratis)

($.="1$.0")%$_?redo:say$.
msh210
fuente
0

a. C., 58 bytes

define f(n){for(x=1;m=10^x/9*10^x;++x)if(m%n==0)return m;}

Resultados de muestra

200: 111000
201: 111111111111111111111111111111111000000000000000000000000000000000
202: 11110000
203: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000
204: 111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000
205: 1111100000
206: 11111111111111111111111111111111110000000000000000000000000000000000
207: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
208: 111111000000
209: 111111111111111111000000000000000000
210: 111111000000
211: 111111111111111111111111111111000000000000000000000000000000
212: 11111111111110000000000000
213: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
214: 1111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000
215: 111111111111111111111000000000000000000000
216: 111111111111111111111111111000000000000000000000000000
217: 111111111111111111111111111111000000000000000000000000000000
218: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
219: 111111111111111111111111000000000000000000000000
Toby Speight
fuente
0

dc, 27 bytes

Odsm[O*lmdO*sm+O*dln%0<f]sf

Esto define una función fque espera su argumento en la variable n. Para usarlo como un programa, ?sn lfx ppara leer desde stdin, llame a la función e imprima el resultado en stdout. La variable my la parte superior de la pila se deben restablecer a 10 (repitiendo Odsm) antes de que fse puedan reutilizar.

Resultados:

200: 111000
201: 111111111111111111111111111111111000000000000000000000000000000000
202: 11110000
203: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000
204: 111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000
205: 1111100000
206: 11111111111111111111111111111111110000000000000000000000000000000000
207: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
208: 111111000000
209: 111111111111111111000000000000000000
210: 111111000000
211: 111111111111111111111111111111000000000000000000000000000000
212: 11111111111110000000000000
213: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
214: 1111111111111111111111111111111111111111111111111111100000000000000000000000000000000000000000000000000000
215: 111111111111111111111000000000000000000000
216: 111111111111111111111111111000000000000000000000000000
217: 111111111111111111111111111111000000000000000000000000000000
218: 111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111111000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000
219: 111111111111111111111111000000000000000000000000
Toby Speight
fuente