Proving There are Only Six Dudeney Numbers
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) = 4Then 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 = 36We 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:
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: func [value [integer!] /local result] [
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: func [block [block!] item /local pos] [
if (1 < length? block) [
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
threeValues: array/initial 3 value
cubeExpression: interleave-block threeValues '*
; evaluate the expression to show it off
; could have also used: (value ** 3)
cube: first (reduce cubeExpression)
; express the digits of the cube as a sum
digits: make-digit-block cube
sumExpression: interleave-block digits '+
; now evaluate that sum
sum: first (reduce sumExpression)
; if we got the value back, it's a Dudeney!
if (sum == value) [
print mold compose [
(cube) = (cubeExpression)
and
(value) = (sumExpression)
]
]
]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?
Tags: rebol
December 24th, 2009 at 1:06 pm
Great article. It’s wonderful to see the thought process explained, so others can really learn from it.
December 24th, 2009 at 5:52 pm
Thanks Gregg!
It was interesting for me to try this. I didn’t study proofs of this kind in school (at least not that I remember :P). But I’ve read enough Wikipedia math articles on map coloring and distribution of primes to now grok the strategy of attack. Reading up on hard problems might not get you measurably closer to solving other unsolved problems, but it makes little puzzles like this look trivial by comparison!
I fixed up the code a little…but if anyone has ideas to improve it (that don’t involve taking out parentheses) let me know!
January 13th, 2010 at 11:46 am
Parentheses, yes there is useless one but I imagine it is for clarity purpose.
Anyway, nice demonstration !
Here is just another implementation for interleave-block :
interleave-block: func [block [block!] item /local pos] [
loop subtract length? block 1 [
block: insert next block item
]
return head block
]
if block length is 1 or 0, then no loop occurs, so no item is inserted.
November 19th, 2010 at 8:20 pm
I very much like your proof, but I have a minor improvement (unless I’ve missed something) that reduces the bound. Simply put, you substitute in for DigitCount(value^3) when you don’t have to. The log term in your bound on DigitCount will nicely remove the power for you, which decreases the constant term involved from 36 to 9, and the bound to about 55.
DigitSum(value^3)
<= 9 * DigitCount(value^3)
<=9*(log(value^3) + 1)
<=9*(3*log(value) + 1)
<=27*log(value) + 9
http://www.wolframalpha.com/input/?i=%289+%2B+27+*+log_10%28x%29%29+-+x+from+1+to+100
In terms of your proof, this bound doesn’t matter much, but it starts to be important if, like me, you’re looking at the equivalent of Dudeney numbers with powers much higher than 3.
~Zomega
December 20th, 2010 at 6:06 pm
@Zomega: Indeed, it seems choosing that order for the substitutions gives fewer cases to test!
April 9th, 2011 at 9:42 pm
May I borrow your program?
And I must say your proof is quite wonderful!
April 11th, 2011 at 2:43 pm
@steven - Sure! From http://hostilefork.com/legal/
“All short code samples presented in articles, unless otherwise marked, do not require attribution to when used in your own software. However, I will point out that it’s often very nice (for maintenance reasons) to link to the source of such information in a comment.”
June 19th, 2011 at 9:47 am
“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.”
Clarification:
Using Wolfram Alpha, you can find that the derivative of (36+27*log10(x))-x is 27/(x ln(10))-1, and this function stays at the negative part forever beyond a certain point. Therefore (36+27*log10(x))-x never goes up again.
June 21st, 2011 at 6:41 am
@Cloudy0: Such formalism is absolutely valuable, so thanks! Though once you start saying “derivative” and “ln” many people’s eyes glaze over. I don’t know if you’ve read Lockhart’s Lament or not, but his point about the “excessive” proof about intersecting lines and angles is something I’ll mention:
http://www.maa.org/devlin/LockhartsLament.pdf
It would be nice if we could drill down into an argument to the level of our curiosity. So if you want to know the exact zero you could click to see how to find it with the right equations, but if you’re willing to accept a “good enough for the purpose” approximation then you could just keep reading.
Some day they’ll finish A Young Lady’s Illustrated Primer
http://en.wikipedia.org/wiki/The_Diamond_Age