Calculate the p-adic norm of a rational number

Question

Calculate the p-adic norm of a rational number

Write a function or a program, that takes 3 integers m,n,p (where p is a positive prime) as input, that outputs the p-adic norm (denoted by |m/n|_p) as a (completely reduced) fraction. Fermat is known to have only very small margins, but what is rather unknown is that he only had a very small computer screen. So try to make the code as short as possible for it to fit on Fermat's screen!

Definition

Given a prime p, every fraction m/n can uniquely be written (ignoring the signs) as (a/b)* p^e such that e is a integer and p divides neither a nor b. The p-adic norm of m/n is p^-e. There is a special case, if the fraction is 0: |0|_p = 0.

The output format must be x/y (e.g. 1/3; for integers both 10 or equivalently 10/1 is allowed, for negative numbers there must be a leading minus e.g. -1/3)

Details

The program must use stdin/stdout, or just consist of a function that returns the rational number or string. You have to assume that the input m/n is not fully reduced. You can assume that p is a prime. The program has to be able to process integers between -2^28 up to 2^28, and should not take more than 10 seconds.

Built in factorization and prime checking functionalities are not allowed, as well as built in base conversatio, and built in function that calculate the p-adic valuation or norm.

Examples (stolen from 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

Interesting trivia

(Not necessary to know/read for this challenge, but perhaps nice to read as a motivation.)

(Please correct me if I use the wrong words, or something else is wrong, I am not used to talking about this in english.)

If you consider the rational numbers as a field, then the p-adic norm induces the p-adic metric d_p(a,b) = |a-b|_p. Then you can complete this field with regard to this metric, that means you can construct a new field where all cauchy sequences converge, which is a nice topological property to have. (Which e.g. the rational numbers do not have, but the reals do.) These p-adic numbers are as you might have guessed, used a lot in number theory.

Another interesting result is Ostrowski's theorem which basically says, any absolut value (as defined below) on the rational numbers is one of the following three:

• The trivial: |x|=0 iff x=0, |x|=1 otherwise
• The standard (real): |x| = x if x>=0, |x| = -x if x<0
• The p-adic (as we defined it).

An absolute value / a metric is just the generalization of what we consider a distance. A absolute value |.| satisfies following conditions:

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

Note that you can easily construct metrics from absolute values and vice versa: |x| := d(0,x) or d(x,y) := |x-y|, so they are almost the same if you can add/substract/multiply (that is in integral domains). You can of course define a metric on more general sets, without this structure.

Answer 1

Julia, 94 80 75 bytes

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)

Note: using linefeeds in place of semicolons for readability - will work same either way.

This is quite simple - the g(m,n) function uses recursion and remainder (%) to extract the p^n factor from input m, with n=1 as default and then multiplied by p on each step of the recursion, so that the output will be p^n. The code applies that to n/gcd(m,n), and then to m/gcd(m,n) to obtain the appropriate expression. k=gcd(m,n) is used to avoid calculating the gcd(m,n) twice, to save characters. m!=0 is a test to handle the case where x=0.

The output is of the form N/1 or 1/N as appropriate, where N is p^e.

Answer 2

J, 35 34 bytes

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

This is a binary verb that takes the prime p as its left argument, and the array m n as its right argument. It always prints the slash /, and returns 0/1 if m = 0. Use it like this:

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

Explanation

The x: turns on extended precision, since we're handling very large numbers. The rest of the code works as follows:

(,'/'&,)&":/@(%+./)@(]<.^+.|.@])
                        ^         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

Answer 3

CJam, 42 bytes

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

THis finishes with an error (after printing 0) for input 0. Try it online in the CJam interpreter.

Answer 4

Stax, 32 bytes

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

Run and debug it

Should be able to make it shorter. The native support for fraction by Stax is quite neat.

ASCII equivalent:

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