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!


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)


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.

  • \$\begingroup\$ I assume Mathematica's PadicNorm function is also out? :P \$\endgroup\$
    – Alex A.
    Commented Nov 11, 2015 at 21:49
  • \$\begingroup\$ You assume correct/ly. (which one is used here?) \$\endgroup\$
    – flawr
    Commented Nov 11, 2015 at 21:52
  • \$\begingroup\$ Unless the Interesting Properties section is useful for completing the challenge, I'd say it's better to just link to that information for interested parties. Otherwise it unnecessarily clutters the post. \$\endgroup\$
    – Alex A.
    Commented Nov 11, 2015 at 21:56
  • \$\begingroup\$ Just to be clear, output should be something like |x|_11 = 11, right? Or is just 11 fine? And does it have to handle the x=0 case? \$\endgroup\$
    – Glen O
    Commented Nov 12, 2015 at 6:38
  • \$\begingroup\$ @GlenO Correct, it does have to handle the x=0 case and for this example you can output 11 as well as 11/1, but you do not have to print |x|_11. \$\endgroup\$
    – flawr
    Commented Nov 12, 2015 at 9:10

4 Answers 4


Julia, 94 80 75 bytes


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.


J, 35 34 bytes


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


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

CJam, 42 bytes


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


Stax, 32 bytes


Run and debug it

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

ASCII equivalent:


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.