Calculer la norme p-adique d'un nombre rationnel

Écrivez une fonction ou un programme, qui prend en entrée 3 entiers m,n,p(où pest un nombre positif), qui produit la norme p-adique (notée par |m/n|_p) comme une fraction (complètement réduite). Fermat est connu pour n'avoir que de très petites marges, mais ce qui est plutôt inconnu, c'est qu'il n'avait qu'un très petit écran d'ordinateur. Essayez donc de rendre le code aussi court que possible pour qu'il tienne sur l'écran de Fermat!

Définition

Étant donné un nombre premier p, chaque fraction m/npeut être écrite de manière unique (en ignorant les signes) comme (a/b)* p^etelle qui eest un entier et pne divise ni ani b. La norme p-adique de m/nest p^-e. Il y a un cas particulier, si la fraction est 0: |0|_p = 0.

Le format de sortie doit être x/y(par exemple 1/3; pour les entiers les deux 10ou de manière équivalente 10/1est autorisé, pour les nombres négatifs, il doit y avoir un moins négatif, par exemple -1/3)

Détails

Le programme doit utiliser stdin / stdout, ou simplement se composer d'une fonction qui renvoie le nombre rationnel ou la chaîne. Vous devez supposer que l'entrée m/nn'est pas complètement réduite. Vous pouvez supposer que pc'est une prime. Le programme doit être capable de traiter des nombres entiers -2^28allant jusqu'à 2^28, et ne devrait pas prendre plus de 10 secondes.

Les fonctionnalités intégrées de factorisation et de vérification principale ne sont pas autorisées, ainsi que la conversion de base intégrée et la fonction intégrée qui calcule la valeur ou la norme p-adique.

Exemples (volés sur 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

Anecdotes intéressantes

(Pas nécessaire de savoir / lire pour ce défi, mais peut-être agréable à lire comme motivation.)

(Veuillez me corriger si j'utilise les mauvais mots, ou si quelque chose d'autre ne va pas, je n'ai pas l'habitude d'en parler en anglais.)

Si vous considérez les nombres rationnels comme un champ, la norme p-adique induit la métrique p-adique d_p(a,b) = |a-b|_p. Ensuite, vous pouvez compléter ce champ en ce qui concerne cette métrique, cela signifie que vous pouvez construire un nouveau champ où toutes les séquences de cauchy convergent, ce qui est une belle propriété topologique. (Ce qui, par exemple, les nombres rationnels n'ont pas, mais les réels en ont.) Ces nombres p-adiques sont, comme vous l'avez peut-être deviné, beaucoup utilisés dans la théorie des nombres.

Un autre résultat intéressant est le théorème d'Ostrowski qui dit essentiellement que toute valeur absolue (telle que définie ci-dessous) sur les nombres rationnels est l'une des trois suivantes:

• Le trivial: |x|=0 iff x=0, |x|=1 otherwise
• La norme (réelle): |x| = x if x>=0, |x| = -x if x<0
• Le p-adique (tel que nous l'avons défini).

Une valeur absolue / une métrique n'est que la généralisation de ce que nous considérons comme une distance . Une valeur absolue |.|satisfait aux conditions suivantes:

• |x| >= 0 and |x|=0 if x=0
• |xy| = |x| |y|
• |x+y| <= |x|+|y|

Notez que vous pouvez facilement construire des métriques à partir de valeurs absolues et vice versa: |x| := d(0,x)ou d(x,y) := |x-y|alors elles sont presque les mêmes si vous pouvez ajouter / soustraire / multiplier (c'est-à-dire dans des domaines intégraux). Vous pouvez bien sûr définir une métrique sur des ensembles plus généraux, sans cette structure.

Julia, 94 80 75 octets

f(m,n,p)=(k=gcd(m,n)
g(m)=m%p>0?g(m÷p)p:1
m!=0?print(g(n÷k),/,g(m÷k)):0)

Remarque: l'utilisation de sauts de ligne à la place des points-virgules pour plus de lisibilité - fonctionnera de la même façon.

C'est assez simple - la g(m,n)fonction utilise la récursivité et reste ( %) pour extraire le p^nfacteur d'entrée m, avec n=1par défaut et ensuite multiplié par pà chaque étape de la récursivité, de sorte que la sortie sera p^n. Le code applique cela à n/gcd(m,n), puis à m/gcd(m,n)pour obtenir l'expression appropriée. k=gcd(m,n)est utilisé pour éviter de calculer le gcd(m,n)double, pour enregistrer les caractères. m!=0est un test pour gérer le cas où x=0.

La sortie est de la forme N/1ou, 1/Nle cas échéant, où Nest p^e.

J, 35 34 octets

(,'/'&,)&":/@(%+./)@(]<.^+.|.@])x:

Il s'agit d'un verbe binaire qui prend le premier pcomme argument de gauche et le tableau m ncomme argument de droite. Il imprime toujours la barre oblique /et renvoie 0/1if m = 0. Utilisez-le comme ceci:

  f =: (,'/'&,)&":/@(%+./)@(]<.^+.|.@])x:
  5 f 63 550
25/1

Explication

Les x:tours sur la précision étendue, car nous traitons de très grands nombres. Le reste du code fonctionne comme suit:

(,'/'&,)&":/@(%+./)@(]<.^+.|.@])
                        ^         Power: this gives the array p^n p^m
                         +.       Take element-wise GCD with
                           |.@]   the rotated array n m; this gives
                                  the largest powers of p that divide n and m
                      <.          Take element-wise minimum with
                     [            The array m n to handle the m=0 case correctly
              %+./                Divide this array by its GCD to get it to lowest terms
        &":/                      Convert both elements to strings
 ,'/'&,                           Insert the slash '/' between them

CJam, 42 octets

q~)\_:*g_sW<o@*28#f{{{_@\%}h;}:G~}_~Gf/'/*

Cela se termine par une erreur (après l'impression de 0) pour l'entrée 0. Essayez-le en ligne dans l' interpréteur CJam .

Stax , 32 octets

éE▌ΦΔΘao£╙)ΩuÅI~AAε3∞xC█&½╤%╩▌ïö

Exécuter et déboguer

Doit pouvoir le raccourcir. Le support natif de fraction par Stax est assez soigné.

Équivalent ASCII:

hY{y:+y|aEGsG-ys|**}0?}0{^scxHY%Cy/sWd