### Cubes with non-decreasing digits

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.)