p-adic Expansion
Details
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 ai (i = 0…∞) of the p-adic expansion of r can be obtained by repeating the following steps:
- Find the only integer ai between 0 and p − 1 such that the numerator of r − ai is divisible by p.
- Replace r with (r − ai)/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 pk.
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