30
\$\begingroup\$

A Munchausen Number in base \$b\$, also known as a Perfect digit-to-digit invariant or PDDI is a peculiar type of positive integer where the sum of its base-\$b\$ digits raised to themselves is equal to the number itself. They are named for the fictional Baron Munchausen, who apparently hoisted himself up via his own ponytail to save himself from drowning. A related concept is Narcissistic numbers.

For instance, \$1\$ is trivially a Munchausen number in every base because \$1^1=1\$. Additionally, every positive integer is a base-1 Munchausen number by definition.

More interestingly, \$3435\$ is a base-10 Munchausen number because \$3^3+4^4+3^3+5^5=3435\$, and in fact is the only other base-10 Munchausen number.

A partial list of Munchausen numbers in every base up to 35 can be found on the OEIS as sequence A166623.

Given a positive integer \$n>0\$, determine if it is a Munchausen number in any base \$b\geq2\$.

Rules

  • Default I/O rules apply, so:
    • Full program or functions are acceptable.
    • Input can be from STDIN, as a function argument, and output can be to STDOUT, as a function return value, etc.
  • Default loopholes apply.
  • The output must be one of two distinct, consistent results. So TRUE is fine for truthy and FALSE is fine for falsy, but you can reverse that or return None for truthy and 1 for falsy or whatever. Please specify the selected results in your answer.
  • Your answer has to work at least theoretically for any positive integer.
  • Munchausen numbers use the convention \$0^0=1\$, so \$2\$ is a base-2 Munchausen number as \$1^1+0^0=2\$. Your code must follow this convention.
  • Explanations are strongly encouraged, even though submissions will most likely use the brute-force search method.
  • Using esoteric languages earns you brownie points since Munchausen was apparently a strange person.

Test Cases

Truthy
1 (all bases)
2 (base 2)
5 (base 3)
28 (base 9 and base 25)
29 (base 4)
55 (base 4)
3435 (base 10)
923362 (base 9)
260 (base 128)
257 (base 64 and base 253)

Falsy
3
4
591912
3163
17

This is , so the shortest answer in each language (in bytes) wins!

\$\endgroup\$
  • \$\begingroup\$ Can we assume the maximum base we need to calculate is 35/36? \$\endgroup\$ – Benjamin Urquhart May 8 at 16:52
  • 7
    \$\begingroup\$ @BenjaminUrquhart no you may not; determine if it's a Munchausen number in any base b≥2. \$\endgroup\$ – Giuseppe May 8 at 17:00
  • \$\begingroup\$ How about just guessing "no." There are a countably infinite number of integers and a provably finite number of Munchausens, so probability of choosing a Munchausen number is (n)/(Infinity) = 0 . //ducks and runs \$\endgroup\$ – Carl Witthoft May 10 at 18:52
  • \$\begingroup\$ @CarlWitthoft I laughed at the suggestion, but of course that would be an invalid submission :-) \$\endgroup\$ – Giuseppe May 10 at 19:01

19 Answers 19

13
\$\begingroup\$

05AB1E, 7 bytes

LвDmOQZ

Try it online!

The larger test cases will time out on TIO.

Explanation

L         # push range [1 ... input]
 в        # convert input to a digit list in each of these bases
  Dm      # raise each digit to the power of itself
    O     # sum each
     Q    # check each for equality with input
      Z   # max
\$\endgroup\$
  • 3
    \$\begingroup\$ How is this filtering base-1 from the results? \$\endgroup\$ – Shaggy May 8 at 20:32
  • 1
    \$\begingroup\$ @Shaggy: With this base conversion, all numbers are 1 in base-1. The only number that will return true for 1^1 is 1. \$\endgroup\$ – Emigna May 9 at 6:14
5
\$\begingroup\$

Jelly, 8 bytes

bŻ*`§ċ⁸Ị

Yields 0 for Munchausen and 1 otherwise.

Try it online!
Or see the first five hundred positive integers split up as [[Munchausen], [non-Munchausen]].

How?

bŻ*`§ċ⁸Ị - Link: integer, n
 Ż       - zero-range -> [0,1,2,3,4,...,n]
b        - (n) to base (vectorises)
   `     - with left as both arguments:
  *      -   exponentiation (vectorises)
    §    - sums
     ċ   - count occurrences of:
      ⁸  -   n
       Ị - is insignificant (abs(x) <= 1)

Alternative for 1 for Munchausen and 0 otherwise:

bŻ*`§ċ>1
\$\endgroup\$
  • \$\begingroup\$ Um... why do I think that your previous version was valid and this one is invalid? \$\endgroup\$ – Erik the Outgolfer May 8 at 17:57
  • \$\begingroup\$ I think my previous version was invalid since it did not say that 1 was Munchausen. \$\endgroup\$ – Jonathan Allan May 8 at 17:59
5
\$\begingroup\$

J, 33 28 27 bytes

e.1#.i.@>:^~@(#.inv ::1)"0]

Try it online!

  • e. is the input an element of...
  • 1#. the sum of each row of...
  • i.@>: ... ] 0..input and the input itself, passed as left and right args to...
  • ^~@(#.inv)"0 convert the right arg (input) to each base in the left arg and raise each result elementwise to itself ^~@.
  • ::1 finally this is needed because you can't convert uniquely to base 1, so it errors. in this case, we simply return 1, which won't match for any number except 1, which is what we want
\$\endgroup\$
4
\$\begingroup\$

R, 72 69 bytes

-1 byte thanks to digEmAll

function(x){for(b in 1+1:x)F=F|!sum((a=x%/%b^(0:log(x,b))%%b)^a)-x;F}

Try it online!

Outputs TRUE for Munchausen numbers and FALSE otherwise.

x%/%b^(0:log(x,b))%%b) converts x to base b, and the for loop does the rest of the work (reassigning F, which is FALSE by default).

We need to allow the base b to go all the way to x+1 instead of x to handle the case x=1.

\$\endgroup\$
  • \$\begingroup\$ 71 using a for loop \$\endgroup\$ – digEmAll May 11 at 13:22
  • \$\begingroup\$ @digEmAll Thanks! I shaved off another 2 bytes by using booleans instead of integers. \$\endgroup\$ – Robin Ryder May 11 at 20:20
  • \$\begingroup\$ I was trying to understand what you changed to save 2 bytes from mine besides changing + with | and removing !, then I realized I wrote 71 but my code was actually 70 :D \$\endgroup\$ – digEmAll May 12 at 6:16
  • \$\begingroup\$ Great idea using | BTW ! \$\endgroup\$ – digEmAll May 12 at 6:19
  • \$\begingroup\$ @digEmAll Oh yes, I didn't even think to check your byte count! :) \$\endgroup\$ – Robin Ryder May 12 at 8:37
3
\$\begingroup\$

Japt, 13 bytes

õ@ìXÄ x_pZ
øN

Saved one byte thanks to @Shaggy

Try it

\$\endgroup\$
  • \$\begingroup\$ @Shaggy Fixed at the cost of a byte \$\endgroup\$ – Embodiment of Ignorance May 8 at 20:26
  • \$\begingroup\$ You can get that byte back by replacing ÃÃøU with <newline>øN. \$\endgroup\$ – Shaggy May 8 at 20:34
  • \$\begingroup\$ @Shaggy Nice trick with N, I never used it before! \$\endgroup\$ – Embodiment of Ignorance May 8 at 20:38
3
\$\begingroup\$

Perl 6, 51 bytes

{?grep {$_==sum [Z**] .polymod($^a xx*)xx 2},^$_+2}

Try it online!

Explanation:

{                                                 } # Anonymous code block
 ?grep {                                  }         # Do any
                                           ,^$_+2   # Of the bases from 2 to n+1
            sum                              # Have the sum of
                      .polymod($^a xx*)      # The digits of n in that base
                [Z**]                  xx 2  # Raised to the power of themselves
        $_==                                 # Equal to the original number?
\$\endgroup\$
3
\$\begingroup\$

Ruby, 50 bytes

TIO timed out on 591912. Somehow edges out Perl by 1 byte... (at time of writing)

->n{(2..n+1).any?{|b|n.digits(b).sum{|d|d**d}==n}}

Try it online!

\$\endgroup\$
3
\$\begingroup\$

JavaScript (ES7), 60 bytes

Returns a Boolean value.

n=>(F=b=>(g=n=>n&&g(n/b|0)+(n%=b)**n)(n)==n||b<n&&F(b+1))(2)

Try it online!

Commented

n =>                   // n = input
  ( F = b =>           // F = recursive function taking a base b
    ( g = n =>         //   g = recursive function taking an integer n
      n &&             //     if n is not equal to 0:
        g(n / b | 0) + //       do a recursive call with floor(n / b)
        (n %= b) ** n  //       and add (n mod b) ** (n mod b)
    )(n)               //   initial call to g with the original value of n
    == n ||            //   return true if the result is equal to n
    b < n &&           //   otherwise, if b is less than n:
      F(b + 1)         //     try with b + 1
  )(2)                 // initial call to F with b = 2
\$\endgroup\$
3
\$\begingroup\$

APL (dzaima/APL), 23 13 bytes

⊢∊⊂+.*⍨⍤⊤⍨¨2…

Try it online!

Thanks to Adám, ngn and dzaima, we managed to shave 10 bytes off this answer by using dzaima/APL.

Prefix tacit function. Munchausen numbers return 1, else 0.

How

⊢∊⊂+.*⍨⍤⊤⍨¨2… ⍝ Prefix tacit function, argument will be called ⍵

             2… ⍝ Generate the integer sequence [2..⍵]
          ⊤⍨¨  ⍝ Convert ⍵ to each base in the vector
     +.*⍨⍤      ⍝ Raise each digit of each element in the vector to itself, then sum
⊢∊⊂            ⍝ Check if ⍵ is in the resulting vector.
\$\endgroup\$
2
\$\begingroup\$

Wolfram Language (Mathematica), 65 bytes

#<2||!Tr[Check[#^#,1]&/@#~IntegerDigits~i]~Table~{i,2,#}~FreeQ~#&

Try it online!

-4 bytes from @attinat

\$\endgroup\$
2
\$\begingroup\$

Charcoal, 17 bytes

Nθ¬Φθ⁼θΣE↨θ⁺²ιXλλ

Try it online! Link is to verbose version of code. My 16-byte attempt didn't work but that might be a bug in Charcoal, so watch this space. Outputs - unless the number is a Munchausen number. Explanation:

Nθ                  Input `n` as a number
   Φθ               Try bases `2` .. `n+1`
       Σ            Sum of
         ↨θ         `n` converted to base
           ⁺²ι      Next trial base
        E           Each digit
              Xλλ   Raised to its own power
     ⁼              Equals
      θ             `n`
  ¬                 Logical Not
\$\endgroup\$
2
\$\begingroup\$

C# (Visual C# Interactive Compiler), 99 bytes

n=>Enumerable.Range(2,n).Any(x=>{int g=0,t=n;for(;t>0;t/=x)g+=(int)Math.Pow(t%x,t%x);return g==n;})

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Haskell, 61 bytes

_#0=0
b#n|m<-mod n b=m^m+b#div n b
f n=elem n$1:map(#n)[2..n]

Returns True for Munchausen and False otherwise.

Try it online!

\$\endgroup\$
2
\$\begingroup\$

C (gcc) -lm, 79 75 bytes

f(n,b,i,g,c){for(g=b=1;b+++~n;g*=!!c)for(c=i=n;c-=pow(i%b,i%b),i/=b;);n=g;}

Try it online!

Returns 0 for Munchausen numbers, and 1 otherwise.


also 75 bytes

a,b;f(n){for(a=b=1;b+++~n;a*=g(n)!=n);n=a;}g(n){n=n?g(n/b)+pow(n%b,n%b):0;}

Try it online!

\$\endgroup\$
2
\$\begingroup\$

Python 2, 83 81 bytes

def f(n,b=2):
 s=0;m=n
 while m:k=m%b;s+=k**k;m/=b
 return s==n or b<n>0<f(n,b+1)

Try it online!

Returns 1 for truthy and 0 for falsey. Because of the recursion, can't practically deal with 591912, but it works in the abstract.

\$\endgroup\$
1
\$\begingroup\$

Perl 6, 66 65 bytes

{$^a==1||[+] map {$a==[+] map {$_**$_},$a.polymod($_ xx*)},2..$a}

Try it online!

\$\endgroup\$
1
\$\begingroup\$

JavaScript (ES6), 88 bytes

f=n=>{for(b=2;n-b++;){for(c=0,r=n;r;r=(r-a)/b)c+=(a=(r%b))**a;if(n==c)return 1}return 0}
\$\endgroup\$
1
\$\begingroup\$

Icon, 109 bytes

procedure m(n)
every k:=2to n&{i:=n;s:=0
while{a:=i%k;a<:=1;s+:=a^a;0<(i/:=k)}
n=s&return 1}
return n=1|0
end

Try it online!

Times out for 591912. Icon treats 0^0 as an overflow and that's why I need an additional check for zero.

\$\endgroup\$
1
\$\begingroup\$

Stax, 15 bytes

╡!←!║╝âñoêû►╦ä▓

Run and debug it

Takes very long for the larger test cases.

Explanation:

{^xs|E{c|*m|+x=m|a Full program, unpacked
                   Implicitly input x
{              m   Map over bases [1 .. x]
 ^                   Increment base (effectively mapping over [2 .. x+1])
  xs                 Tuck x below base
    |E               Get digits of x in base
      {   m          Map over digits:
       c|*             copy and power
           |+        Sum
             x=      sum = x?
                |a Check if any element in array is true
                   Implicit output
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.