## Muenchhausen Numbers

### December 6, 2019

A radix-10 number is a Muenchhausen number if it is equal to the sum of its digits, each digit raised to the power of itself. For instance, 3435 is a Muenchhausen number because 3**3 + 4**4 + 3**3 + 5**5 = 3435. Strict Muenchhausen numbers do not permit 0 as a digit, because 0**0 is undefined. Variant Muenchhausen numbers permit 0 as a digit, with 0**0 defined as 0. Muenchhausen numbers also exist with radices other than 10.

Your task is to find all the Muenchhausen numbers in radix-10. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

### 8 Responses to “Muenchhausen Numbers”

1. Zack said

Here is my take on this in Julia (v. 1.1.1): https://pastebin.com/eppLUrZb

The result is this (fairly short) array: 1, 3435, 438579088

Note that I used the strict definition of Muenchhausen numbers, as it makes for a more interesting collection of numbers. Also, I set a limit of 1 billion when searching through the integer space to save time. Besides, it’s quite unlikely that there are any Muenchhausen numbers larger than that.

Have a nice weekend!

2. matthew said

Here’s a variation on that algorithm by Chai Wah Wu on http://oeis.org/A166623: generate all digit combinations of length up to radix+2 (this covers the range 2r^r), calculate the digit sum, then see if that sum has the same digits as the original combination – if so, we have a Münchhausen number. Use 0 or 1 for “zeroval” to set the assumed value for 0^0:

```def nextcombo(a,limit):
"""
Lexicographically next combination (with replacement)
If last for length, change to first for length+1
"""
for i in range(1,len(a)+1):
if a[-i] < limit-1:
a[-i] += 1
for j in range(1,i):
a[-j] = a[-i]
break
else:
a[:] = *(len(a)+1)

def digits(n,r):
""" (Reversed) digits of n in radix r """
if n == 0: return 
s = []
while n != 0:
s.append(n%r)
n //= r
return s

def münch(r, zeroval):
""" Return list of Münchhausen numbers for radix r """
digivals = [zeroval]+[d**d for d in range(1,r)]
res = []
s = 
while len(s) <= r+2:
dsum = sum(digivals[d] for d in s)
if sorted(digits(dsum, r)) == s:
res.append(dsum)
nextcombo(s,r)
return sorted(res)

```
3. matthew said

That python program runs happily up to radix 15, but I got bored waiting for hexadecimal, so converted it into C++, which finds 1, c76712ffc311e6e and c4ef722b782c26f, along with c4ef722b7820c2f and 123b2309ff572f6b if we put 0^0 = 0 (not the usual convention). Calculations are done with uint64_t which gives just enough bits to check up to 16^16, which is apparently an adequate bound. There is a possibility that the sum might wrap around and we get a false positive, but that doesn’t seem to happen here. Results agree with https://github.com/elizarov/MunchausenNumbers/ which has an interesting meet-in-the-middle algorithm.

Runtime is about 40 seconds with g++ -O3

```#include <stdint.h>
#include <stdio.h>
#include <algorithm>
bool nextcombo(int *a, int len,int limit) {
for (int i = len-1; i >= 0; i--) {
if (a[i] < limit-1) {
a[i] += 1;
for (int j = i+1; j < len; j++) {
a[j] = a[i];
}
return true;
}
}
return false;
}

int getdigits(uint64_t n, int r, int *a) {
int i = 0;
if (n == 0) a[i++] = 0;
else while (n != 0) {
a[i++] = n%r;
n /= r;
}
return i;
}

uint64_t ipow(uint64_t n, uint64_t m) {
if (m == 0) return 1;
if (m == 1) return n;
uint64_t t = ipow(n,m/2);
if (m%2 == 1) return n*t*t;
else return t*t;
}

int main() {
int N = 16, a[N];
uint64_t digival[N];
digival = 1;
for (int i = 1; i < N; i++) digival[i] = ipow(i,i);
for (int n = 1; n <= N; n++) {
for (int i = 0; i < n; i++) a[i] = 0;
do {
uint64_t sum = 0;
for (int i = 0; i < n; i++) sum += digival[a[i]];
int digits[N];
int dlen = getdigits(sum,N,digits);
if (dlen == n) {
std::sort(digits,digits+dlen);
for (int i = 0; i < dlen; i++) {
if (digits[i] != a[i]) {
goto end;
}
}
printf("%lx\n",sum);
}
end:;
} while (nextcombo(a,n,N));
}
}
```
4. matthew said

Python just got finished radix 16, so here are the full results with 0^0 = 1, and numbers in their proper radixes:

```2: 1, 10
3: 1, 12, 22
4: 1, 131, 313
5: 1
6: 1, 22352, 23452
7: 1, 13454
8: 1
9: 1, 31, 156262, 1656547
10: 1, 3435
11: 1, 18453278, 18453487
12: 1, 3a67a54832
13: 1, 33661, 2aa834668a, 4ca92a233518, 4ca92a233538
14: 1, 23, 26036, 45a0a04513cc, a992b5d96720d
15: 1, 4b1648420dcd0, 5a99e538339a43, 5acbc41c19e333, 5acbc41c19e400, 5d0b197c25e056
16: 1, c4ef722b782c26f, c76712ffc311e6e
```
5. learn some maths said

0^0 = 1, not undefined.

6. Zack said

Also, this video can help shed some light on the 0^0 topic: https://youtu.be/UKqoXMyp4_U

Whatever the case, it’s always useful to remember that the Mathematics we is largely based on conventions and assumptions we have made about certain matters (e.g. Euclid’s axiom about the parallel lines). So, regardless of what 0^0 is in reality (if there is a way to access that kind of truth), what we accept it to be may be a matter of debate. In my experience as an engineer / scientist, figuring out a solution to a problem using Math is much more useful than any philosophical discussions about Math properties. I hope that helps. Cheers!

7. Steve said

Klong version 20190209

```
t::0,1_{x^x}'!10
[0 1 4 27 256 3125 46656 823543 16777216 387420489]

f::{[n s]; n::\$x; s::0; x=+/{[n2]; t@n2::1:\$\$x}'n}