4 ms·

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 num

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.

gus_massa 10y ago
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.
- wolfram74 10y ago
  Exploring this in other bases would be amusing, maybe not particularly enlightening though.
  - Someone 10y ago
    https://oeis.org/A166623 https://oeis.org/A166623
- AnimalMuppet 10y ago
  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.
Someone 10y ago
https://oeis.org/A046253 https://oeis.org/A046253 agrees, but adds 0 and 438579088, using 0^0 = 0. Also, http://mathworld.wolfram.com/MuenchhausenNumber.html 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)
- deleted 10y ago
  [deleted]

gus_massa 10y ago

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.

wolfram74 10y ago
Exploring this in other bases would be amusing, maybe not particularly enlightening though.
- Someone 10y ago
  https://oeis.org/A166623 https://oeis.org/A166623
AnimalMuppet 10y ago
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.

Someone 10y ago

https://oeis.org/A046253 https://oeis.org/A046253 agrees, but adds 0 and 438579088, using 0^0 = 0. Also, http://mathworld.wolfram.com/MuenchhausenNumber.html 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)

deleted 10y ago
[deleted]