Feed Icon RSS 1.0 XML Feed available

Proving There are Only Six Dudeney Numbers

Date: 24-Dec-2009/6:30

Tags: , ,

Characters: (none)

I came across an article in Wikipedia about Dudeney numbers. These are numbers whose digit sum add up to their cube root:
    1 =  1 x  1 x  1   ;   1 = 1
  512 =  8 x  8 x  8   ;   8 = 5 + 1 + 2
 4913 = 17 x 17 x 17   ;  17 = 4 + 9 + 1 + 3
 5832 = 18 x 18 x 18   ;  18 = 5 + 8 + 3 + 2
17576 = 26 x 26 x 26   ;  26 = 1 + 7 + 5 + 7 + 6
19683 = 27 x 27 x 27   ;  27 = 1 + 9 + 6 + 8 + 3
The wiki page went on to proclaim that those are the only six such numbers. Somebody on the talk page asked where the proof was.
I poked on Google and didn't find anything, so I wondered if I could just prove it myself. Here's what I came up with off the cuff. Perhaps others would find it interesting.

Bounding From Above

Let us define DigitCount to be the number of decimal digits in a value, e.g.
DigitCount(132) = 3
DigitCount(9999) = 4
Then let us define DigitSum to be the sum of the values of digits in the decimal representation of a number. So for instance:
DigitSum(132) = 1 + 3 + 2 = 6
DigitSum(9999) = 9 + 9 + 9 + 9 = 36
We can see that for any n-digit number, the largest possible digit sum is the case where all those digits are 9. To put this a little more formally:
DigitSum(value) <= 9 * DigitCount(value)
Another interesting property is that an n-digit number will have at most as many digits as the cube of a 1 followed by n zeroes. (So for instance 1000^^3 will always have a greater or equal number of digits than 999^^3.)
Now let's put that together with the fact that if you cube a 1 followed by n zeroes then it will have 3 * n + 1 digits:
DigitCount(value^3) <= 3 * DigitCount(value) + 1
One last thing we need is a mathematical way of expressing a maximum bound on the number of digits, and that comes from the base 10 logarithm:
DigitCount(value) <= log(value) + 1

Limiting The Search Space

In this case, I want to show that once value becomes a certain size, even a generous overestimate of what possible value DigitSum(value^3) could have is going to be less than value (hence not equal, and not meeting the requirement to be a Dudeney number). So let's apply the bounds. Since we're working with <= and not = it's okay for me to substitute any expression which is known to be larger or equal to the previous value... the inequality will still hold true:
DigitSum(value^^3)
    <= 9 * DigitCount(value^^3) 
    <= 9 * (3 * DigitCount(value) + 1)
    <= 9 + 27 * DigitCount(value)
    <= 9 + 27 * (log(value) + 1)
    <= 36 + 27 * log(value)
Remember that we are looking for Dudeney numbers where this rule holds:
value = DigitSum(value^3)
Let's mutate this into the question "find a boundary above which value must always be greater than DigitSum(value^3)". It would be nice to find a minimal boundary, but any boundary is better than nothing. Using our simple case we look to find where:
value > 36 + 27 * log(value)
Wolfram Alpha is here to help with this:
We just look for where the crossover is in this plot:
Dudeney Equation
Dudeney Graph
88 is the last number for which the right hand side is bigger than the left, and from then on we know that log(value)—even multiplied by a constant and added to another constant—will not have the possibility of catching up with value again.

Brute Force The Remaining Possibilities

89 is probably not the best bound we could find. But it didn't need any advanced math knowledge to get to. Now the only remaining thing to do is let the computer pick up the slack and try from 1 to 88. If the claim is true, we should only find those six numbers.
Easy program to write in any programming language. But I'll use Rebol just to show how nicely it can format the output for us without too much overhead:
; This generates a block of integers containing the decimal
; digits of an integer's absolute value, e.g.
;    >> make-digit-block 123
;    == [1 2 3]

make-digit-block: function [value [integer!]] [
    result: copy []

    foreach ch (to-string abs (value)) [
        append result (to-integer (to-string ch))
    ]

    return result
]

; This interleave function puts a value between elements
; in a block, e.g.:
;     >> interleave-block [a b c] 'FOO
;     == [a FOO b FOO c]

interleave-block: function [block [block!] item] [ 
    pos: next block
    while [not tail? pos] [
        pos: next (insert pos item)
    ]

    return block
]

; Now we loop from 1 to 88 and test each for Dudeney-ness

for value 1 88 1 [
    ; make an expression of cube as a product
    three-values: array/initial 3 value
    cube-expression: interleave-block three-values '*

    ; evaluate the expression to show it off
    ; could have also used: (value ** 3)
    cube: first (reduce cube-expression)

    ; express the digits of the cube as a sum
    digits: make-digit-block cube
    sum-expression: interleave-block digits '+

    ; now evaluate that sum
    sum: first (reduce sum-expression)

    ; if we got the value back, it's a Dudeney!
    if (sum = value) [
        print mold compose [
            (cube) = (cube-expression)
            and
            (value) = (sum-expression)
        ]
    ]
]
The output of the program is:
[1 = 1 * 1 * 1 and 1 = 1]

[512 = 8 * 8 * 8 and 8 = 5 + 1 + 2]

[4913 = 17 * 17 * 17 and 17 = 4 + 9 + 1 + 3]

[5832 = 18 * 18 * 18 and 18 = 5 + 8 + 3 + 2]

[17576 = 26 * 26 * 26 and 26 = 1 + 7 + 5 + 7 + 6]

[19683 = 27 * 27 * 27 and 27 = 1 + 9 + 6 + 8 + 3]
That's it!
Notice how Rebol lets us build a symbolic structure to represent the sums and products. That structure can be reflected, evaluated, and "molded" into output. It actually builds blocks of symbols like [4 + 9 + 1 + 3]. Then it "evals" it (using reduce) to get back a single-element list [26]. Finally it picks the first and only item out of that block to get the result as a value.
Pretty nifty, eh? And isn't it much more natural looking than Lisp, with all those parentheses and CAR and CDR?
Currently I am experimenting with using Disqus for comments, however it is configured that you don't have to log in or tie it to an account. Simply check the "I'd rather post as a guest" button that appears after you begin typing in a name.
comments powered by Disqus
Copyright (c) 2007-2014 hostilefork.com

Project names and graphic designs are All Rights Reserved, unless otherwise noted. Software codebases are governed by licenses included in their distributions. Posts on blog.hostilefork.com are licensed under the Creative Commons BY-NC-SA 4.0 license, and may be excerpted or adapted under the terms of that license for noncommercial purposes.