Calcular a norma p-adic de um número racional
Escreva uma função ou um programa, que use 3 números inteiros m,n,p
(onde p
é um primo positivo) como entrada, que produza a norma p-adic (indicada por |m/n|_p
) como uma fração (completamente reduzida). Sabe-se que Fermat possui apenas margens muito pequenas, mas o que é desconhecido é que ele tinha apenas uma tela de computador muito pequena. Portanto, tente tornar o código o mais curto possível para caber na tela de Fermat!
Definição
Dado um primo p
, cada fração m/n
pode ser escrita exclusivamente (ignorando os sinais), como (a/b)* p^e
tal, que e
é um número inteiro e p
não divide nem a
nem b
. A norma p-adic de m/n
é p^-e
. Não é um caso especial, se a fração for 0: |0|_p = 0
.
O formato de saída deve ser x/y
(por exemplo 1/3
, para números inteiros ambos 10
ou equivalentemente 10/1
é permitido, para números negativos deve haver um sinal de menos à frente -1/3
)
Detalhes
O programa deve usar stdin / stdout ou apenas consistir em uma função que retorna o número racional ou a sequência. Você deve assumir que a entrada m/n
não está totalmente reduzida. Você pode assumir que isso p
é primo. O programa deve ser capaz de processar números inteiros entre -2^28
até 2^28
e não deve demorar mais de 10 segundos.
Não são permitidas funcionalidades embutidas de fatoração e verificação primária, bem como conversação básica e função incorporada que calculam a avaliação ou norma p-adic.
Exemplos (roubados da wikipedia ):
x = m/n = 63/550 = 2^-1 * 3^2 * 5^-2 * 7 * 11^-1
|x|_2 = 2
|x|_3 = 1/9
|x|_5 = 25
|x|_7 = 1/7
|x|_11 = 11
|x|_13 = 1
Curiosidades interessantes
(Não é necessário saber / ler para este desafio, mas talvez seja bom ler como motivação.)
(Corrija-me se eu usar as palavras erradas, ou se algo estiver errado, não estou acostumado a falar sobre isso em inglês.)
Se você considerar os números racionais como um campo, a norma p-adic induz a métrica p-adic d_p(a,b) = |a-b|_p
. Em seguida, você pode preencher esse campo com relação a essa métrica, o que significa que você pode construir um novo campo onde todas as sequências cauchy convergem, o que é uma boa propriedade topológica. (Que, por exemplo, os números racionais não têm, mas os reais.) Esses números p-adic são como você deve ter adivinhado, muito usados na teoria dos números.
Outro resultado interessante é o teorema de Ostrowski, que basicamente diz que qualquer valor absoluto (conforme definido abaixo) nos números racionais é um dos três seguintes:
- O trivial:
|x|=0 iff x=0, |x|=1 otherwise
- O padrão (real):
|x| = x if x>=0, |x| = -x if x<0
- O p-adic (como o definimos).
Um valor absoluto / uma métrica é apenas a generalização do que consideramos uma distância . Um valor absoluto |.|
satisfaz as seguintes condições:
|x| >= 0 and |x|=0 if x=0
|xy| = |x| |y|
|x+y| <= |x|+|y|
Observe que você pode facilmente construir métricas a partir de valores absolutos e vice-versa: |x| := d(0,x)
ou d(x,y) := |x-y|
, então, elas são quase as mesmas se você puder adicionar / subtrair / multiplicar (que está em domínios integrais). É claro que você pode definir uma métrica em conjuntos mais gerais, sem essa estrutura.
fonte
PadicNorm
função do Mathematica também esteja fora? : P|x|_11 = 11
, certo? Ou está11
bem? E tem que lidar com ox=0
caso?x=0
caso e, neste exemplo, você pode imprimir11
também11/1
, mas não precisa imprimir|x|_11
.Respostas:
Julia,
948075 bytesNota: o uso de feeds de linha no lugar de ponto e vírgula para facilitar a leitura - funcionará da mesma maneira.
Isso é bastante simples - a
g(m,n)
função usa recursão e restante (%
) para extrair op^n
fator da entradam
, comn=1
o padrão e depois multiplicado porp
cada etapa da recursão, para que a saída sejap^n
. O código aplica isso an/gcd(m,n)
e, em seguida,m/gcd(m,n)
para obter a expressão apropriada.k=gcd(m,n)
é usado para evitar o cálculogcd(m,n)
duas vezes, para salvar caracteres.m!=0
é um teste para lidar com o caso em quex=0
.A saída é da forma
N/1
ou,1/N
conforme apropriado, ondeN
estáp^e
.fonte
J,
3534 bytesEste é um verbo binário que usa o primo
p
como argumento à esquerda e a matrizm n
como argumento à direita. Ele sempre imprime a barra/
e retorna0/1
sem = 0
. Use-o assim:Explicação
A
x:
precisão aumenta, já que estamos lidando com números muito grandes. O restante do código funciona da seguinte maneira:fonte
CJam, 42 bytes
Isso termina com um erro (após a impressão de 0) para a entrada 0. Experimente on-line no intérprete CJam .
fonte
Stax , 32 bytes
Execute e depure
Deve ser capaz de torná-lo mais curto. O suporte nativo para fração por Stax é bastante elegante.
Equivalente ASCII:
fonte