Dividendo um zero

28

Descrição do Desafio

Para todo número inteiro positivo nexiste um número que tem a forma de 111...10...000que é divisível por, nisto é, um número decimal que começa com todos 1e termina com todos 0. É muito fácil provar: se pegarmos um conjunto de n+1números diferentes na forma de111...111 (todos 1), pelo menos dois deles fornecerão o mesmo restante após a divisão por n(conforme o princípio do buraco de pombo). A diferença desses dois números será divisível por ne terá a forma desejada. Seu objetivo é escrever um programa que encontre esse número.

Descrição da entrada

Um número inteiro positivo.

Descrição da saída

Um número pna forma de 111...10...000, de modo quep ≡ 0 (mod n) . Se você encontrar mais de um - exiba qualquer um deles (não precisa ser o menor).

Notas

Seu programa deve fornecer a resposta em um período de tempo razoável. O que significa que a força bruta não é permitida:

p = 0
while (p != 11..10.00 and p % n != 0)
    p++

Nem é isso:

do
    p = random_int()
while (p != 11..10.00 and p % n != 0)

A iteração pelos números na forma de 11..10..00é permitida.

Seu programa não precisa lidar com uma entrada arbitrariamente grande - o limite superior é o limite superior do seu idioma.

Saídas de amostra

2: 10
3: 1110
12: 11100
49: 1111111111111111111111111111111111111111110
102: 1111111111111111111111111111111111111111111111110
code-golf math arithmetic number-theory shooqie
fonte
Podemos ter um limite superior razoável para a saída possível? (Algo sobre menos de 2,4 bilhões (aproximadamente o valor máximo de um inteiro assinado) deve estar bem, como matrizes ou listas pode ser necessária para algumas implementações.)
Tamoghna Chowdhury
@ MartinBüttner Eu acho que a saída primeiro satisfazendo deve ser suficiente (restrição prazo razoável)
Tamoghna Chowdhury
O último 0 não é necessário no caso de teste 49.
CalculatorFeline
@CatsAreFluffy Acho que todos os números precisam conter pelo menos 1e pelo menos um 0, caso contrário, 0é uma solução para qualquer entrada. (Seria bom esclarecer isso embora.)
Martin Ender
Apenas exigir um 1deve funcionar.
CalculatorFeline

Respostas:

22

Mathematica, 29 bytes

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

Código de Martin Büttner .

Na entrada n, isso gera o número com 9*ϕ(n)os seguidos de nzeros, onde ϕestá a função totiente de Euler . Com uma função phi, isso pode ser expresso em Python como

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

Seria suficiente usar o fatorial em n!vez de ϕ(n), mas imprimir muitos deles não tem um tempo de execução razoável.

Reivindicação: 9*ϕ(n) uns seguidos de nzeros é um múltiplo de n.

Prova: Primeiro, vamos provar isso para o caso de que nnão é um múltiplo de 2, 3ou 5. Mostraremos que o número com consistência de ϕ(n)unidades é um múltiplo de `n.

O número feito de kuns é igual (10^k-1)/9. Como nnão é um múltiplo de 3, este é um múltiplo ndesde que 10^k-1seja um fator de n, ou equivalente se 10^k = 1 (mod n). Observe que essa formulação torna aparente que, se kfuncionar para o número de unidades, o mesmo ocorre com qualquer múltiplo de k.

Então, estamos procurando kser um múltiplo da ordem de kno módulo multiplicativo n . Pelo Teorema de Lagrange , qualquer ordem desse tipo é um divisor do tamanho do grupo. Como os elementos do grupo são o número de 1para o nque é relativamente primo n, seu tamanho é a função totiente de Euler ϕ(n) . Então, nós mostramos isso 10^ϕ(n) = 1 (mod n), e então o número feito deϕ(n) um é um múltiplo de `n.

Agora, vamos lidar com os fatores potenciais de 3in n. Sabemos que 10^ϕ(n)-1é um múltiplo de n, mas (10^ϕ(n)-1)/9pode não ser. Mas, (10^(9*ϕ(n))-1)/9é um múltiplo de 9porque consiste em 9*ϕ(n)uns, então a soma de seus dígitos é um múltiplo de 9. E observamos que multiplicando o expoentek por uma constante preserva a divisibilidade.

Agora, se ntiver fatores de 2's e 5' s, precisamos adicionar zeros ao final da saída. É mais do que suficiente usar nzeros (de fato log_2(n)seria). Portanto, se nossa entrada né dividida como n = 2^a * 5^b * m, basta ter um 9*ϕ(m)para ser um múltiplo de n, multiplicado por 10^num múltiplo de 2^a * 5^b. E, como né um múltiplo de m, basta usá-los 9*ϕ(n). Então, funciona para ter 9*ϕ(n)uns seguidos de nzeros.

xnor
fonte
12
Apenas para garantir que ninguém pense que isso foi publicado sem a minha permissão: xnor criou o método e a prova por conta própria, e eu apenas forneci a ele uma implementação do Mathematica, porque ela possui uma EulerPhifunção interna. Não há nada de alucinante na implementação real, então eu consideraria isso totalmente seu próprio trabalho.
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)

Quando jé uma potência de 10 como 1000, a divisão de piso j/9fornece um número feito de 1's como 111. Portanto, j/9*jdá 1's seguidos por um número igual de 0s como 111000.

A função testa recursivamente números dessa forma, tentando potências cada vez maiores de 10 até encontrarmos uma que seja um múltiplo do número desejado.

xnor
fonte
1
Oh, bom ponto, só precisa verificar 1 ^ n0 ^ n ...
Martin Ender
@ MartinBüttner Se for mais fácil, também basta fixar o número de 0 para ser o valor de entrada. Não sei se é tão eficiente imprimir tantos zeros.
xnor 28/02
Por que verificar 1 ^ n0 ^ n funciona?
Lynn
5
@ Lynn A adição de mais zeros não pode prejudicar, e há infinitos números possíveis de unidades, alguns terão o suficiente de unidades e zeros.
xnor 28/02
5

Pitão, 11 bytes

.W%HQsjZ`TT

Suíte de teste

Basicamente, ele coloca um 1 na frente e um 0 na parte de trás uma e outra vez até que o número seja divisível pela entrada.

Explicação:

.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
fonte
4

Haskell, 51 bytes

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

Usando a abordagem do xnor. nimi salvou um byte!

Lynn
fonte
3

CJam, 28 25 19 bytes

Salva 6 bytes com a observação do xnor de que precisamos apenas olhar para os números do formulário .1n0n

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

Teste aqui.

Explicação

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
fonte
2

Mathematica, 140 55 bytes

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

Muitos bytes foram removidos graças ao truque de 1 ^ n0 ^ n do xnor.

Valor mínimo, 140 156 bytes Isso fornece a menor solução possível.

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

Ele calcula quantos zeros são necessários e verifica todas as 1contagens possíveis até que funcione. Ele pode gerar um número sem 0, mas que pode ser corrigido adicionando um <>"0"antes da final &.

CalculatorFeline
fonte
2

Haskell, 37 bytes

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

Isso usa o fato de que funciona para ter 9*phi(n)uns, onde phiestá a função totiente de Euler. Aqui, ele é implementado usando gcde filtrando, produzindo um dígito para cada valor ique é relativamente primordial àquele que está no intervalo 1e 9*n. Também é suficiente usar tantos zeros.

xnor
fonte
2

JavaScript (ES6), 65 bytes

Editar 2 bytes salvos thx @Neil

Ele funciona dentro dos limites do tipo numérico javascript, com 17 dígitos significativos. (Tão limitado)

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

Menos golfe

function (a) {
    for (n = ''; !(m = n += '1')[17]; )
        for (; !(m += '0')[17]; )
            if (!(m % a))
                 return +m;
}
edc65
fonte
1
Por que não for(m=n;?
Neil
@ Neil porque eu preciso de pelo menos um zero. Talvez eu possa encontrar um caminho mais curto ... (thx para a edição)
edc65
Ah, isso não ficou claro na pergunta, mas agora vejo que todas as saídas de amostra têm pelo menos um zero. Nesse caso, você ainda pode salvar um byte usando for(m=n;!m[16];)if(!((m+=0)%a)).
Neil
1
@ Neil ou até 2 bytes. Thx
edc65 28/02
1

Perl 5, 26 bytes

inclui um byte para -n( -M5.01é grátis)

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

bc, 58 bytes

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

Resultados da amostra

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
fonte
0

dc, 27 bytes

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

Isso define uma função fque espera seu argumento na variável n. Para usá-lo como um programa, ?sn lfx ppara ler a partir de stdin, chame a função e imprima o resultado em stdout. A variável me o topo da pilha devem ser redefinidos para 10 (repetindo Odsm) antes que fpossam ser reutilizados.

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
fonte