Münchhausen numbers of length 3

[miroslavkures]

3435 is well-known as the Münchhausen number in the base 10 and its length (number of digits) is 4.

Are there infinitely many Münchhausen numbers of length 3?

Please visit http://searchfornumbers.blogspot.com...-length-3.html

[axn]

904:[1, 7, 1]:823545

[miroslavkures]

Great!

[uau]

No larger solutions with less than 1000 base-10 digits. Given the three digits, you can solve for base as a second-degree polynomial. I checked that all triples with largest digit in [8, 400[ give irrational bases, and 400^400 would have 1041 base-10 digits.

[Dylan14]

So I wrote some code in Python to test this:

#Python script to find Munchhausen numbers for some base and length
#A Munchhausen Number is a number equal to the sum of it's digits
#raised to each digit's power.
#For example, in base 10 3435 is a Munchhausen number, since
#3435 = 3*10^3+4*10^2+3*10+5 and 3435 = 3^3+4^4+3^3+5^5=27+27+256+3125.
#The question posed here: https://mersenneforum.org/showpost.php?p=548680&postcount=1
#are there infinitely many Munchhausen numbers with length 3?

#first, we define a function for the sum of the digits raised to each digit's power.
def sum_digits_raised(digits):
    '''Takes a list of integers and sums up the powers of them.'''
    digitpowersum = 0
    for digit in digits:
        if digit < 0:
            raise ValueError("Digit needs to be non-negative.")
        digitpowersum += pow(digit, digit)
        #print(digitpowersum)
    return digitpowersum
    
#as a check, run the list [3,4,3,5]. It should yield 3435
#print(sum_digits_raised([3,4,3,5]))

#Now, we define a function to translate from base n to base 10.
def tobase10(orig_base, digits):
    '''Converts a list of digits in base orig_base into a number in base 10.'''
    base10num = 0
    i = len(digits)-1
    for digit in digits:
        base10num += digit*pow(orig_base, i)
        i -= 1
    return base10num

#check on [3,4,3,5] in base 10
#print(tobase10(10, [3,4,3,5]))

#Now we want to run for length 3 and base all the possible digit combinations.
base = 904
biggestlefthandside = tobase10(base, [base-1,base-1,base-1])
#this works for length 3, the problem at hand.
for i in range(0, base+1):
    for j in range(0, base+1):
        for k in range(0, base+1):
            digits = [i,j,k]
            righthandside = sum_digits_raised(digits)
            #the biggest we could hope the left hand side to be is 
            #(base-1)*base^(length-1)+(base-1)*base^(length-2)+...+base-1
            #so if the right hand side is bigger than that there's no way the lefthand side will be the same as the right.
            if righthandside > biggestlefthandside:
                continue
            lefthandside = tobase10(base, digits)
            if lefthandside == righthandside:
                print(i, j, k, str(tobase10(base, digits)))
    print("Incrementing i to " + str(i+1))

Using this, I did confirm axn's find and the original number, 823545. It's a bit better than brute forcing, since it won't compute the base 10 conversion of the number if the sum of the digits raised to the power of the digit is bigger than the largest possible conversion. But it is still pretty slow.

[R. Gerbicz]

Originally Posted by uau

No larger solutions with less than 1000 base-10 digits. Given the three digits, you can solve for base as a second-degree polynomial. I checked that all triples with largest digit in [8, 400[ give irrational bases, and 400^400 would have 1041 base-10 digits.

A faster approach: if the discriminant is not a square then you can eliminate that triplet. With that you don't even need to calculate the coefficients, just check for ~50 smallest primes if the discriminant is a quadratic residue or not. Very likely there will be no larger solution.

[uau]

Originally Posted by Dylan14

So I wrote some code in Python to test this:

But it is still pretty slow.

Here's a more reasonable way to search a fixed base for solutions (seems to be about ten thousand times as fast as your code):

base = 904
p = [i**i for i in range(base)]
d = {pi-i:i for i, pi in enumerate(p)}
for i in range(base):
    ni = base*base*i - p[i]
    for j in range(base):
        if ni + base*j - p[j] in d:
            print(i, j, d[ni+base*j-p[j]])

[uau]

Originally Posted by R. Gerbicz

A faster approach: if the discriminant is not a square then you can eliminate that triplet. With that you don't even need to calculate the coefficients, just check for ~50 smallest primes if the discriminant is a quadratic residue or not. Very likely there will be no larger solution.

Separating the check per prime does sound like it could give a speedup (current code calculates the discriminant and uses Sage's is_square()). But as you say, it feels pretty unlikely that there would actually exist a 1000+ digit solution, which lowers my motivation to try implementing this...