News for hackers. Stuff that matters.
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.

Re:Munchausen Numbers and How to Find Them by AnimalMuppet on Wednesday September 21, 2016 @05:38PM (#12552501)
For an 11-digit number, Mun(N) <= 11 * 9^9 = 4,261,625,379 - which only has 10 digits. Therefore, no Munchausen number can have 11 (or more) digits.

For a 10-digit number, Mun(N) <= 10 * 9^9 = 3,874,204,890. So you can stop there.

Re:Munchausen Numbers and How to Find Them by wolfram74 on Wednesday September 21, 2016 @05:19PM (#12552343)
Exploring this in other bases would be amusing, maybe not particularly enlightening though.
Re:Munchausen Numbers and How to Find Them by Someone on Wednesday September 21, 2016 @05:42PM (#12552519)
Re:Munchausen Numbers and How to Find Them by Someone on Wednesday September 21, 2016 @05:30PM (#12552439)
https://oeis.org/A046253 agrees, but adds 0 and 438579088, using 0^0 = 0.

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)