mersenneforum.org  

Go Back   mersenneforum.org > Fun Stuff > Puzzles

Reply
 
Thread Tools
Old 2020-06-21, 05:20   #1
miroslavkures
 
Sep 2018

2×3 Posts
Default Münchhausen numbers of length 3

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
miroslavkures is offline   Reply With Quote
Old 2020-06-21, 06:04   #2
axn
 
axn's Avatar
 
Jun 2003

22×32×131 Posts
Default

904:[1, 7, 1]:823545
axn is offline   Reply With Quote
Old 2020-06-21, 15:39   #3
miroslavkures
 
Sep 2018

2×3 Posts
Default

Great!
miroslavkures is offline   Reply With Quote
Old 2020-06-21, 16:19   #4
uau
 
Jan 2017

79 Posts
Default

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.
uau is offline   Reply With Quote
Old 2020-06-21, 20:53   #5
Dylan14
 
Dylan14's Avatar
 
"Dylan"
Mar 2017

3×173 Posts
Default

So I wrote some code in Python to test this:

Code:
#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.
Dylan14 is offline   Reply With Quote
Old 2020-06-21, 22:56   #6
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

17×83 Posts
Default

Quote:
Originally Posted by uau View Post
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.
R. Gerbicz is offline   Reply With Quote
Old 2020-06-21, 23:21   #7
uau
 
Jan 2017

79 Posts
Default

Quote:
Originally Posted by Dylan14 View Post
So I wrote some code in Python to test this:
Quote:
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):
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 is offline   Reply With Quote
Old 2020-06-21, 23:26   #8
uau
 
Jan 2017

4F16 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
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...
uau is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
fft length changes JPL Information & Answers 5 2018-11-13 22:12
Algorithm for finding arbitrary length prime numbers mikenickaloff Miscellaneous Math 3 2018-08-30 18:12
Help with FFT length Gradient Software 3 2013-12-16 01:53
FFT Length Samoflan Information & Answers 8 2010-02-16 22:05
FFt length mack Information & Answers 1 2009-09-06 03:24

All times are UTC. The time now is 12:22.

Wed Oct 28 12:22:43 UTC 2020 up 48 days, 9:33, 1 user, load averages: 1.61, 1.64, 1.63

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2020, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.