Mahler’s Quinary Conundrum

The following question was posed by the German mathematician Kurt Mahler (1903 – 1988) in a letter that he wrote to Alf van der Poorten.

I am interested in the problem of whether there are squares of integers which, to the base g = 5, have only digits 0 or 1. I could not find a single example although I went quite far on my calculator.

Now some examples come immediately to mind. If \( n = 5^k\) then \( n^2 = 5^{2k}\) which is expressed in base 5 as \( 1000\ldots0\) with \( 2k\) zeros. But these solutions are trivial. We are more interested in solutions that are not divisible by 5, since they generate all other solutions. If \( n^2\) has only digits 0 or 1, then the same is true for \( (5^k \cdot n)^2\) and conversely. (The word “digits” always refers to base 5 digits in this note.)

I wrote a Python script to search for examples. The first step is to write a function to check if a number has only digits 0 or 1 in a given base.

def check(n, base):
    while n > 0:
        if n % base > 1:
            return False
        n = n // base
    return True

We could use this function to search for examples directly, but this is inefficient.

def naive_search(N):
    for n in range(N):
        if n % 5 > 0 and check(n*n, 5):
            yield n

It is inefficient because we are checking many values that could have been excluded from the outset. For example, the last digit of n must be 1 or 4, otherwise the last digit of \( n^2\) would be 4. We can find similar conditions on the last two digits, the last three digits, and so on.

  • The last two digits of n must be 01, 14, 31, or 44.
  • The last three digits of n must be 001, 031, 114, 144, 301, 331, 414, or 444.
  • The last four digits of n must be 0001, 0301, 0331, 0414, 1444, 2031, 2114, 2144, 2301, 2331, 2414, 3001, 4031, 4114, 4144, or 4444.

In fact, the number of possible \( k\)-digit endings is \( 2^k\). Each \( k\)-digit ending gives birth to two \( (k+1)\)-digit endings by adding digits to the left. I will leave it to the reader to prove this fact.

Here is a Python function that generates the possible \( k\)-digit endings. It works recursively by generating and extending the possible \( (k-1)\)-digit endings.

def gen(k):
    if k == 1:
        yield 1
        yield 4
    else:
        P = 5 ** (k-1)
        for n in gen(k-1):
            x = (n*n) // P
            delta = 2 * (n % 5) % 5
            d = x % 5
            m = n
            for a in range(5):
                if d < 2:
                    yield m
                d = (d + delta) % 5
                m += P        

The final step is to feed these candidates into our digit checker. By this means, I was able to find all positive integers n less than \( 5^{32} \approx 2.3 \times 10^{22}\) and not divisible by 5 such that \( n^2\) has only digits 0 or 1 when written in base 5.

results = sorted([n for n in gen(32) 
                    if check(n*n, 5)])

Results: 1, 972799, 3051273374, 6132750376, 839228035909, 3818357814376, 2384643515634376, 1490173338867234376, 931329727148437734376.

If we write these numbers in base 5, a pattern becomes apparent. Here is a Python script that converts the numbers to base 5.

def toBase5(n):
    if n < 5: 
        return n
    return 10 * toBase5(n//5) + (n % 5)

for n in results:
    print (toBase5(n))

# Base 10 Base 5
1 1 1
2 972799 222112144
3 3051273374 22222111221444
4 6132750376 100024441003001
5 839228035909 102222214334122114
6 3818357814376 1000024444100030001
7 2384643515634376 10000024444410000300001
8 1490173338867234376 100000024444441000003000001
9 931329727148437734376 1000000024444444100000030000001

One sees a similarity between the fourth, sixth, seventh, eighth, and ninth terms of this sequence. The runs of 0s and 4s increase by one in each step. This can be described by a polynomial function. If \( P(x) = 25x^4 + 15x^3 – 4x^2 + 3x + 1\) then these terms are \( P(5^3), P(5^4), P(5^5), P(5^6)\), and \( P(5^7)\).

We can verify that

$$
\begin{align*}
[P(x)]^2 & = 625x^8+750x^7+25x^6+30x^5 \\
& + 156x^4+6x^3+x^2+6x+1.
\end{align*}
$$

Note that the coefficients are positive integers less than \( 5^5\) and they can be written in base 5 using only 0s and 1s. Therefore, \( (P(5^k))^2\) has only digits 0 or 1 for all \( k \ge 3\).

This gives a striking, albeit partial, answer to Mahler’s question. There exist infinitely many squares that are not divisible by 5, but which have only the digits 0 or 1 when written in base 5.

Credits: Thanks to Gary Davis (@republicofmath) for bringing this problem to my attention. The problem is mentioned in the article The Legacy of Kurt Mahler, which appears in the May 2015 edition of the Notices of the American Mathematical Society.

One thought on “Mahler’s Quinary Conundrum”

Leave a Reply

Your email address will not be published. Required fields are marked *