Perfect digital invariant

In

${\displaystyle b}$

${\displaystyle p}$

Definition

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

${\displaystyle F_{p,b}(n)=\sum _{i=0}^{k-1}d_{i}^{p}.}$

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

${\displaystyle 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 ${\displaystyle n}$ is a perfect digital invariant if it is a fixed point for ${\displaystyle F_{p,b}}$, which occurs if ${\displaystyle F_{p,b}(n)=n}$. ${\displaystyle 0}$ and ${\displaystyle 1}$ are trivial perfect digital invariants for all ${\displaystyle b}$ and ${\displaystyle p}$, all other perfect digital invariants are nontrivial perfect digital invariants.

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

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

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

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

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

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

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

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

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.^[1]

F_2,b

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

${\displaystyle d_{0}^{2}+d_{1}^{2}=d_{1}b+d_{0}}$ when ${\displaystyle d_{2}=0}$, and

${\displaystyle d_{0}^{2}+d_{1}^{2}+1=b^{2}+d_{1}b+d_{0}}$ when ${\displaystyle d_{2}=1}$.

The two-digit natural number ${\displaystyle n=d_{1}d_{0}}$ is a perfect digital invariant in base

${\displaystyle b=d_{1}+{\frac {d_{0}(d_{0}-1)}{d_{1}}}.}$

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

There are no three-digit perfect digital invariants for ${\displaystyle F_{2,b}}$, which can be proven by taking the second case, where ${\displaystyle d_{2}=1}$, and letting ${\displaystyle d_{0}=b-a_{0}}$ and ${\displaystyle d_{1}=b-a_{1}}$. Then the Diophantine equation for the three-digit perfect digital invariant becomes

${\displaystyle (b-a_{0})^{2}+(b-a_{1})^{2}+1=b^{2}+(b-a_{1})b+(b-a_{0})}$

${\displaystyle b^{2}-2a_{0}b+a_{0}^{2}+b^{2}-2a_{1}b+a_{1}^{2}+1=b^{2}+(b-a_{1})b+(b-a_{0})}$

${\displaystyle 2b^{2}-2(a_{0}+a_{1})b+a_{0}^{2}+a_{1}^{2}+1=b^{2}+(b-a_{1})b+(b-a_{0})}$

${\displaystyle 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})}$

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

F_3,b

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

${\displaystyle 153=1^{3}+5^{3}+3^{3}}$

${\displaystyle 370=3^{3}+7^{3}+0^{3}}$

${\displaystyle 371=3^{3}+7^{3}+1^{3}}$

${\displaystyle 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. (sequence A046197 in the OEIS)
— G. H. Hardy, A Mathematician's Apology

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

${\displaystyle d_{0}^{3}+d_{1}^{3}+d_{2}^{3}=d_{2}b^{2}+d_{1}b+d_{0}}$ when ${\displaystyle d_{3}=0}$

${\displaystyle d_{0}^{3}+d_{1}^{3}+d_{2}^{3}+1=b^{3}+d_{2}b^{2}+d_{1}b+d_{0}}$ when ${\displaystyle d_{3}=1}$

${\displaystyle d_{0}^{3}+d_{1}^{3}+d_{2}^{3}+8=2b^{3}+d_{2}b^{2}+d_{1}b+d_{0}}$ when ${\displaystyle d_{3}=2}$

We take the first case, where ${\displaystyle d_{3}=0}$.

b = 3k + 1

Let ${\displaystyle k}$ be a positive integer and the number base ${\displaystyle b=3k+1}$. Then:

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

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

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

Perfect digital invariants

${\displaystyle k}$	${\displaystyle b}$	${\displaystyle n_{1}}$	${\displaystyle n_{2}}$	${\displaystyle n_{3}}$
1	4	130	131	203
2	7	250	251	305
3	10	370	371	407
4	13	490	491	509
5	16	5B0	5B1	60B
6	19	6D0	6D1	70D
7	22	7F0	7F1	80F
8	25	8H0	8H1	90H
9	28	9J0	9J1	A0J

b = 3k + 2

Let ${\displaystyle k}$ be a positive integer and the number base ${\displaystyle b=3k+2}$. Then:

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

Perfect digital invariants

${\displaystyle k}$	${\displaystyle b}$	${\displaystyle n_{1}}$
1	5	103
2	8	205
3	11	307
4	14	409
5	17	50B
6	20	60D
7	23	70F
8	26	80H
9	29	90J

b = 6k + 4

Let ${\displaystyle k}$ be a positive integer and the number base ${\displaystyle b=6k+4}$. Then:

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

Perfect digital invariants

${\displaystyle k}$	${\displaystyle b}$	${\displaystyle n_{4}}$
0	4	021
1	10	153
2	16	285
3	22	3B7
4	28	4E9

F_p,b

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

${\displaystyle p}$	${\displaystyle b}$	Nontrivial perfect digital invariants	Cycles
2	3	12, 22	2 → 11 → 2
	4	${\displaystyle \varnothing }$	${\displaystyle \varnothing }$
	5	23, 33	4 → 31 → 20 → 4
	6	${\displaystyle \varnothing }$	5 → 41 → 25 → 45 → 105 → 42 → 32 → 21 → 5
	7	13, 34, 44, 63	2 → 4 → 22 → 11 → 2 16 → 52 → 41 → 23 → 16
	8	24, 64	4 → 20 → 4 5 → 31 → 12 → 5 15 → 32 → 15
	9	45, 55	58 → 108 → 72 → 58 75 → 82 → 75
	10	${\displaystyle \varnothing }$	4 → 16 → 37 → 58 → 89 → 145 → 42 → 20 → 4
	11	56, 66	5 → 23 → 12 → 5 68 → 91 → 75 → 68
	12	25, A5	5 → 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, C4	28 → 53 → 28 79 → A0 → 79 98 → B2 → 98
	14	${\displaystyle \varnothing }$	1B → 8A → BA → 11B → 8B → D3 → CA → 136 → 34 → 1B 29 → 61 → 29
	15	78, 88	2 → 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	${\displaystyle \varnothing }$	D → A9 → B5 → 92 → 55 → 32 → D
3	3	122	2 → 22 → 121 → 101 → 2
	4	20, 21, 130, 131, 203, 223, 313, 332	${\displaystyle \varnothing }$
	5	103, 433	14 → 230 → 120 → 14
	6	243, 514, 1055	13 → 44 → 332 → 142 → 201 → 13
	7	12, 22, 250, 251, 305, 505	2 → 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, 661	662 → 670 → 1057 → 725 → 734 → 662
	9	30, 31, 150, 151, 570, 571, 1388	38 → 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, 407	55 → 250 → 133 → 55 136 → 244 → 136 160 → 217 → 352 → 160 919 → 1459 → 919
	11	32, 105, 307, 708, 966, A06, A64	3 → 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, B85	13 → 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
4	3	${\displaystyle \varnothing }$	121 → 200 → 121 122 → 1020 → 122
	4	1103, 3303	3 → 1101 → 3
	5	2124, 2403, 3134	1234 → 2404 → 4103 → 2323 → 1234 2324 → 2434 → 4414 → 11034 → 2324 3444 → 11344 → 4340 → 4333 → 3444
	6	${\displaystyle \varnothing }$
	7	${\displaystyle \varnothing }$
	8	20, 21, 400, 401, 420, 421
	9	432, 2466
5	3	1020, 1021, 2102, 10121	${\displaystyle \varnothing }$
	4	200	3 → 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 ${\displaystyle p\equiv 1{\bmod {2}}}$, ${\displaystyle F_{p,{\text{bal}}3}}$ reduces down to digit sum iteration, as ${\displaystyle (-1)^{p}=-1}$, ${\displaystyle 0^{p}=0}$ and ${\displaystyle 1^{p}=1}$.
• With even powers ${\displaystyle p\equiv 0{\bmod {2}}}$, ${\displaystyle 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 ${\displaystyle 0^{p}=0}$ and ${\displaystyle (-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

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

Programming example

The example below implements the perfect digital invariant function described in the definition above

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

• Arithmetic dynamics
• Dudeney number
• Factorion
• Happy number
• Kaprekar's constant
• Kaprekar number
• Meertens number
• Narcissistic number
• Perfect digit-to-digit invariant
• Sum-product number

References

External links

• Digital Invariants