Cubes with non-decreasing digits

by David Radcliffe

Let us say that a number has non-decreasing digits if each decimal digit is greater than or equal to the previous digit. It is not hard to show that there are infinitely many squares that have non-decreasing digits, but are there infinitely many cubes with that property?

The first few cubes with non-decreasing digits are 0, 1, 8, 27, and 125, but it seems hard to find any other examples. I wrote a Python program to search for these elusive cubes.

There are two key ideas which reduce the search space. The first idea is that n^3 cannot have non-decreasing digits if n \equiv 0 \pmod{10} or n \equiv 1 \pmod{10}, except when n = 0 or n = 1. The second idea is the following. If n^3 has non-decreasing digits and n \equiv a \pmod{10^d}, then (a^3 \mod 10^d) must also have non-decreasing digits. These two ideas allow us to avoid checking most of the cubes in our range.

The diagram below shows part of the search tree. Each node is a string of decimal digits, which can be represented as a pair (n, d) such that 0 \le n < 10^d. The node (n, d) is circled in green if the last d digits of n^3 are non-decreasing; otherwise it is circled in red. The search algorithm only examines the children of green nodes. The red nodes are “dead”.

I implemented these ideas in the Python code listed below, and I determined that 125 is the largest cube less than 10^{60} whose digits are non-decreasing. The search took 65 minutes and it examined 247,962,478 cubes.

from time import time

start = time()
itercount = 0  # Counts the number of cubes that are tested.

# Tests whether the digits of n are non-decreasing.
def ndd(n):
    global itercount
    itercount += 1
    d1 = 9
    while n:
        d1, d2 = n % 10, d1
        if d1 > d2:
            return False
        n /= 10
    return True

# Finds all positive integers n having d digits or fewer
# such that the digits of n^3 are non-decreasing.

def monotone_cubes(d):

    # This helper function finds all positive integers n < N
    # with n = a (mod M) such that the digits of n^3
    # are non-decreasing.
    # It is assumed that M and N are powers of 10.

    def mc(a,M,N):
        if M == N:
            if ndd(a**3):
                print a, a**3
        elif ndd(a**3 % M):
            for d in range(10):
                n = a + M*d
                mc(n,10*M,N)

    print 1, 1
    for a in range(2,10):
        mc(a,10,10**d)

monotone_cubes(20)
print 'Iterations:', itercount
print 'Time:', time()-start, 'seconds.'

(This post replaces a previous version, that unfortunately had a bug.)

Advertisements