by Greg Egan

Is there an integer d whose reciprocal, 1/d, has a decimal representation with a recurring block of digits exactly 10 digits long, containing all ten decimal digits?

The answer is yes! 72,728 has this property. In fact, we can find integers with analogous properties in several different bases besides base 10. A number is described as pandigital in base b if its representation contains all the digits 0, ..., b – 1, and non-redundant if each digit appears only once, so we will call these blocks of b repeating digits, enclosed in parentheses in the table below, non-redundant pandigital reptends.

Here we are describing the integers themselves with the usual base 10 notation, and only switching to base b when we give the representations of the fractions. We follow the convention of using the letters A, B, C, ... for digits 10, 11, 12, ... in bases greater than 10.

These numbers were found with a computer search, which came up empty for all the other bases that were tried. But are these really the only bases in which an integer can have this property?

Question: In what bases can the reciprocal of an integer have a non-redundant pandigital reptend?

Partial answer: We will prove with some simple number theory that there are no solutions for odd bases, and computer calculations have ruled out solutions for bases 8, 16, 32 and 64. But in general, this is still an open question.

[If we didn’t care about the non-redundancy of the digits, this would be a trivial question: for every base there are an infinite number of integers whose reciprocals have pandigital reptends, when some digits are allowed to appear more than once. The Online Encyclopedia of Integer Sequences has a list of the smallest such integers for each base, A382498.]

The rational number R that this represents can be found by summing a geometric series with an infinite number of terms:

R = [x + r Σ_{i = 1}^∞ (1 / b^j)ⁱ] / b^k
= [x + (r / b^j) 1 / (1 – 1 / b^j)] / b^k
= [x + r / (b^j – 1)] / b^k

We can check this formula with a few examples:

R = 0.(142857) ...
b = 10
r = 142,857
j = 6
x = k = 0

R = 142,857 / (10⁶ – 1) = 142,857 / 999,999 = 1/7

R = 0.03(571428) ...
b = 10
r = 571,428
j = 6
x = 3
k = 2

R = (3 + 571,428 / (10⁶ – 1)) / 10²
= (3 + 571,428 / 999,999) / 100
= (3 + 4/7) / 100
= 25/700
= 1/28

R = 0.0(0132)₄ ...
b = 4
r = 132₄ = 2 + 3×4 + 1×4² = 30
j = 4
x = 0
k = 1

R = (30 / (4⁴ – 1)) / 4
= (30 / 255) / 4
= 1/34

Since we will mostly be concerned with rational numbers that are reciprocals of integers, we will find it useful to rewrite this formula as:

When R = 1/d:

d [r + x (b^j – 1)] = (b^j – 1) b^k

Let’s return to our original question about which bases allow reciprocals of integers to have non-redundant pandigital reptends. We will be performing several calculations in modular arithmetic, with modulus b – 1. We start with a couple of obvious statements:

b ≡ 1 (mod b – 1)
bⁱ ≡ 1 (mod b – 1) for any integer i

This in turn means that any number with digits D_i is equivalent, mod b – 1, to the sum of its digits:

Σ_i=0ⁿ D_i bⁱ ≡ Σ_i=0ⁿ D_i (mod b – 1)

This is the basis for the well-known divisibility tests for 3 and 9: a number in base 10 will be equivalent to the sum of its digits, modulo 9.

For a non-redundant pandigital integer P_b in base b, since its digits are 0, ..., b – 1 (in any order, it doesn’t matter), we have:

P_b ≡ Σ_i=0^{b – 1} i ≡ ½ b (b – 1) (mod b – 1)

Now, suppose the base b is odd. Then b – 1 is even, and we have:

P_b ≡ ½(b – 1) (mod b – 1, for b odd)

For example, if b = 7, then for any non-redundant pandigital number in base 7, with 0+1+2+3+4+5+6 = 21:

P₇ ≡ ½(b – 1) ≡ 3 (mod 6)

If we take our formula linking an integer d with the features of its reciprocal’s representation in base b, and assume that the reptend r is a non-redundant pandigital number in an odd base, we get:

For odd base b, and a non-redundant pandigital reptend r for the reciprocal of d:

r ≡ ½(b – 1) (mod b – 1)

d [r + x (b^b – 1)] = (b^b – 1) b^k
d r = (b^b – 1) (b^k – d x)
d r = (b – 1) (1 + b + b² + ... + b^{b – 1}) (b^k – d x)

The reptend r is not divisible by b – 1, so d must be. Suppose d = g (b – 1), and divide both sides of the equation by b – 1.

g r = (1 + b + b² + ... + b^{b – 1}) (b^k – g (b – 1) x)

Now taking everything mod b – 1:

g (½(b – 1)) ≡ (1 + 1 + ... [b terms]) (1 – 0) ≡ 1 (mod b – 1)

If g is even, then g (½(b – 1)) ≡ 0 (mod b – 1), so g must be odd. But in that case, g (½(b – 1)) ≡ ½(b – 1), leaving us with:

½(b – 1) = 1
b = 3

So we have ruled out all odd bases except for b = 3. But our computer search found no reciprocals with non-redundant pandigital reptends in base 3. Can we prove that this is also impossible?

The non-redundant pandigital integers in base 3 are:

{012₃, 021₃, 102₃, 120₃, 201₃, 210₃}
= {5, 7, 11, 15, 19, 21}

Note that all of these values are odd.

Our formula linking the integer d with the representation of its reciprocal becomes:

d [r + x (b^b – 1)] = (b^b – 1) b^k
d [r + 26 x] = 26 × 3^k = 2 × 13 × 3^k

Since r must be odd, the only possible prime factors of r + 26 x are 3 and 13. If we first assume no factor of 13, we have:

r + 26 x ≡ r ≡ 3^a (mod 13)

But since 3³ = 27 ≡ 1 (mod 13), the only powers of 3 are {1, 3, 9} (mod 13), whereas our list of possible values of r is:

{5, 7, 11, 15, 19, 21} ≡ {5, 7, 11, 2, 6, 8} (mod 13)

On the other hand, if we assume r + 26 x does have a factor of 13, then so will r. But none of the possible values of r satisfies this condition either.

So we have proved:

Theorem 1: In any odd base, no integer has a reciprocal with a non-redundant pandigital reptend.

When we are performing modular arithmetic on the n integers 0, 1, ..., n–1, we refer to this set as Z_n. If we are only interested in addition, Z_n becomes what is known as a commutative group: a set with a single operation, +, that obeys all the usual rules for adding numbers, including the existence of an additive identity, 0, which leaves things unchanged when you add it, and additive inverses for every number x in the set, which you can add to x to get 0. In this case, we have:

x + (n–x) ≡ 0 (mod n)

If we also wish to perform multiplication, things become a bit more complicated. When we deal with the set of all integers, Z, we are already used to the fact that although there is a multiplicative identity, 1, which leaves things unchanged when you multiply with it, unlike the real numbers and the rational numbers, in the integers most numbers do not have a multiplicative inverse. The only integers with multiplicative inverses are 1 and –1, whereas every real number other than zero has a multiplicative inverse.

For Z_n, the situation can lie anywhere between these two extremes. If n is a prime number, then every number in Z_n other than zero does have a multiplicative inverse. For example, in Z₇:

1 × 1 ≡ 1 (mod 7)
2 × 4 ≡ 1 (mod 7)
3 × 5 ≡ 1 (mod 7)

But if n is not prime, then only those numbers that have no factor greater than 1 in common with n have multiplicative inverses. For example, in Z₈:

1 × 1 ≡ 1 (mod 8)
3 × 3 ≡ 1 (mod 8)
5 × 5 ≡ 1 (mod 8)
7 × 7 ≡ 1 (mod 8)
But 2, 4, 6 have no multiplicative inverses.

It is not hard to see why a number that has a factor f greater than 1 in common with n cannot have a multiplicative inverse in Z_n. If x is divisible by f then any multiple of x, say mx, will also be divisible by f, even when the product is greater than or equal to n and we subtract a multiple of n to keep the result in Z_n. But 1 plus any multiple of n is obviously not divisible by f, so mx can never be equivalent to 1.

Now, consider the subset of Z_n consisting of all elements that do not have any factor greater than 1 in common with n. We will call this Z_n^×.

Clearly 1 is in Z_n^×. If x and y are both in Z_n^×, can xy have a factor greater than 1 in common with n, say f? If it did, then any prime factor p of f would need to divide at least one of x and y, and would also divide n, contradicting our assumption. So, xy will also be in Z_n^×.

Furthermore, suppose x, y and z are all in Z_n^×, and xy ≡ xz (mod n). It follows that:

x (y – z) ≡ 0 (mod n)

In other words, n divides x (y – z). But since x and n have no factors greater than 1 in common, n must divide y – z. So we can conclude that:

For x, y and z in Z_n^×
xy ≡ xz (mod n) if and only if y ≡ z (mod n)

It then follows that if we multiply every element of Z_n^× by some x in Z_n^×, the products must all be distinct, and must be all the elements of Z_n^× itself, including 1. Since one of the products is 1, whatever we multiplied by x to produce 1 will be the unique multiplicative inverse of x.

Taken together, all the properties we have established for Z_n^× (along with the obvious fact that multiplication is associative) make it a commutative group, known as the multiplicative group of integers modulo n.

If n is prime, Z_n^× contains all the non-zero elements of Z_n, so every non-zero element of Z_n has a multiplicative inverse, as we claimed earlier. This means Z_n is an algebraic structure known as a field, like the real numbers.

When n is not prime, Z_n is a commutative ring with unity, which is the same kind of structure as the set of all integers, Z.

When n is prime, the size of Z_n^×, which we will write as |Z_n^×|, is just n–1. But in general, |Z_n^×| is given by Euler’s totient function, φ(n), which counts the numbers less than n that are relatively prime to n (which is just another way of saying that they share no factor with n greater than 1). Euler’s totient function can be evaluated directly, without checking all the numbers for this property individually, with the formula:

φ(n) = n Π_{Distinct primes p that divide n} (1 – 1/p)

Here Π is the symbol for a product, i.e. we are multiplying together the expression that follows, for each distinct prime p that divides n.

It was proved by Gauss that if and only if n is 1, 2, 4, p^k or 2 p^k, for p an odd prime, Z_n^× is a cyclic group, i.e. a group where every element is some integer power of a single element, known as the generator of the group.

Suppose we compute the digits in the base b representation of the reciprocal of some integer d that is relatively prime to b, i.e. they share no common factors greater than 1. Then b will belong to the group Z_d^×, as will all its integer powers. For example, if d=13 and b=10, as we saw earlier the powers of 10 (mod 13), starting from 10⁰, are {1, 10, 9, 12, 3, 4}. Note that in this case, since d is prime, we know immediately that |Z_d^×|=12, and it is no coincidence that the size of the set of powers of 10, which is 6, divides |Z_d^×|. The powers of 10 (mod 13) form a subgroup of the group Z_d^×, and the number of elements of any subgroup of a group must divide the number of elements of the group. In general, if d is relatively prime to b, the length of the reptend of 1/d must divide |Z_d^×| = φ(d).

Given the powers of 10 (mod 13), and knowing the representation for 1/13 in base 10, we can immediately write down the representations for six different fractions with 13 in the denominator. We just take the successive powers of 10 (mod 13) as the numerators, and rotate the digits in the reptend:

We can obtain the representations of the remaining six fractions by doubling the powers of 10 (mod 13) we use as the numerators:

2 &times {1, 10, 9, 12, 3, 4} ≡ {2, 7, 5, 11, 6, 8} (mod 13)

and doubling the reptend for 1/13 to obtain the six digits for 2/13, then rotating them as before:

In general, if d is relatively prime to b, then the powers of b will form a subgroup of Z_d^×, the subgroup generated by b, which can be written more succinctly as <b>. The size of <b> is called the multiplicative order of b modulo d. Either this subgroup <b> will be the entire group Z_d^×, and all fractions less than 1 with d in the denominator when written in lowest terms can be found by cycling the digits of the reptend, or it will comprise some smaller portion of Z_d^×, and the other fractions can be found by taking suitable multiples of <b>, producing reptends with different digits but the same length.

If d is prime, that will cover all the fractions 1/d, 2/d, ..., (d–1)/d. If d is composite, there will be some numerators in that list that are not relatively prime to d (and hence not in Z_d^×), so d will no longer be the denominator when the fraction is written in lowest terms. For those cases, the representation can be found by examining the numerator and denominator after cancelling any common factors.