Perfect digit-to-digit invariant

☆ Save On Wikipedia ↗

In number theory, a perfect digit-to-digit invariant (PDDI; also known as a Munchausen number[1]) is a natural number in a given number base b {\displaystyle b} {\displaystyle b} that is equal to the sum of its digits each raised to the power of itself. An example in base 10 is 3435, because 3435 = 3 3 + 4 4 + 3 3 + 5 5 {\displaystyle 3435=3^{3}+4^{4}+3^{3}+5^{5}} {\displaystyle 3435=3^{3}+4^{4}+3^{3}+5^{5}}. The term "Munchausen number" was coined by Dutch mathematician and software engineer Daan van Berkel in 2009,[2] as this evokes the story of Baron Munchausen raising himself up by his own ponytail because each digit is raised to the power of itself.[3][4]

Definition

Let n {\displaystyle n} {\displaystyle n} be a natural number which can be written in base b {\displaystyle b} {\displaystyle b} as the k-digit number d k − 1 d k − 2 . . . d 1 d 0 {\displaystyle d_{k-1}d_{k-2}...d_{1}d_{0}} {\displaystyle d_{k-1}d_{k-2}...d_{1}d_{0}} where each digit d i {\displaystyle d_{i}} {\displaystyle d_{i}} is between 0 {\displaystyle 0} {\displaystyle 0} and b − 1 {\displaystyle b-1} {\displaystyle b-1} inclusive, and n = ∑ i = 0 k − 1 d i b i {\displaystyle n=\sum _{i=0}^{k-1}d_{i}b^{i}} {\displaystyle n=\sum _{i=0}^{k-1}d_{i}b^{i}}. We define the function F b : N → N {\displaystyle F_{b}:\mathbb {N} \rightarrow \mathbb {N} } {\displaystyle F_{b}:\mathbb {N} \rightarrow \mathbb {N} } as F b ( n ) = ∑ i = 0 k − 1 d i d i {\displaystyle F_{b}(n)=\sum _{i=0}^{k-1}{d_{i}}^{d_{i}}} {\displaystyle F_{b}(n)=\sum _{i=0}^{k-1}{d_{i}}^{d_{i}}}. (As 00 is usually undefined, there are typically two conventions used, one where it is taken to be equal to one, and another where it is taken to be equal to zero.[5][6]) A natural number n {\displaystyle n} {\displaystyle n} is defined to be a perfect digit-to-digit invariant in base b if F b ( n ) = n {\displaystyle F_{b}(n)=n} {\displaystyle F_{b}(n)=n}. For example, the number 3435 is a perfect digit-to-digit invariant in base 10 because 3 3 + 4 4 + 3 3 + 5 5 = 27 + 256 + 27 + 3125 = 3435 {\displaystyle 3^{3}+4^{4}+3^{3}+5^{5}=27+256+27+3125=3435} {\displaystyle 3^{3}+4^{4}+3^{3}+5^{5}=27+256+27+3125=3435}.

F b ( 1 ) = 1 {\displaystyle F_{b}(1)=1} {\displaystyle F_{b}(1)=1} for all b {\displaystyle b} {\displaystyle b}, and thus 1 is a trivial perfect digit-to-digit invariant in all bases, and all other perfect digit-to-digit invariants are nontrivial. For the second convention where 0 0 = 0 {\displaystyle 0^{0}=0} {\displaystyle 0^{0}=0}, both 0 {\displaystyle 0} {\displaystyle 0} and 1 {\displaystyle 1} {\displaystyle 1} are trivial perfect digit-to-digit invariants.

A natural number n {\displaystyle n} {\displaystyle n} is a sociable digit-to-digit invariant if it is a periodic point for F b {\displaystyle F_{b}} {\displaystyle F_{b}}, where F b k ( n ) = n {\displaystyle F_{b}^{k}(n)=n} {\displaystyle F_{b}^{k}(n)=n} for a positive integer k {\displaystyle k} {\displaystyle k}, and forms a cycle of period k {\displaystyle k} {\displaystyle k}. A perfect digit-to-digit invariant is a sociable digit-to-digit invariant with k = 1 {\displaystyle k=1} {\displaystyle k=1}. An amicable digit-to-digit invariant is a sociable digit-to-digit invariant with k = 2 {\displaystyle k=2} {\displaystyle k=2}.

All natural numbers n {\displaystyle n} {\displaystyle n} are preperiodic points for F b {\displaystyle F_{b}} {\displaystyle F_{b}}, regardless of the base. This is because all natural numbers of base b {\displaystyle b} {\displaystyle b} with k {\displaystyle k} {\displaystyle k} digits satisfy b k − 1 ≤ n ≤ ( k ) ( b − 1 ) b − 1 {\displaystyle b^{k-1}\leq n\leq (k){(b-1)}^{b-1}} {\displaystyle b^{k-1}\leq n\leq (k){(b-1)}^{b-1}}. However, when k ≥ b + 1 {\displaystyle k\geq b+1} {\displaystyle k\geq b+1}, then b k − 1 > ( k ) ( b − 1 ) b − 1 {\displaystyle b^{k-1}>(k){(b-1)}^{b-1}} {\displaystyle b^{k-1}>(k){(b-1)}^{b-1}}, so any n {\displaystyle n} {\displaystyle n} will satisfy n > F b ( n ) {\displaystyle n>F_{b}(n)} {\displaystyle n>F_{b}(n)} until n < b b + 1 {\displaystyle n<b^{b+1}} {\displaystyle n<b^{b+1}}. There are a finite number of natural numbers less than b b + 1 {\displaystyle b^{b+1}} {\displaystyle b^{b+1}}, so the number is guaranteed to reach a periodic point or a fixed point less than b b + 1 {\displaystyle b^{b+1}} {\displaystyle b^{b+1}}, making it a preperiodic point. This means also that there are a finite number of perfect digit-to-digit invariant and cycles for any given base b {\displaystyle b} {\displaystyle b}.

The number of iterations i {\displaystyle i} {\displaystyle i} needed for F b i ( n ) {\displaystyle F_{b}^{i}(n)} {\displaystyle F_{b}^{i}(n)} to reach a fixed point is the b {\displaystyle b} {\displaystyle b}-factorion function's persistence of n {\displaystyle n} {\displaystyle n}, and undefined if it never reaches a fixed point.

Perfect digit-to-digit invariants and cycles of Fb for specific b

All numbers are represented in base b {\displaystyle b} {\displaystyle b}.

Convention 00 = 1

Base Nontrivial perfect digit-to-digit invariants ( n ≠ 1 {\displaystyle n\neq 1} {\displaystyle n\neq 1}) Cycles
2 10 ∅ {\displaystyle \varnothing } {\displaystyle \varnothing }
3 12, 22 2 → 11 → 2
4 131, 313 2 → 10 → 2
5 ∅ {\displaystyle \varnothing } {\displaystyle \varnothing }

2 → 4 → 2011 → 12 → 10 → 2

104 → 2013 → 113 → 104

6 22352, 23452

4 → 1104 → 1111 → 4

23445 → 24552 → 50054 → 50044 → 24503 → 23445

7 13454 12066 → 536031 → 265204 → 265623 → 551155 → 51310 → 12125 → 12066
8 ∅ {\displaystyle \varnothing } {\displaystyle \varnothing } 405 → 6466 → 421700 → 3110776 → 6354114 → 142222 → 421 → 405
9 31, 156262, 1656547
10 3435
11 18453278, 18453487
12 3A67A54832
13 33661, 2AA834668A, 4CA92A233518, 4CA92A233538
14 23, 26036, 45A0A04513CC, A992B5D96720D
15 4B1648420DCD0, 5A99E538339A43, 5ACBC41C19E333, 5ACBC41C19E400, 5D0B197C25E056
16 C4EF722B782C26F, C76712FFC311E6E
17 33
18
19
20 6534
21
22
23
24
25 13, 513

Convention 00 = 0

Base Nontrivial perfect digit-to-digit invariants ( n ≠ 0 {\displaystyle n\neq 0} {\displaystyle n\neq 0}, n ≠ 1 {\displaystyle n\neq 1} {\displaystyle n\neq 1})[1] Cycles
2 ∅ {\displaystyle \varnothing } {\displaystyle \varnothing } ∅ {\displaystyle \varnothing } {\displaystyle \varnothing }
3 12, 22 2 → 11 → 2
4 130, 131, 313 ∅ {\displaystyle \varnothing } {\displaystyle \varnothing }
5 103, 2024

2 → 4 → 2011 → 11 → 2

9 → 2012 → 9

6 22352, 23452

5 → 22245 → 23413 → 1243 → 1200 → 5

53 → 22332 → 150 → 22250 → 22305 → 22344 → 2311 → 53

7 13454
8 400, 401
9 30, 31, 156262, 1647063, 1656547, 34664084
10 3435, 438579088
11 ∅ {\displaystyle \varnothing } {\displaystyle \varnothing } ∅ {\displaystyle \varnothing } {\displaystyle \varnothing }
12 3A67A54832

Programming examples

The following program in Python determines whether an integer number is a Munchausen Number / Perfect Digit to Digit Invariant or not, following the convention 0 0 = 1 {\displaystyle 0^{0}=1} {\displaystyle 0^{0}=1}.

num = int(input("Enter number:"))
temp = num
s = 0.0
while num > 0:
     digit = num % 10
     num //= 10
     s+= pow(digit, digit)
     
if s == temp:
    print("Munchausen Number")
else:
    print("Not Munchausen Number")

The examples below implement the perfect digit-to-digit invariant function described in the definition above to search for perfect digit-to-digit invariants and cycles in Python for the two conventions.

Convention 00 = 1

def pddif(x: int, b: int) -> int:
    total = 0
    while x > 0:
        total = total + pow(x % b, x % b)
        x = x // b
    return total

def pddif_cycle(x: int, b: int) -> list[int]:
    seen = []
    while x not in seen:
        seen.append(x)
        x = pddif(x, b)
    cycle = []
    while x not in cycle:
        cycle.append(x)
        x = pddif(x, b)
    return cycle

Convention 00 = 0

def pddif(x: int, b: int) -> int:
    total = 0
    while x > 0:
        if x % b > 0:
            total = total + pow(x % b, x % b)
        x = x // b
    return total

def pddif_cycle(x: int, b: int) -> list[int]:
    seen = []
    while x not in seen:
        seen.append(x)
        x = pddif(x, b)
    cycle = []
    while x not in cycle:
        cycle.append(x)
        x = pddif(x, b)
    return cycle

See also

References

  1. van Berkel, Daan (2009). "On a curious property of 3435". arXiv:0911.3038 [math.HO].
  2. Olry, Regis and Duane E. Haines. "Historical and Literary Roots of Münchhausen Syndromes", from Literature, Neurology, and Neuroscience: Neurological and Psychiatric Disorders, Stanley Finger, Francois Boller, Anne Stiles, eds. Elsevier, 2013. p.136.
  3. Daan van Berkel, On a curious property of 3435.
  4. Parker, Matt (2014). Things to Make and Do in the Fourth Dimension. Penguin UK. p. 28. ISBN 9781846147654. Retrieved 2 May 2015.
  5. Narcisstic Number, Harvey Heinz
  6. Wells, David (1997). The Penguin Dictionary of Curious and Interesting Numbers. London: Penguin. p. 185. ISBN 0-14-026149-4.