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 10003 will always have a greater or equal number of digits than 9993.)
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<sup>3</sup>) <= 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(value3) 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. So we know DigitSum(value3):
- <= 9 * DigitCount(value3)
- <= 9 * (3 * DigitCount(value) + 1)
- <= 9 + 27 * DigitCount(value)
- <= 9 + 27 * (log(value) + 1)
- <= 36 + 27 * log(value)
Note
Remember that we are looking for Dudeney numbers where
value = DigitSum(value3)
Let's mutate this into the question "find a boundary above which
value must always be greater than DigitSum(value3)". 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:
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?