HOME

TheInfoList



OR:

In
number theory Number theory is a branch of pure mathematics devoted primarily to the study of the integers and arithmetic functions. Number theorists study prime numbers as well as the properties of mathematical objects constructed from integers (for example ...
, 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 Power may refer to: Common meanings * Power (physics), meaning "rate of doing work" ** Engine power, the power put out by an engine ** Electric power, a type of energy * Power (social and political), the ability to influence people or events Math ...
(p).''Perfect and PluPerfect Digital Invariants''
by Scott Moore

by Harvey Heinz


Definition

Let n be a
natural number In mathematics, the natural numbers are the numbers 0, 1, 2, 3, and so on, possibly excluding 0. Some start counting with 0, defining the natural numbers as the non-negative integers , while others start with 1, defining them as the positive in ...
. The perfect digital invariant function (also known as a happy function, from
happy number In number theory, a happy number is a number which eventually reaches 1 when the number is replaced by the sum of the square of each digit. For instance, 13 is a happy number because 1^2+3^2=10, and 1^2+0^2=1. On the other hand, 4 is not a happy ...
s) for base b > 1 and power p > 0 F_ : \mathbb \rightarrow \mathbb is defined as: :F_(n) = \sum_^ d_i^p. where k = \lfloor \log_ \rfloor + 1 is the number of digits in the number in base b, and :d_i = \frac 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_, which occurs if F_(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 In mathematics, in the study of iterated functions and dynamical systems, a periodic point of a function (mathematics), function is a point which the system returns to after a certain number of function iterations or a certain amount of time. It ...
for F_, where F_^k(n) = n for a positive
integer An integer is the number zero (0), a positive natural number (1, 2, 3, ...), or the negation of a positive natural number (−1, −2, −3, ...). The negations or additive inverses of the positive natural numbers are referred to as negative in ...
k (here F_^k is the kth
iterate Iteration is the repetition of a process in order to generate a (possibly unbounded) sequence of outcomes. Each repetition of the process is a single iteration, and the outcome of each iteration is then the starting point of the next iteration. ...
of F_), 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_, regardless of the base. This is because if k \geq p + 2, n \geq b^ > b^p k, so any n will satisfy n > F_(n) until n < b^. There are a finite number of natural numbers less than b^, so the number is guaranteed to reach a periodic point or a fixed point less than b^, 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. The number of iterations i needed for F_^(n) to reach a fixed point is the perfect digital invariant function's
persistence Persistence or Persist may refer to: Math and computers * Image persistence, in LCD monitors * Persistence (computer science), the characteristic of data that outlives the execution of the program that created it * Persistence of a number, a ma ...
of n, and undefined if it never reaches a fixed point. F_ is the
digit sum In mathematics, the digit sum of a natural number in a given radix, number base is the sum of all its numerical digit, digits. For example, the digit sum of the decimal number 9045 would be 9 + 0 + 4 + 5 = 18. Definition Let n be a natural number. ...
. 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_ reduces to F_, 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_(n) \equiv m \bmod k, where \phi(k) is
Euler's totient function In number theory, Euler's totient function counts the positive integers up to a given integer that are relatively prime to . It is written using the Greek letter phi as \varphi(n) or \phi(n), and may also be called Euler's phi function. In ot ...
. 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''2,''b''

By definition, any three-digit perfect digital invariant n = d_2 d_1 d_0 for F_ with natural number digits 0 \leq d_0 < b, 0 \leq d_1 < b, 0 \leq d_2 < b has to satisfy the
cubic Cubic may refer to: Science and mathematics * Cube (algebra), "cubic" measurement * Cube, a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex ** Cubic crystal system, a crystal system w ...
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. 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 In mathematics, a divisor of an integer n, also called a factor of n, is an integer m that may be multiplied by some integer to produce n. In this case, one also says that n is a '' multiple'' of m. An integer n is divisible or evenly divisibl ...
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_, 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_.


''F''3,''b''

By definition, any four-digit perfect digital invariant n for F_ 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 Cubic may refer to: Science and mathematics * Cube (algebra), "cubic" measurement * Cube, a three-dimensional solid object bounded by six square faces, facets or sides, with three meeting at each vertex ** Cubic crystal system, a crystal system w ...
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_ for all k. *n_2 = kb^2 + (2k + 1)b + 1 is a perfect digital invariant for F_ for all k. *n_3 = (k + 1)b^2 + (2k + 1) is a perfect digital invariant for F_ for all k.


''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_ for all k.


''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_ for all k.


''F''''p'',''b''

All numbers are represented in base b.


Extension to negative integers

Perfect digital invariants can be extended to the negative integers by use of a
signed-digit representation In mathematical notation for numbers, a signed-digit representation is a positional numeral system with a set of signed digits used to encode the integers. Signed-digit representation can be used to accomplish fast addition of integers becau ...
to represent each integer.


Balanced ternary

In
balanced ternary Balanced ternary is a ternary numeral system (i.e. base 3 with three Numerical digit, digits) that uses a balanced signed-digit representation of the integers in which the digits have the values −1, 0, and 1. This stands in contrast to the stand ...
, the digits are 1, −1 and 0. This results in the following: * With odd powers p \equiv 1 \bmod 2, F_ reduces down to
digit sum In mathematics, the digit sum of a natural number in a given radix, number base is the sum of all its numerical digit, digits. For example, the digit sum of the decimal number 9045 would be 9 + 0 + 4 + 5 = 18. Definition Let n be a natural number. ...
iteration, as (-1)^p = -1, 0^p = 0 and 1^p = 1. * With even powers p \equiv 0 \bmod 2, F_ indicates whether the number is even or odd, as the sum of each digit will indicate divisibility by 2
if and only if In logic and related fields such as mathematics and philosophy, "if and only if" (often shortened as "iff") is paraphrased by the biconditional, a logical connective between statements. The biconditional is true in two cases, where either bo ...
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

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_ such that the m-th iteration of F_ 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 Python may refer to: Snakes * Pythonidae, a family of nonvenomous snakes found in Africa, Asia, and Australia ** ''Python'' (genus), a genus of Pythonidae found in Africa and Asia * Python (mythology), a mythical serpent Computing * Python (prog ...
. 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 nt 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 Arithmetic dynamics is a field that amalgamates two areas of mathematics, dynamical systems and number theory. Part of the inspiration comes from complex dynamics, the study of the Iterated function, iteration of self-maps of the complex plane or o ...
*
Dudeney number In number theory, a Dudeney number in a given number base b is a natural number equal to the perfect cube of another natural number such that the digit sum of the first natural number is equal to the second. The name derives from Henry Dudeney, ...
* Factorion *
Happy number In number theory, a happy number is a number which eventually reaches 1 when the number is replaced by the sum of the square of each digit. For instance, 13 is a happy number because 1^2+3^2=10, and 1^2+0^2=1. On the other hand, 4 is not a happy ...
*
Kaprekar's constant In number theory, Kaprekar's routine is an iterative algorithm named after its inventor, Indian mathematician D. R. Kaprekar. Each iteration starts with a four-digit random number, sorts the digits into descending and ascending order, and calculate ...
*
Kaprekar number In mathematics, a natural number in a given number base is a p-Kaprekar number if the representation of its square in that base can be split into two parts, where the second part has p digits, that add up to the original number. For example, in ...
* Meertens number * Narcissistic number *
Perfect digit-to-digit invariant In number theory, a perfect digit-to-digit invariant (PDDI; also known as a Munchausen number) is a natural number in a given number base b that is equal to the sum of its digits each raised to the power of itself. An example in base 10 is 3435, b ...
*
Sum-product number A sum-product number in a given number base b is a natural number that is equal to the product of the sum of its digits and the product of its digits. There are a finite number of sum-product numbers in any given base b. In base 10, there are ...


References


External links


Digital Invariants
{{Classes of natural numbers Arithmetic dynamics Articles with example Python (programming language) code Base-dependent integer sequences Diophantine equations