perfect digital invariant

{{Short description|Number that is the sum of its own digits, each raised to a given power}}

In number theory, a perfect digital invariant (PDI) is a number in a given number base (b) that is the sum of its own digits each raised to a given power (p).[http://www.cs.umd.edu/Honors/reports/NarcissisticNums/NarcissisticNums.html Perfect and PluPerfect Digital Invariants] {{webarchive|url=https://web.archive.org/web/20071010035540/http://www.cs.umd.edu/Honors/reports/NarcissisticNums/NarcissisticNums.html |date=2007-10-10 }} by Scott Moore[https://web.archive.org/web/20091027123639/http://www.geocities.com/~harveyh/narciss.htm PDIs] by Harvey Heinz

Definition

Let n be a natural number. The perfect digital invariant function (also known as a happy function, from happy numbers) for base b > 1 and power p > 0 F_{p, b} : \mathbb{N} \rightarrow \mathbb{N} is defined as:

:F_{p, b}(n) = \sum_{i=0}^{k - 1} d_i^p.

where k = \lfloor \log_{b}{n} \rfloor + 1 is the number of digits in the number in base b, and

:d_i = \frac{n \bmod{b^{i+1}} - n \bmod b^i}{b^i}

is the value of each digit of the number. A natural number n is a perfect digital invariant if it is a fixed point for F_{p, b}, which occurs if F_{p, b}(n) = n. 0 and 1 are trivial perfect digital invariants for all b and p, all other perfect digital invariants are nontrivial perfect digital invariants.

For example, the number 4150 in base b = 10 is a perfect digital invariant with p = 5, because 4150 = 4^5 + 1^5 + 5^5 + 0^5.

A natural number n is a sociable digital invariant if it is a periodic point for F_{p, b}, where F_{p,b}^k(n) = n for a positive integer k (here F_{p,b}^k is the kth iterate of F_{p,b}), and forms a cycle of period k. A perfect digital invariant is a sociable digital invariant with k = 1, and a amicable digital invariant is a sociable digital invariant with k = 2.

All natural numbers n are preperiodic points for F_{p, b}, regardless of the base. This is because if k \geq p + 2, n \geq b^{k-1} > b^p k, so any n will satisfy n > F_{b,p}(n) until n < b^{p+1}. There are a finite number of natural numbers less than b^{p+1}, so the number is guaranteed to reach a periodic point or a fixed point less than b^{p+1}, making it a preperiodic point.

Numbers in base b > p lead to fixed or periodic points of numbers n \leq (p - 2)^p + p (b - 1)^p.

{{Math proof|title=Proof|drop=hidden|proof=

If b > p, then the n < b^{p+1} bound can be reduced.

Let r be the number for which the sum of squares of digits is largest among the numbers less than b^p.

:r = b^p - 1 = \sum_{t=0}^p (b - 1)b^t

:F_{p, b}(r) = (p + 1)(b - 1)^p < (p + 1) b^p \leq b^{p + 1} because b \geq (p + 1)

Let s be the number for which the sum of squares of digits is largest among the numbers less than (p + 1)(b - 1)^p.

:s = (p + 1)b^p - 1 = p b^p + \sum_{t=0}^{p - 1} (b - 1)b^t

:F_{p, b}(s) = p^p + p (b - 1)^p < p b^p because b \geq p

Let t be the number for which the sum of squares of digits is largest among the numbers less than p b^p.

:t = (p - 1) b^p + \sum_{t=0}^{p - 1} (b - 1)b^t

:F_{p, b}(t) = (p - 1)^p + p (b - 1)^p

Let u be the number for which the sum of squares of digits is largest among the numbers less than F_{p, b}(t) + 1.

:u = (p - 2) b^p + \sum_{t=0}^{p - 1} (b - 1)b^t

:F_{p, b}(u) = (p - 2)^p + p (b - 1)^p < (p - 1)^p + p (b - 1)^p = n_{\ell+1}

u \leq F_{p, b}(u) < F_{p, b}(t). Thus, numbers in base b > p lead to cycles or fixed points of numbers n \leq F_{p, b}(u) = (p - 1)^p + p (b - 1)^p.

}}

The number of iterations i needed for F_{p,b}^{i}(n) to reach a fixed point is the perfect digital invariant function's persistence of n, and undefined if it never reaches a fixed point.

F_{1, b} is the digit sum. The only perfect digital invariants are the single-digit numbers in base b, and there are no periodic points with prime period greater than 1.

F_{p, 2} reduces to F_{1, 2}, as for any power p, 0^p = 0 and 1^p = 1.

For every natural number k > 1, if p < b, (b - 1) \equiv 0 \bmod k and (p - 1) \equiv 0 \bmod \phi(k), then for every natural number n, if n \equiv m \bmod k, then F_{p, b}(n) \equiv m \bmod k, where \phi(k) is Euler's totient function.

{{Math proof|title=Proof|drop=hidden|proof=

Let

:n = \sum_{i = 0}^j d_i b^i

be a natural number with j digits, where 0 \leq d_i < b, and (b - 1) \equiv 0 \bmod k, where k is a natural number greater than 1.

According to the divisibility rules of base b, if b - 1 \equiv 0 \bmod k, then if n \equiv m \bmod k, then the digit sum

: F_{1, b}(n) = \sum_{i = 0}^j d_i \equiv m \bmod k

If a digit d_i \equiv m \bmod k, then d_i^p \equiv m^p \bmod k. According to Euler's theorem, if (p - 1) \equiv 0 \bmod \phi(k), m^p \bmod k = m \bmod k. Thus, if the digit sum F_{1, b}(n) \equiv m \bmod k, then F_{p, b}(n) \equiv m \bmod k.

Therefore, for any natural number k, if p < b, (b - 1) \equiv 0 \bmod k and (p - 1) \equiv 0 \bmod \phi(k), then for every natural number n, if n \equiv m \bmod k, then F_{p, b}(n) \equiv m \bmod k.

}}

No upper bound can be determined for the size of perfect digital invariants in a given base and arbitrary power, and it is not currently known whether or not the number of perfect digital invariants for an arbitrary base is finite or infinite.

''F''<sub>2,''b''</sub>

By definition, any three-digit perfect digital invariant n = d_2 d_1 d_0 for F_{2, b} with natural number digits 0 \leq d_0 < b, 0 \leq d_1 < b, 0 \leq d_2 < b has to satisfy the cubic Diophantine equation d_0^2 + d_1^2 + d_2^2 = d_2 b^2 + d_1 b + d_0. d_2 has to be equal to 0 or 1 for any b > 2, because the maximum value n can take is n = (2 - 1)^2 + 2 (b - 1)^2 = 1 + 2 (b - 1)^2 < 2 b^2. As a result, there are actually two related quadratic Diophantine equations to solve:

: d_0^2 + d_1^2 = d_1 b + d_0 when d_2 = 0, and

: d_0^2 + d_1^2 + 1 = b^2 + d_1 b + d_0 when d_2 = 1.

The two-digit natural number n = d_1 d_0 is a perfect digital invariant in base

: b = d_1 + \frac{d_0 (d_0 - 1)}{d_1}.

This can be proven by taking the first case, where d_2 = 0, and solving for b. This means that for some values of d_0 and d_1, n is not a perfect digital invariant in any base, as d_1 is not a divisor of d_0 (d_0 - 1). Moreover, d_0 > 1, because if d_0 = 0 or d_0 = 1, then b = d_1, which contradicts the earlier statement that 0 \leq d_1 < b.

There are no three-digit perfect digital invariants for F_{2, b}, which can be proven by taking the second case, where d_2 = 1, and letting d_0 = b - a_0 and d_1 = b - a_1. Then the Diophantine equation for the three-digit perfect digital invariant becomes

: (b - a_0)^2 + (b - a_1)^2 + 1 = b^2 + (b - a_1) b + (b - a_0)

: b^2 - 2 a_0 b + a_0^2 + b^2 - 2 a_1 b + a_1^2 + 1 = b^2 + (b - a_1) b + (b - a_0)

: 2 b^2 - 2 (a_0 + a_1) b + a_0^2 + a_1^2 + 1 = b^2 + (b - a_1) b + (b - a_0)

: b^2 + (b - 2 (a_0 + a_1)) b + a_0^2 + a_1^2 + 1 = b^2 + (b - a_1) b + (b - a_0)

2 (a_0 + a_1) > a_1 for all values of 0 < a_1 \leq b. Thus, there are no solutions to the Diophantine equation, and there are no three-digit perfect digital invariants for F_{2, b}.

''F''<sub>3,''b''</sub>

{{Quote frame|

There are just four numbers, after unity, which are the sums of the cubes of their digits:

:153=1^3+5^3+3^3

:370=3^3+7^3+0^3

: 371=3^3+7^3+1^3

:407=4^3+0^3+7^3.

These are odd facts, very suitable for puzzle columns and likely to amuse amateurs, but there is nothing in them which appeals to the mathematician. {{OEIS|id=A046197}}|G. H. Hardy|A Mathematician's Apology}}

By definition, any four-digit perfect digital invariant n for F_{3, b} with natural number digits 0 \leq d_0 < b, 0 \leq d_1 < b, 0 \leq d_2 < b, 0 \leq d_3 < b has to satisfy the quartic Diophantine equation d_0^3 + d_1^3 + d_2^3 + d_3^3 = d_3 b^3 + d_2 b^2 + d_1 b + d_0. d_3 has to be equal to 0, 1, 2 for any b > 3, because the maximum value n can take is n = (3 - 2)^3 + 3 (b - 1)^3 = 1 + 3 (b - 1)^3 < 3 b^3. As a result, there are actually three related cubic Diophantine equations to solve

: d_0^3 + d_1^3 + d_2^3 = d_2 b^2 + d_1 b + d_0 when d_3 = 0

: d_0^3 + d_1^3 + d_2^3 + 1 = b^3 + d_2 b^2 + d_1 b + d_0 when d_3 = 1

: d_0^3 + d_1^3 + d_2^3 + 8 = 2 b^3 + d_2 b^2 + d_1 b + d_0 when d_3 = 2

We take the first case, where d_3 = 0.

= ''b'' = 3''k'' + 1 =

Let k be a positive integer and the number base b = 3 k + 1. Then:

  • n_1 = kb^2 + (2k + 1)b is a perfect digital invariant for F_{3, b} for all k.

{{Math proof|title=Proof|drop=hidden|proof=

Let the digits of n_1 = d_2 b^2 + d_1 b + d_0 be d_2 = k, d_1 = 2k + 1, and d_0 = 0. Then

:

\begin{align}

F_{3, b}(n_1) & = d_0^3 + d_1^3 + d_2^3 \\

& = k^3 + (2k + 1)^3 + 0^3 \\

& = (k^2 - k(2k + 1) + (2k + 1)^2)(k + (2k + 1)) \\

& = (k^2 - 2k^2 - k + 4k^2 + 4k + 1)(3k + 1) \\

& = (3k^2 + 3k + 1)(3k + 1) \\

& = (3k^2 + 4k + 1)(3k + 1) - k(3k + 1) \\

& = (k + 1)(3k + 1)(3k + 1) - k(3k + 1) \\

& = k(3k + 1)(3k + 1) + (3k + 1)(3k + 1) - k(3k + 1) \\

& = k(3k + 1)^2 + (2k + 1)(3k + 1) + 0 \\

& = d_2 b^2 + d_1 b + d_0 \\

& = n_1

\end{align}

Thus n_1 is a perfect digital invariant for F_{3, b} for all k.

}}

  • n_2 = kb^2 + (2k + 1)b + 1 is a perfect digital invariant for F_{3, b} for all k.

{{Math proof|title=Proof|drop=hidden|proof=

Let the digits of n_2 = d_2 b^2 + d_1 b + d_0 be d_2 = k, d_1 = 2k + 1, and d_0 = 1. Then

:

\begin{align}

F_{3, b}(n_2) & = d_0^3 + d_1^3 + d_2^3 \\

& = k^3 + (2k + 1)^3 + 1^3 \\

& = (k^2 - k(2k + 1) + (2k + 1)^2)(k + (2k + 1)) + 1 \\

& = (k^2 - 2k^2 - k + 4k^2 + 4k + 1)(3k + 1) + 1 \\

& = (3k^2 + 3k + 1)(3k + 1) + 1 \\

& = (3k^2 + 4k + 1)(3k + 1) - k(3k + 1) + 1 \\

& = (k + 1)(3k + 1)(3k + 1) - k(3k + 1) + 1 \\

& = k(3k + 1)(3k + 1) + (3k + 1)(3k + 1) - k(3k + 1) + 1 \\

& = k(3k + 1)^2 + (2k + 1)(3k + 1) + 1 \\

& = d_2 b^2 + d_1 b + d_0 \\

& = n_2

\end{align}

Thus n_2 is a perfect digital invariant for F_{3, b} for all k.

}}

  • n_3 = (k + 1)b^2 + (2k + 1) is a perfect digital invariant for F_{3, b} for all k.

{{Math proof|title=Proof|drop=hidden|proof=

Let the digits of n_3 = d_2 b^2 + d_1 b + d_0 be d_2 = k + 1, d_1 = 0, and d_0 = 2k + 1. Then

:

\begin{align}

F_{3, b}(n_3) & = d_0^3 + d_1^3 + d_2^3 \\

& = (k + 1)^3 + 0^3 + (2k + 1)^3 \\

& = ((k + 1)^2 - (k + 1)(2k + 1) + (2k + 1)^2)((k + 1) + (2k + 1)) \\

& = ((k + 1)^2 + k(2k + 1)(3k + 2) \\

& = (k^2 + 2k + 1 + 2k^2 + k)(3k + 2) \\

& = (3k^2 + 3k + 1)(3k + 2) \\

& = (3k^2 + 3k)(3k + 2) + (3k + 2) \\

& = 3k(k + 1)(3k + 2) + (3k + 2) \\

& = (k + 1)((3k + 1)^2 - 1) + (3k + 2) \\

& = (k + 1)(3k + 1)^2 - (k + 1) + (3k + 2) \\

& = (k + 1)(3k + 1)^2 + 0(3k + 1) + (2k + 1) \\

& = d_2 b^2 + d_1 b + d_0 \\

& = n_3

\end{align}

Thus n_3 is a perfect digital invariant for F_{3, b} for all k.

}}

class="wikitable"

|+ Perfect digital invariants

! k

! b

! n_1

! n_2

! n_3

--

| 1

4130131203
--

| 2

7250251305
--

| 3

10370371407
--

| 4

13490491509
--

| 5

165B05B160B
--

| 6

196D06D170D
--

| 7

227F07F180F
--

| 8

258H08H190H
--

| 9

289J09J1A0J

= ''b'' = 3''k'' + 2 =

Let k be a positive integer and the number base b = 3 k + 2. Then:

  • n_1 = kb^2 + (2k + 1) is a perfect digital invariant for F_{3, b} for all k.

{{Math proof|title=Proof|drop=hidden|proof=

Let the digits of n_1 = d_2 b^2 + d_1 b + d_0 be d_2 = k, d_1 = 2k + 1, and d_0 = 0. Then

: F_{3, b}(n_1) = d_0^3 + d_1^3 + d_2^3

:: = k^3 + 0^3 + (2k + 1)^3

:: = (k^2 - k(2k + 1) + (2k + 1)^2)(k + (2k + 1))

:: = (k^2 - 2k^2 - k + 4k^2 + 4k + 1)(3k + 1)

:: = (3k^2 + 3k + 1)(3k + 1)

:: = (3k^2 + 3k + 1)(3k + 2) - (3k^2 + 3k + 1)

:: = (3k^2 + 3k + 1)(3k + 2) - (3k^2 + 2k + k + 1)

:: = (3k^2 + 3k + 1)(3k + 2) - k(3k + 2) - (k + 1)

:: = (3k^2 + 2k + 1)(3k + 2) - (k + 1)

:: = (3k^2 + 2k)(3k + 2) + (3k + 2) - (k + 1)

:: = k(3k + 2)^2 + (2k + 1)

:: = d_2 b^2 + d_1 b + d_0

:: = n_1

Thus n_1 is a perfect digital invariant for F_{3, b} for all k.

}}

class="wikitable"

|+ Perfect digital invariants

! k

! b

! n_1

--

| 1

5103
--

| 2

8205
--

| 3

11307
--

| 4

14409
--

| 5

1750B
--

| 6

2060D
--

| 7

2370F
--

| 8

2680H
--

| 9

2990J

= ''b'' = 6''k'' + 4 =

Let k be a positive integer and the number base b = 6 k + 4. Then:

  • n_4 = kb^2 + (3k + 2)b + (2k + 1) is a perfect digital invariant for F_{3, b} for all k.

{{Math proof|title=Proof|drop=hidden|proof=

Let the digits of n_4 = d_2 b^2 + d_1 b + d_0 be d_2 = k + 1, d_1 = 3k + 2, and d_0 = 2k + 1. Then

:F_{3, b}(n_3) = d_0^3 + d_1^3 + d_2^3

:: = (k)^3 + (3k + 2)^3 + (2k + 1)^3

:: = k^3 + ((3k + 2)^2 - (3k + 2)(2k + 1) + (2k + 1)^2)((3k + 2) + (2k + 1))

:: = k^3 + ((3k + 2)(k + 1) + (2k + 1)^2)(5k + 3)

:: = k^3 + (3k^2 + 5k + 2 + 4k^2 + 4k + 1)(5k + 3)

:: = k^3 + (7k^2 + 9k + 3)(5k + 3)

:: = k^3 + 5k(7k^2 + 9k + 3) + 3(7k^2 + 9k + 3)

:: = k^3 + 35k^3 + 45k^2 + 15k + 21k^2 + 27k + 9

:: = 36k^3 + 66k^2 + 42k + 9

:: = (6k + 4)(6k^2) + 42k^2 + 42k + 9

:: = (6k + 4)(6k^2) + (6k + 4)(4k^2) + 18k^2 + 26k + 9

:: = (6k + 4)(6k^2 + 4k) + 18k^2 + 26k + 9

:: = k(6k + 4)^2 + (6k + 4)(3k) + 14k + 9

:: = k(6k + 4)^2 + (3k + 2)(6k + 4) + 2k + 1

:: = d_2 b^2 + d_1 b + d_0

:: = n_4

Thus n_4 is a perfect digital invariant for F_{3, b} for all k.

}}

class="wikitable"

|+ Perfect digital invariants

! k

! b

! n_4

--

| 0

4021
--

| 1

10153
--

| 2

16285
--

| 3

223B7
--

| 4

284E9

''F''<sub>''p'',''b''</sub>

All numbers are represented in base b.

class="wikitable"

! p

! b

! Nontrivial perfect digital invariants

! Cycles

--

| rowspan="14" | 2

312, 222 → 11 → 2
--

| 4

\varnothing\varnothing
--

| 5

23, 334 → 31 → 20 → 4
--

| 6

\varnothing5 → 41 → 25 → 45 → 105 → 42 → 32 → 21 → 5
--

| 7

13, 34, 44, 632 → 4 → 22 → 11 → 2

16 → 52 → 41 → 23 → 16

--

| 8

24, 644 → 20 → 4

5 → 31 → 12 → 5

15 → 32 → 15

--

| 9

45, 5558 → 108 → 72 → 58

75 → 82 → 75

--

| 10

\varnothing4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4
--

| 11

56, 665 → 23 → 12 → 5

68 → 91 → 75 → 68

--

| 12

25, A55 → 21 → 5

8 → 54 → 35 → 2A → 88 → A8 → 118 → 56 → 51 → 22 → 8

18 → 55 → 42 → 18

68 → 84 → 68

--

| 13

14, 36, 67, 77, A6, C428 → 53 → 28

79 → A0 → 79

98 → B2 → 98

--

| 14

\varnothing1B → 8A → BA → 11B → 8B → D3 → CA → 136 → 34 → 1B

29 → 61 → 29

--

| 15

78, 882 → 4 → 11 → 2

8 → 44 → 22 → 8

15 → 1B → 82 → 48 → 55 → 35 → 24 → 15

2B → 85 → 5E → EB → 162 → 2B

4E → E2 → D5 → CE → 17A → A0 → 6A → 91 → 57 → 4E

9A → C1 → 9A

D6 → DA → 12E → D6

--

| 16

\varnothingD → A9 → B5 → 92 → 55 → 32 → D
--

| rowspan="14" | 3

31222 → 22 → 121 → 101 → 2
--

| 4

20, 21, 130, 131, 203, 223, 313, 332\varnothing
--

| 5

103, 43314 → 230 → 120 → 14
--

| 6

243, 514, 105513 → 44 → 332 → 142 → 201 → 13
--

| 7

12, 22, 250, 251, 305, 5052 → 11 → 2

13 → 40 → 121 → 13

23 → 50 → 236 → 506 → 665 → 1424 → 254 → 401 → 122 → 23

51 → 240 → 132 → 51

160 → 430 → 160

161 → 431 → 161

466 → 1306 → 466

516 → 666 → 1614 → 552 → 516

--

| 8

134, 205, 463, 660, 661662 → 670 → 1057 → 725 → 734 → 662
--

| 9

30, 31, 150, 151, 570, 571, 138838 → 658 → 1147 → 504 → 230 → 38

152 → 158 → 778 → 1571 → 572 → 578 → 1308 → 660 → 530 → 178 → 1151 → 152

638 → 1028 → 638

818 → 1358 → 818

--

| 10

153, 370, 371, 40755 → 250 → 133 → 55

136 → 244 → 136

160 → 217 → 352 → 160

919 → 1459 → 919

--

| 11

32, 105, 307, 708, 966, A06, A643 → 25 → 111 → 3

9 → 603 → 201 → 9

A → 82A → 1162 → 196 → 790 → 895 → 1032 → 33 → 4A → 888 → 1177 → 576 → 5723 → A3 → 8793 → 1210 → A

25A → 940 → 661 → 364 → 25A

366 → 388 → 876 → 894 → A87 → 1437 → 366

49A → 1390 → 629 → 797 → 1077 → 575 → 49A

--

| 12

577, 668, A83, 11AA
--

| 13

490, 491, 509, B8513 → 22 → 13
--

| 14

136, 409
--

| 15

C3A, D87
--

| 16

23, 40, 41, 156, 173, 208, 248, 285, 4A5, 580, 581, 60B, 64B, 8C0, 8C1, 99A, AA9, AC3, CA8, E69, EA0, EA1
--

| rowspan="7" | 4

3\varnothing121 → 200 → 121

122 → 1020 → 122

--

| 4

1103, 33033 → 1101 → 3
--

| 5

2124, 2403, 31341234 → 2404 → 4103 → 2323 → 1234

2324 → 2434 → 4414 → 11034 → 2324

3444 → 11344 → 4340 → 4333 → 3444

--

| 6

\varnothing
--

| 7

\varnothing
--

| 8

20, 21, 400, 401, 420, 421
--

| 9

432, 2466
--

| rowspan="2" | 5

31020, 1021, 2102, 10121\varnothing
--

| 4

2003 → 3303 → 23121 → 10311 → 3312 → 20013 → 10110 → 3

3311 → 13220 → 10310 → 3311

Extension to negative integers

Perfect digital invariants can be extended to the negative integers by use of a signed-digit representation to represent each integer.

= Balanced ternary =

In balanced ternary, the digits are 1, −1 and 0. This results in the following:

  • With odd powers p \equiv 1 \bmod 2, F_{p, \text{bal}3} reduces down to digit sum iteration, as (-1)^p = -1, 0^p = 0 and 1^p = 1.
  • With even powers p \equiv 0 \bmod 2, F_{p, \text{bal}3} indicates whether the number is even or odd, as the sum of each digit will indicate divisibility by 2 if and only if the sum of digits ends in 0. As 0^p = 0 and (-1)^p = 1^p = 1, for every pair of digits 1 or −1, their sum is 0 and the sum of their squares is 2.

Relation to happy numbers

{{Main|Happy number}}

A happy number n for a given base b and a given power p is a preperiodic point for the perfect digital invariant function F_{p, b} such that the m-th iteration of F_{p, b} is equal to the trivial perfect digital invariant 1, and an unhappy number is one such that there exists no such m.

Programming example

The example below implements the perfect digital invariant function described in the definition above to search for perfect digital invariants and cycles in Python. This can be used to find happy numbers.

def pdif(x: int, p: int, b: int) -> int:

"""Perfect digital invariant function."""

total = 0

while x > 0:

total = total + pow(x % b, p)

x = x // b

return total

def pdif_cycle(x: int, p: int, b: int) -> list[int]:

seen = []

while x not in seen:

seen.append(x)

x = pdif(x, p, b)

cycle = []

while x not in cycle:

cycle.append(x)

x = pdif(x, p, b)

return cycle

See also

References

{{reflist}}