Automorphic number

In mathematics, an automorphic number (sometimes referred to as a circular number) is a natural number in a given number base ${\displaystyle b}$ whose square "ends" in the same digits as the number itself.

Definition and properties

Given a number base ${\displaystyle b}$, a natural number ${\displaystyle n}$ with ${\displaystyle k}$ digits is an automorphic number if ${\displaystyle n}$ is a fixed point of the polynomial function ${\displaystyle f(x)=x^{2}}$ over ${\displaystyle \mathbb {Z} /b^{k}\mathbb {Z} }$, the ring of integers modulo ${\displaystyle b^{k}}$. As the inverse limit of ${\displaystyle \mathbb {Z} /b^{k}\mathbb {Z} }$ is ${\displaystyle \mathbb {Z} _{b}}$, the ring of ${\displaystyle b}$-adic integers, automorphic numbers are used to find the numerical representations of the fixed points of ${\displaystyle f(x)=x^{2}}$ over ${\displaystyle \mathbb {Z} _{b}}$.

For example, with ${\displaystyle b=10}$, there are four 10-adic fixed points of ${\displaystyle f(x)=x^{2}}$, the last 10 digits of which are

${\displaystyle \ldots 0000000000}$

${\displaystyle \ldots 0000000001}$

${\displaystyle \ldots 8212890625}$ (sequence A018247 in the OEIS)

${\displaystyle \ldots 1787109376}$ (sequence A018248 in the OEIS)

Thus, the automorphic numbers in base 10 are 0, 1, 5, 6, 25, 76, 376, 625, 9376, ... (sequence A003226 in the OEIS).

A fixed point of ${\displaystyle f(x)}$ is a zero of the function ${\displaystyle g(x)=f(x)-x}$. In the ring of integers modulo ${\displaystyle b}$, there are ${\displaystyle 2^{\omega (b)}}$ zeroes to ${\displaystyle g(x)=x^{2}-x}$, where the prime omega function ${\displaystyle \omega (b)}$ is the number of distinct prime factors in ${\displaystyle b}$. An element ${\displaystyle x}$ in ${\displaystyle \mathbb {Z} /b\mathbb {Z} }$ is a zero of ${\displaystyle g(x)=x^{2}-x}$ if and only if ${\displaystyle x\equiv 0{\bmod {p}}^{v_{p}(b)}}$ or ${\displaystyle x\equiv 1{\bmod {p}}^{v_{p}(b)}}$ for all ${\displaystyle p|x}$. Since there are two possible values in ${\displaystyle \lbrace 0,1\rbrace }$, and there are ${\displaystyle \omega (b)}$ such ${\displaystyle p|x}$, there are ${\displaystyle 2^{\omega (b)}}$ zeroes of ${\displaystyle g(x)=x^{2}-x}$, and thus there are ${\displaystyle 2^{\omega (b)}}$ fixed points of ${\displaystyle f(x)=x^{2}}$. According to Hensel's lemma, if there are ${\displaystyle k}$ zeroes or fixed points of a polynomial function modulo ${\displaystyle b}$, then there are ${\displaystyle k}$ corresponding zeroes or fixed points of the same function modulo any power of ${\displaystyle b}$, and this remains true in the inverse limit. Thus, in any given base ${\displaystyle b}$ there are ${\displaystyle 2^{\omega (b)}}$ ${\displaystyle b}$-adic fixed points of ${\displaystyle f(x)=x^{2}}$.

As 0 is always a zero divisor, 0 and 1 are always fixed points of ${\displaystyle f(x)=x^{2}}$, and 0 and 1 are automorphic numbers in every base. These solutions are called trivial automorphic numbers. If ${\displaystyle b}$ is a prime power, then the ring of ${\displaystyle b}$-adic numbers has no zero divisors other than 0, so the only fixed points of ${\displaystyle f(x)=x^{2}}$ are 0 and 1. As a result, nontrivial automorphic numbers, those other than 0 and 1, only exist when the base ${\displaystyle b}$ has at least two distinct prime factors.

Automorphic numbers in base ${\displaystyle b}$

All ${\displaystyle b}$-adic numbers are represented in base ${\displaystyle b}$, using A−Z to represent digit values 10 to 35.

${\displaystyle b}$	Prime factors of ${\displaystyle b}$	Fixed points in ${\displaystyle \mathbb {Z} /b\mathbb {Z} }$ of ${\displaystyle f(x)=x^{2}}$	${\displaystyle b}$-adic fixed points of ${\displaystyle f(x)=x^{2}}$	Automorphic numbers in base ${\displaystyle b}$
6	2, 3	0, 1, 3, 4	${\displaystyle \ldots 0000000000}$ ${\displaystyle \ldots 0000000001}$ ${\displaystyle \ldots 2221350213}$ ${\displaystyle \ldots 3334205344}$	0 1 3, 13, 213, 50213, 350213, 1350213, 21350213, 221350213, 3334205344 ... 4, 44, 344, 5344, 205344, 4205344, 34205344, 334205344, 2221350213 ...
10	2, 5	0, 1, 5, 6	${\displaystyle \ldots 0000000000}$ ${\displaystyle \ldots 0000000001}$ ${\displaystyle \ldots 8212890625}$ ${\displaystyle \ldots 1787109376}$	0, 1, 5, 6, 25, 76, 376, 625, 9376, 90625, 109376, 890625, 2890625, 7109376, 12890625, 87109376, 212890625, 787109376, 1787109376, 8212890625 ...
12	2, 3	0, 1, 4, 9	${\displaystyle \ldots 0000000000}$ ${\displaystyle \ldots 0000000001}$ ${\displaystyle \ldots 21{\text{B}}61{\text{B}}3854}$ ${\displaystyle \ldots 9{\text{A}}05{\text{A}}08369}$	0, 1, 4, 9, 54, 69, 369, 854, 3854, 8369, B3854, 1B3854, A08369, 5A08369, 61B3854, B61B3854, 1B61B3854, A05A08369, 21B61B3854, 9A05A08369 ...
14	2, 7	0, 1, 7, 8	${\displaystyle \ldots 0000000000}$ ${\displaystyle \ldots 0000000001}$ ${\displaystyle \ldots 7337{\text{A}}{\text{A}}0{\text{C}}37}$ ${\displaystyle \ldots 6{\text{A}}{\text{A}}633{\text{D}}1{\text{A}}8}$	0, 1, 7, 8, 37, A8, 1A8, C37, D1A8, 3D1A8, A0C37, 33D1A8, AA0C37, 633D1A8, 7AA0C37, 37AA0C37, A633D1A8, 337AA0C37, AA633D1A8, 7337AA0C37, 6AA633D1A8 ...
15	3, 5	0, 1, 6, 10	${\displaystyle \ldots 0000000000}$ ${\displaystyle \ldots 0000000001}$ ${\displaystyle \ldots 624{\text{D}}4{\text{B}}{\text{D}}{\text{A}}86}$ ${\displaystyle \ldots 8{\text{C}}{\text{A}}1{\text{A}}3146{\text{A}}}$	0, 1, 6, A, 6A, 86, 46A, A86, 146A, DA86, 3146A, BDA86, 4BDA86, A3146A, 1A3146A, D4BDA86, 4D4BDA86, A1A3146A, 24D4BDA86, CA1A3146A, 624D4BDA86, 8CA1A3146A ...
18	2, 3	9, 10	...1249 ...GFDA
20	2, 5	5, 16	...B6B5 ...8D8G
21	3, 7	7, 15	...H7G7 ...3D4F
22	2, 11	11, 12	...185B ...KDGC
24	2, 3	9, 16	...D0L9 ...AN2G
26	2, 13	13, 14	...1G6D ...O9JE
28	2, 7	8, 21
30	2, 3, 5	6, 10, 15, 16, 21, 25	...B2J6 ...H13A ...1Q7F ...S3MG ...CSQL ...IRAP
33	3, 11	12, 22
34	2, 17	17, 18
35	5, 7	15, 21
36 (6^2)	2, 3	9, 28 (13, 44 in base 6)	...DN29 (...21350213 in base 6) ...MCXS (...34205344 in base 6)

Extensions

Automorphic numbers can be extended to any such polynomial function of degree ${\displaystyle n}$ ${\displaystyle f(x)=\sum _{i=0}^{n}a_{i}x^{i}}$ with b-adic coefficients ${\displaystyle a_{i}}$. These generalised automorphic numbers form a tree.

${\displaystyle a}$-automorphic numbers

An ${\displaystyle a}$-automorphic number occurs when the polynomial function is ${\displaystyle f(x)=ax^{2}}$

For example, with ${\displaystyle b=10}$ and ${\displaystyle a=2}$, as there are two fixed points for ${\displaystyle f(x)=2x^{2}}$ in ${\displaystyle \mathbb {Z} /10\mathbb {Z} }$ (${\displaystyle x=0}$ and ${\displaystyle x=8}$), according to Hensel's lemma there are two 10-adic fixed points for ${\displaystyle f(x)=2x^{2}}$,

${\displaystyle \ldots 0000000000}$

${\displaystyle \ldots 0893554688}$

so the 2-automorphic numbers in base 10 are 0, 8, 88, 688, 4688...

Trimorphic numbers

A trimorphic number or spherical number occurs when the polynomial function is ${\displaystyle f(x)=x^{3}}$ .[1] All automorphic numbers are trimorphic. The terms circular and spherical were formerly used for the slightly different case of a number whose powers all have the same last digit as the number itself.[2]

For base ${\displaystyle b=10}$, the trimorphic numbers are:

0, 1, 4, 5, 6, 9, 24, 25, 49, 51, 75, 76, 99, 125, 249, 251, 375, 376, 499, 501, 624, 625, 749, 751, 875, 999, 1249, 3751, 4375, 4999, 5001, 5625, 6249, 8751, 9375, 9376, 9999, ... (sequence A033819 in the OEIS)

For base ${\displaystyle b=12}$, the trimorphic numbers are:

0, 1, 3, 4, 5, 7, 8, 9, B, 15, 47, 53, 54, 5B, 61, 68, 69, 75, A7, B3, BB, 115, 253, 368, 369, 4A7, 5BB, 601, 715, 853, 854, 969, AA7, BBB, 14A7, 2369, 3853, 3854, 4715, 5BBB, 6001, 74A7, 8368, 8369, 9853, A715, BBBB, ...

Programming example

def hensels_lemma(polynomial_function, base: int, power: int):
    """Hensel's lemma."""
    if power == 0:
        return [0]
    if power > 0:
        roots = hensels_lemma(polynomial_function, base, power - 1)
    new_roots = []
    for root in roots:
        for i in range(0, base):
            new_i = i * base ** (power - 1) + root
            new_root = polynomial_function(new_i) % pow(base, power)
            if new_root == 0:
                new_roots.append(new_i)
    return new_roots

base = 10
digits = 10

def automorphic_polynomial(x):
    return x ** 2 - x

for i in range(1, digits + 1):
    print(hensels_lemma(automorphic_polynomial, base, i))

See also

• Arithmetic dynamics
• Kaprekar number
• P-adic number
• P-adic analysis
• Zero divisor

References

1. See Gérard Michon's article at
2. "spherical number". Oxford English Dictionary (3rd ed.). Oxford University Press. September 2005. (Subscription or UK public library membership required.)

• examples of 1-automorphic numbers at PlanetMath.org.

External links

• Weisstein, Eric W. "Automorphic number". MathWorld.
• Weisstein, Eric W. "Trimorphic Number". MathWorld.