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 cannot have non-decreasing digits if or , except when or . The second idea is the following. If has non-decreasing digits and , then 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 such that . The node is circled in green if the last d digits of 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 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.)