p-adic Expansion

A p-adic integer is an integer written in base p with an infinite number of digits: …a2a1a0. Every rational number r with denominator not divisible by p is a p-adic integer (in other words, r has a p-adic expansion). For example, the 5-adic expansion of 17 is …00032.

The digits a_i (i = 0…∞) of the p-adic expansion of r can be obtained by repeating the following steps:

1. Find the only integer a_i between 0 and p − 1 such that the numerator of r − a_i is divisible by p.
2. Replace r with (r − a_i)/p.

Note: The first k digits of the p-adic expansion of a rational number a/b can also be found by computing a×b^-1 modulo p^k.

The p-adic expansion of a rational number is periodic. Quote notation uses a single quote (') to mean that the digits to its left are repeated indefinitely to the left:

(p=5) 17 = …00032 = 0'32

(p=5) 1/3 = …1313132 = 13'2

(p=7) -1 = …666 = 6'

Given a prime number p (2 ≤ p ≤ 61) and a reduced fraction r, print the p-adic expansion of r in quote notation. Use Base62 characters (0-9 A-Z a-z) as digits:

61 -85/24 → X2'Wy

External links: Rosetta Code, Wikipedia