Re:Munchausen Numbers and How to Find Them
by eridius on Wednesday September 21, 2016 @04:08PM
(#12551774)
The initial example seems broken. In Safari, it looks like
3³ + 4⁴ + 3³ + 5⁵ = 343533+44+33+55=3435
This is apparently because it shows the same example in two different ways in the HTML, the first using MathML (which renders the superscripts), and the second using straight HTML (which doesn't handle the superscripts properly).
In Chrome it's broken a bit differently. Here it render as
Re:Munchausen Numbers and How to Find Them
by zacharydenton on Thursday September 22, 2016 @12:04AM
(#12554247)
Thanks, this post has been converted through several different blog engines over the years and I hadn't noticed the rendering was broken until now. It's meant to look more like https://zach.se/project-euler-solutions/48/.
Re:Munchausen Numbers and How to Find Them
by cperciva on Wednesday September 21, 2016 @07:01PM
(#12553037)
This unintentionally but very clearly demonstrates how a few minutes of thought can save a much longer period of computation. Rather than testing all of the integers between 1 and 500,000,000 (as in the article) or between 1 and 10 * 9^9 (for the trivial upper bound), we can simply test all of the multisets of 10 digits -- of which there are a mere 92378. (Or multisets of up to 10 digits if you take 0^0 = 1, in which case you must consider 184755 possibilities.)
Re:Munchausen Numbers and How to Find Them
by zeveb on Wednesday September 21, 2016 @05:03PM
(#12552233)
Here's a version in Lisp:
(defun münchhausen-p (i)
(eq (loop for number = i then quotient
for (quotient remainder) = (multiple-value-list (floor number 10))
sum (expt remainder remainder)
until (zerop quotient))
i))
(loop for i from 1 to 500000000 when (münchhausen-p i) do (print i))
It takes .002 seconds to check the first 5,000 integers, 2.108 for the first 5,000,000 and 268.867 seconds for the first 500,000,000.
I'm sure there could be some clever tricks to make it run faster, but this is probably good enough, given that there are, I think, only two such numbers.
Re:Munchausen Numbers and How to Find Them
by AnimalMuppet on Wednesday September 21, 2016 @05:31PM
(#12552440)
Well, 9^9 = 387,420,489. So a ten-digit Munchausen number that had enough nines in it could be as big as 3,874,204,890. So going to 500,000,000 isn't quite enough. You can stop at 4 billion, though...
Re:Munchausen Numbers and How to Find Them
by wolfram74 on Wednesday September 21, 2016 @04:33PM
(#12551954)
someone can spot check me, but since 9^9 = 387420489 < 10^9, there can't be any Munchausen numbers larger than 10^10 as it there's no way for the sum of 10 numbers less than 10^9 is equal to a number larger than 10^10. I feel like the statement that only 1 and 3435 are Munchausen numbers should have been proven by exhaustion by now.
Re:Munchausen Numbers and How to Find Them
by gus_massa on Wednesday September 21, 2016 @05:15PM
(#12552311)
Almost. The numbers can be repeated, if N = 999999999 then Mun(N) = 9 * 9^9 = 3486784401 ~=3.5E9. But the general idea is correct.
[spoiler alert] If we assume that the number N has D digits, then
10^(D-1) <= N < 10^D
Now, N has D digits, and each one can be at most 9, so
Mun(N) <= 9^9 * D = 387420489 * D < 10^9 * D
If we assume that there exist a number N that is a Munchausen number with D digits, then N = Mun(N) so we can combine the left part of the first equation with the right part of the second equation
10^(D-1) <= N = Mun(N) < 10^9 * D
If we only keep the extreme parts of the inequality
10^(D-1) < 10^9 * D
And now we can take log (in base 10)
D-1 < 9 + log(D)
And put all the D in the left side:
D – log(D) < 10
Taking the derivatives, the function f(x)=x-log(x) is essentially increasing if x is big enough, probably when x>1 or x>2, I'm a bit lazy. (Remember to use the ln(10) in the derivative because we are using log=log_10 instead of ln=log_e.)
So we have only to find a value of D that is big enough. For example, if D=12, then
12-log(12) > 12-log(100) = 12-2 = 10
So if D is 12 or more, we have a contradiction, so there are no Munchausen numbers with 12 digits or more.
A more careful analysis can reduce this value a little, but a for between 1 and 10^12-1 to test all the cases should finish in a modern computer in a reasonable time, specially replacing the pow(n, n) calculation with a cached value.
these numbers "raise themselves" analogously to way in which Baron Hieronymus von Münchhausen allegedly raised himself by riding a cannonball.
I would think it refers to bootstrapping (the baron pulled himself out of a morass by pulling on his bootstraps)
And for those playing with this in their favorite language: I would precompute an array of ten d^d values and hoist the d^d computation out of the loop for a very nice speed up.
Finally: int may not be sufficient in C if you iterate up to 9 digits. 9^9 needs 29 bits => 999,999,999 would need over 32 => unsigned int already is living very dangerously (probably too dangerously)
Re:Munchausen Numbers and How to Find Them
by reikonomusha on Wednesday September 21, 2016 @05:23PM
(#12552387)
> Here’s the program written in Python. I used it to find every Munchausen number less than 500,000,000. After thirty minutes or so of intense computation, it turns out that the only Munchausen numbers are 1 and 3435.
This is an awfully long time to wait for something that is very clearly optimizable. If we are searching for Munchausen numbers, then we are probably going to do so in a brute force way. (We could optimize this with various symmetries, such as digit permutations, but let's ignore this for now.)
If we are going to brute force it, then we are probably not going to exceed 64-bits, which means we can avoid using bignums altogether. Written correctly, this would be extremely fast in C.
With this code [0], on my machine, with only meager optimization effort (not thinking too hard about things other than data types), I can go through 3 billion in less than a minute:
> (time (find-munchausen 3000000000))
Computing all Munchausen numbers below three billion.
Evaluation took:
57.087 seconds of real time
57.059879 seconds of total run time (56.840355 user, 0.219524 system)
99.95% CPU
159,836,797,604 processor cycles
401,488 bytes consed
(0 1 3435 438579088)
The assembly code for the Munchausen test is relatively tight (though not at all as good as handwritten, of course), which makes evident why we check so quickly.
Re:Munchausen Numbers and How to Find Them
by lokedhs on Wednesday September 21, 2016 @11:11PM
(#12554053)
I find it quite remarakable that Python is so popular with maths people, even though it's so horribly slow. I've seen similar differences between SBCL and Python quite often, when I have tried reimplmenting code like that in Common Lisp.
In Chrome it's broken a bit differently. Here it render as
This is similar to the Safari version except Chrome apparently doesn't support MathML so it renders the annotation instead (\displaystyle 3^3 + …)or: https://web.archive.org/web/20091027122658/http://geocities.... (Armstrong) Numbers
I'm sure there could be some clever tricks to make it run faster, but this is probably good enough, given that there are, I think, only two such numbers.
/me ducks.
[spoiler alert] If we assume that the number N has D digits, then
Now, N has D digits, and each one can be at most 9, so If we assume that there exist a number N that is a Munchausen number with D digits, then N = Mun(N) so we can combine the left part of the first equation with the right part of the second equation If we only keep the extreme parts of the inequality And now we can take log (in base 10) And put all the D in the left side: Taking the derivatives, the function f(x)=x-log(x) is essentially increasing if x is big enough, probably when x>1 or x>2, I'm a bit lazy. (Remember to use the ln(10) in the derivative because we are using log=log_10 instead of ln=log_e.)So we have only to find a value of D that is big enough. For example, if D=12, then
So if D is 12 or more, we have a contradiction, so there are no Munchausen numbers with 12 digits or more.A more careful analysis can reduce this value a little, but a for between 1 and 10^12-1 to test all the cases should finish in a modern computer in a reasonable time, specially replacing the pow(n, n) calculation with a cached value.
For a 10-digit number, Mun(N) <= 10 * 9^9 = 3,874,204,890. So you can stop there.
Also, http://mathworld.wolfram.com/MuenchhausenNumber.html gives an explanation why they are called Münchhausen Numbers. It states:
these numbers "raise themselves" analogously to way in which Baron Hieronymus von Münchhausen allegedly raised himself by riding a cannonball.
I would think it refers to bootstrapping (the baron pulled himself out of a morass by pulling on his bootstraps)
And for those playing with this in their favorite language: I would precompute an array of ten d^d values and hoist the d^d computation out of the loop for a very nice speed up.
Finally: int may not be sufficient in C if you iterate up to 9 digits. 9^9 needs 29 bits => 999,999,999 would need over 32 => unsigned int already is living very dangerously (probably too dangerously)
This is an awfully long time to wait for something that is very clearly optimizable. If we are searching for Munchausen numbers, then we are probably going to do so in a brute force way. (We could optimize this with various symmetries, such as digit permutations, but let's ignore this for now.)
If we are going to brute force it, then we are probably not going to exceed 64-bits, which means we can avoid using bignums altogether. Written correctly, this would be extremely fast in C.
With this code [0], on my machine, with only meager optimization effort (not thinking too hard about things other than data types), I can go through 3 billion in less than a minute:
The assembly code for the Munchausen test is relatively tight (though not at all as good as handwritten, of course), which makes evident why we check so quickly. [0] https://bitbucket.org/tarballs_are_good/lisp-random/raw/mast...It's popular because of Numpy/Scipy, then the speed of native loops doesn't matter.