Dado um número n >= 2
, produza todos os números inteiros positivos menores que n
onde gcd(n, k) == 1
(com k
qualquer um dos números de saída). Números desse tipo são coprime entre si.
Exemplo: 10
fornece a saída [1, 3, 7, 9]
(de qualquer forma que você quiser, desde que os números sejam separados sem ambiguidade e em algum tipo de lista). A lista não pode ter entradas duplicadas e não precisa ser classificada.
Mais casos de teste:
2 -> [1]
3 -> [1, 2]
6 -> [1, 5]
10 -> [1, 3, 7, 9]
20 -> [1, 3, 7, 9, 11, 13, 17, 19]
25 -> [1, 2, 3, 4, 6, 7, 8, 9, 11, 12, 13, 14, 16, 17, 18, 19, 21, 22, 23, 24]
30 -> [1, 7, 11, 13, 17, 19, 23, 29]
Também não estamos contando números acima dos n
que são coprime n
, apenas porque estou bastante certo de que existem infinitas soluções.
Observe também: os números que são coprime entre si também são considerados relativamente primos ou mutuamente primos entre si.
code-golf
math
number-theory
primes
Rɪᴋᴇʀ
fonte
fonte
1\n3\n
) contam como saída válida?Respostas:
Gelatina , 3 bytes
Experimente online!
Como é que isso funciona?
Prova de validade
Desde que nós queremos extrair apenas os coprimes, o valor mínimo da lista Maior-Common-Divisores tem que ser 1 para o
ÐṂ
truque para o trabalho. Vamos provar que (em dois métodos diferentes):Dois números inteiros positivos consecutivos são sempre coprime. Considere , com . Então tomamos outro número inteiro positivo modo que e .x,y∈Z∗ y=x+1 k k∣x k∣y
Isso implica que , então , portanto, . O único número inteiro positivo a dividir é o próprio , por isso é garantido que apareça na lista e sempre será o valor mínimo.k ∣ ( x + 1 - x ) k ∣ 1 1 1k∣(y−x) k∣(x+1−x) k∣1 1 1
fonte
ÐṂ
existia naquela época, de qualquer forma, estou bastante satisfeito com este.DṂ
existia, mas só funcionava para mônadas. O commit implementadoÞ
,ÐṂ
,ÐṀ
para díades é datado 09 de maio de 2017.Python 2 ,
6147 bytesExperimente online!
fundo
Considere o anel . Embora esse anel seja geralmente definido usando as classes de resíduos módulo n , também pode ser considerado o conjunto Z n = { 0 , … , n - 1 } , onde os operadores de adição e multiplicação são definidos por a + n b = ( a + b )( Zn, +n, ⋅n) n Zn= { 0 , … , n - 1 } e a ⋅ n b = a ⋅ ba +nb = ( a + b )%n , onde + ,a⋅nb=a⋅b%n denotam os operadores usuais de adição, multiplicação e módulo sobre os números inteiros.+,⋅, and %
Dois elementos e b de Z n são chamados inversos multiplicativos mútuos módulo n se a ⋅ n b = 1a b Zn n . Note que 1a⋅nb=1%n sempre que n > 1 .1%n=1 n>1
Corrija e deixe a ser um coprime de n em Z n . Se um ⋅ n x = um ⋅ n y por dois elementos de x e y de Z n , temos que um ⋅ xn>1 a n Zn a⋅nx=a⋅ny x y Zn . Isso implica que a ⋅ ( x - y )a⋅x%n=a⋅y%n , e seguimos que n ∣ a ⋅ ( x - y ) , ou seja, n divide a ⋅ ( x - y ) igualmente. Como n não compartilha divisores primos com a , isso significa que n ∣ x - y . Finalmente, porque - n < x - y < n , concluímos que x = y . Isso mostra que os produtos de uma ⋅a ⋅ ( x - y)%n = um ⋅ x%n - um ⋅ y%n = 0 n ∣ a ⋅ ( x - y) n a ⋅ ( x - y) n uma n ∣ x - y - n < x - y< n x = y são todos elementos diferentes de Z n . Como Z n tem exatamente n elementos, um (e exatamente um) desses produtos deve ser igual a 1 , ou seja, existe um b exclusivoem Z n de modo que a ⋅ n b = 1 .a⋅n0,…,a⋅n(n−1) Zn Zn n 1 b Zn a⋅nb=1
Por outro lado, corrija e deixe a ser um elemento de Z n que não é coprime para n . Nesse caso, existe um primo p tal que p ∣ a e p ∣ n . Se um admitido um módulo inverso multiplicativo n (vamos chamá-lo de b ), teríamos que a ⋅ n b = 1 , significando que a ⋅ bn>1 a Zn n p p∣a p∣n a n b a⋅nb=1 e, portanto, ( a ⋅ b - 1 )a⋅b%n=1 , então n ∣ a ⋅ b - 1 . Desde p ∣ a , seguimos que p ∣ a ⋅ b . Por outro lado, desde p ∣ n , seguimos também p ∣ a ⋅ b - 1 . Dessa forma, p ∣ ( a ⋅ b ) - ( a ⋅ b - 1 ) = 1(a⋅b−1)%n=a⋅b%n−1=0 n∣a⋅b−1 p∣a p∣a⋅b p∣n p∣a⋅b−1 p∣(a⋅b)−(a⋅b−1)=1 , o que contradiz a suposição de que é um número primo.p
Isso prova que as seguintes instruções são equivalentes quando .n>1
e n são coprime.a n
admite um módulo inverso multiplicativo n .a n
admite umúnicomódulo inverso multiplicativo n .a n
Como funciona
Para cada par de números inteiros e b em Z n , o número inteiro k : = um ⋅ n + b é única; de facto, um e b são quociente e o resto de k dividido por n , isto é, dada k , que podem recuperar um = k / n e b = ka b Zn k : = um ⋅ n + b uma b k n k a = k / n , onde / denotadivisãointeira. Finalmente, uma vez que um ≤ n - 1 e b ≤ n - 1 , k é um elemento de Z n 2 ; de fato, k ≤ ( n - 1 ) ⋅ n + ( n - 1 ) = n 2 - 1 .b = k%n / a ≤ n - 1 b ≤ n - 1 k Zn2 k≤(n−1)⋅n+(n−1)=n2−1
Como observado acima, se e n forem coprime, haverá um b único, de modo que a ⋅ ba n b , ou seja, haverá um k únicoque k / n = a e k / n ⋅ ka⋅b%n=1 k k/n=a , então a lista gerada conterá uma exatamente uma vez.k/n⋅k%n=(k/n)⋅(k%n)%n=1 a
Por outro lado, se e n não são coprime, a condição k / n ⋅ ka n será falso para todos os valores de k, de modo que a = k / n , portanto, a lista geradanãoconterá a .k/n⋅k%n=1 k a=k/n a
Isto prova que a lista dos lambda retorna irá conter todos 's coprimes em Z n exactamente uma vez.n Zn
fonte
Gelatina , 4 bytes
Experimente online!
Como funciona
fonte
gRỊT
ÐṂ
) para obter 3 bytes .Mathematica, 25 bytes
Formato de saída ligeiramente estranho, onde cada resultado é agrupado em uma lista separada, por exemplo
{{1}, {3}, {7}, {9}}
. Se não estiver certo, tenho duas soluções em 30 bytes:O Mathematica realmente tem,
CoprimeQ
mas é muito longo.fonte
Q
significaCoprimeQ
?EvenQ
,PrimeQ
ouSubsetQ
.2sable , 4 bytes
Código:
Explicação:
Usa a codificação CP-1252 . Experimente online!
fonte
Python,
938274 bytesf
recursivamente verifica coprimes, e o segundo lambda os gera. Mostra uma lista.fonte
Na verdade , 8 bytes
Experimente online!
Explicação:
fonte
range(1, n)
se isso salva alguns bytes.R
(range(1, n+1)
) er
(range(n)
). Como eles são equivalentes, eu escolhiR
(desde que bati acidentalmente em caps lock enquanto escrevia o código).MATL , 7 bytes
Experimente online!
fonte
MATLAB / oitava, 22 bytes
Experimente online!
fonte
JavaScript (ES6),
6461 bytesGuardado 3 bytes graças a @ user81655
Snippet de teste
fonte
a==
coma<2
?a
pode ser 0 em algum momento. Vou ter que verificarfilter
para remover a necessidade de receber umb
parâmetro:...keys()].filter(b=>(g=a=>b?g(b,b=a%b):a<2)(n))
Água-viva ,
1918 bytesIsso funciona calculando a fatoração primária de cada número no intervalo e verificando se ele cruza o da entrada (o Jellyfish ainda não possui um gcd). Por razões de golfe, a saída está em ordem decrescente. Experimente online!
Explicação
Primeiro,
i
é avaliada a entrada; para entrada10
, o valor dai
célula é10
.Aqui
r
(intervalo) é aplicado à entrada e 1. Como a entrada é maior que 1, o intervalo está em ordem decrescente; para entrada10
, isso dá[9 8 7 6 5 4 3 2 1]
.Esta parte é uma grande função, avaliada na
i
faixa acima.Interseção (
n
) de fatores primos (x
).Está vazio? (
N
)Passe para o nível 0, testando para cada elemento do intervalo.
Filtre (
#
) o intervalo em relação a esta lista de booleanos. Como a função produzida por[
deseja usar o argumento#
como seu próprio argumento, colocamos umB
bloco#
para evitar qualquer argumento. Caso contrário, o valor da~
célula-seria usado como argumento da grande função. Por fim,p
imprime o resultado.fonte
Empilhados, não concorrentes,
2421 bytesEconomizou 3 bytes, inspirado no rubi de Borsunho . (
1 eq
para2<
)Experimente aqui!
Este é um n-lambda que pega um único argumento e gera a matriz.
fonte
keep
não estava funcionando bem.CJam , 14 bytes
Experimente online!
Explicação
Não precisamos verificar todos os divisores possíveis
a
eb
testar se são coprimes. É suficiente verificar se algum dos principais fatores dasb
divisõesa
.fonte
Mathematica, 26 bytes
fonte
Perl 6 , 20 bytes
fonte
Braquilog ,
1613 bytesEsta é uma função que recebe N como entrada e gera todos os números inteiros menores que e coprime para ela.
Experimente online! Como costuma ser o caso do Brachylog, esse código adicional foi adicionado para transformar a função em um programa completo; O intérprete de Brachylog, se receber uma função em vez de um programa completo, executará, mas não imprimirá a saída, o que significa que você não pode realmente observar o funcionamento.
Explicação:
Um programa Brachylog é uma cadeia de restrições; normalmente, o LHS de uma restrição é o RHS da próxima.
Golpeou três caracteres ao perceber que não há razão para verificar se o fator comum (que já é conhecido como um fator primordial da saída) é um fator primordial da entrada. Já sabemos que é excelente, então podemos apenas verificar se é um fator. Estou agradavelmente surpreendido aqui que
:A*?
não envia o intérprete para um loop infinito e não permite um valor não inteiro para A , mas como o intérprete faz o que eu quero, eu aceito.fonte
Dyalog APL, 10 bytes .
Explicação (entrada
n
):fonte
⍨
Japonês
-f
,9852 bytesTente
fonte
o f_jU
j
que também pode ser usado para testar se dois números são co-primos.Mathematica, 33 bytes
Contém U + F4A1
fonte
Haskell, 27 bytes
Experimente online!
fonte
Julia 0,5 , 23 bytes
Experimente online!
fonte
memes , 11 bytes não concorrentes , desatualizado
Não competir, pois a iteração do STDIN é nova. Usa codificação UTF-8.
Explicação:
}
acessa o próximo item de entrada, mas a última entrada é repetida quando fornecida, portanto a entrada6
resultará como6 6 6 6 6 ...
em STDIN, possibilitando a leitura de duas saídas de uma.fonte
05AB1E , 3 bytes
Experimente online!
Tem novos recursos.
fonte
Ruby,
3634É certo que esta não é uma resposta muito inspirada .
2 bytes salvos graças a Conor O'Brien.
fonte
(n)
Python 3 , 60 bytes
Importa o gcd em vez de escrever um novo lambda para ele. Sugestões de golfe são bem-vindas. Experimente online!
fonte
Julia, 30 bytes
Função anônima.
filter
remove elementos de uma lista que não é verdadeira de acordo com uma função.Nesse caso, a função é
x->(gcd(n,x)<2)
(true se o mcd da entrada e o elemento da lista for menor que 2). A lista é o intervalo1:n
.fonte
PARI / GP , 27 bytes
Isso usa a notação de conjunto introduzida na versão 2.6.0 (2013). Nas versões anteriores, eram necessários mais quatro bytes:
seria necessário.
fonte
[1..n]
), verifique se gcd é 1 (gcd(n,k)<2
), retorne os números com essa propriedade. A->
notação é função / fechamento, menor em 2 bytes que a sintaxe da função normal e[...|...<-...,...]
é a notação definida explicada na resposta (consulte a seção 2.3.14 no Manual do Usuário ou procure<-
).05AB1E , 4 bytes
Experimente online!
Como funciona
fonte
C (gcc) , 54 bytes
Esta é uma porta da minha resposta Python .
Experimente online!
fonte
Pitão , 5 bytes
Experimente online!
Como funciona
Observe que o Pyth usa a indexação 0.
fonte