View source for Automorphic number

{{Short description|Number whose square ends in the same digits}}
{{no footnotes|date=March 2013}}
In [[mathematics]], an '''automorphic number''' (sometimes referred to as a '''circular number''') is a [[natural number]] in a given [[number base]] <math>b</math> whose [[square (algebra)|square]] "ends" in the same digits as the number itself.

==Definition and properties==
Given a number base <math>b</math>, a natural number <math>n</math> with <math>k</math> digits is an '''automorphic number''' if <math>n</math> is a [[fixed point (mathematics)|fixed point]] of the [[polynomial function]] <math>f(x) = x^2</math> over <math>\mathbb{Z}/b^k\mathbb{Z}</math>, the [[ring (mathematics)|ring]] of [[Modular arithmetic#Integers modulo m|integers modulo]] <math>b^k</math>. As the [[inverse limit]] of <math>\mathbb{Z}/b^k\mathbb{Z}</math> is <math>\mathbb{Z}_b</math>, the ring of [[P-adic number|<math>b</math>-adic]] integers, automorphic numbers are used to find the numerical representations of the fixed points of <math>f(x) = x^2</math> over <math>\mathbb{Z}_b</math>. 

For example, with <math>b = 10</math>, there are four 10-adic fixed points of <math>f(x) = x^2</math>, the last 10 digits of which are:
: <math>\ldots 0000000000</math>
: <math>\ldots 0000000001</math>
: <math>\ldots 8212890625</math> {{OEIS|id=A018247}}
: <math>\ldots 1787109376</math> {{OEIS|id=A018248}}
Thus, the automorphic numbers in [[base 10]] are 0, 1, 5, 6, 25, 76, 376, 625, 9376, 90625, 109376, 890625, 2890625, 7109376, 12890625, 87109376, 212890625, 787109376, 1787109376, 8212890625, 18212890625, 81787109376, 918212890625, 9918212890625, 40081787109376, 59918212890625, ... {{OEIS|A003226}}.

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

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

===Automorphic numbers in base ''b''===
All <math>b</math>-adic numbers are represented in base <math>b</math>, using A−Z to represent digit values 10 to 35.
{| class="wikitable"
! <math>b</math>
! Prime factors of <math>b</math>
! Fixed points in <math>\mathbb{Z}/b\mathbb{Z}</math> of <math>f(x) = x^2</math>
! <math>b</math>-adic fixed points of <math>f(x) = x^2</math>
! Automorphic numbers in base <math>b</math>
|-----
| 6 || 2, 3 || 0, 1, 3, 4 || 
<math>\ldots 0000000000</math>

<math>\ldots 0000000001</math>

<math>\ldots 2221350213</math>

<math>\ldots 3334205344</math>
|| 
0, 1, 3, 4, 13, 44, 213, 344, 5344, 50213, 205344, 350213, 1350213, 4205344, 21350213, 34205344, 221350213, 334205344, 2221350213, 3334205344, ...
|-----
| 10 || 2, 5 || 0, 1, 5, 6 || 
<math>\ldots 0000000000</math>

<math>\ldots 0000000001</math>

<math>\ldots 8212890625</math>

<math>\ldots 1787109376</math>
|| 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 || 
<math>\ldots 0000000000</math>

<math>\ldots 0000000001</math>

<math>\ldots 21\text{B}61\text{B}3854</math>

<math>\ldots 9\text{A}05\text{A}08369</math>
|| 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 || 
<math>\ldots 0000000000</math>

<math>\ldots 0000000001</math>

<math>\ldots 7337\text{A}\text{A}0\text{C}37</math>

<math>\ldots 6\text{A}\text{A}633\text{D}1\text{A}8</math>
|| 0, 1, 7, 8, 37, A8, 1A8, C37, D1A8, 3D1A8, A0C37, 33D1A8, AA0C37, 633D1A8, 7AA0C37, 37AA0C37, A633D1A8, 337AA0C37, AA633D1A8, 6AA633D1A8, 7337AA0C37, ...
|-----
| 15 || 3, 5 || 0, 1, 6, 10 || 
<math>\ldots 0000000000</math>

<math>\ldots 0000000001</math>

<math>\ldots 624\text{D}4\text{B}\text{D}\text{A}86</math>

<math>\ldots 8\text{C}\text{A}1\text{A}3146\text{A}</math>
|| 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 || 0, 1, 9, 10 || 
...000000

...000001

...4E1249

...D3GFDA
||
|-----
| 20 || 2, 5 || 0, 1, 5, 16 || 
...000000

...000001

...1AB6B5

...I98D8G
||
|-----
| 21 || 3, 7 || 0, 1, 7, 15 || 
...000000

...000001

...86H7G7

...CE3D4F
||
|-----
| 22 || 2, 11 || 0, 1, 11, 12 || 
...000000

...000001

...8D185B

...D8KDGC
||
|-----
| 24 || 2, 3 || 0, 1, 9, 16 || 
...000000

...000001

...E4D0L9

...9JAN2G
||
|-----
| 26 || 2, 13 || 0, 1, 13, 14 || 
...0000

...0001

...1G6D

...O9JE
||
|-----
| 28 || 2, 7 || 0, 1, 8, 21 ||
...0000

...0001

...AAQ8

...HH1L
||
|-----
| 30 || 2, 3, 5 || 0, 1, 6, 10, 15, 16, 21, 25
|| 
...0000

...0001

...B2J6

...H13A

...1Q7F

...S3MG

...CSQL

...IRAP
||
|-----
| 33 || 3, 11 || 0, 1, 12, 22 || 
...0000

...0001

...1KPM

...VC7C
||
|-----
| 34 || 2, 17 || 0, 1, 17, 18 || 
...0000

...0001

...248H

...VTPI
|-----
| 35 || 5, 7 || 0, 1, 15, 21 || 
...0000

...0001

...5MXL

...TC1F
||
|-----
| 36 || 2, 3 || 0, 1, 9, 28 || 
...0000

...0001

...DN29

...MCXS
||
|}

==Extensions==
Automorphic numbers can be extended to any such polynomial function of [[degree of a polynomial|degree]] <math>n</math> <math display="inline">f(x) = \sum_{i = 0}^{n} a_i x^i</math> with ''b''-adic coefficients <math>a_i</math>. These generalised automorphic numbers form a [[Tree structure|tree]].

===''a''-automorphic numbers===
An <math>a</math>-'''automorphic number''' occurs when the polynomial function is <math>f(x) = ax^2</math> 

For example, with <math>b = 10</math> and <math>a = 2</math>, as there are two fixed points for <math>f(x) = 2x^2</math> in <math>\mathbb{Z}/10\mathbb{Z}</math> (<math>x = 0</math> and <math>x = 8</math>), according to [[Hensel's lemma]] there are two 10-adic fixed points for <math>f(x) = 2x^2</math>, 
: <math>\ldots 0000000000</math>
: <math>\ldots 0893554688</math>
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 <math>f(x) = x^3</math>.<ref>[http://www.numericana.com/answer/p-adic.htm#decimal See Gérard Michon's article at]</ref> 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.<ref>{{cite OED|spherical number}}</ref>

For base <math>b = 10</math>, 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, ... {{OEIS|id=A033819}}

For base <math>b = 12</math>, 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==
<syntaxhighlight lang="python">
def hensels_lemma(polynomial_function, base: int, power: int) -> list[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: int) -> int:
    return x ** 2 - x

for i in range(1, digits + 1):
    print(hensels_lemma(automorphic_polynomial, base, i))
</syntaxhighlight>

==See also==
* [[Arithmetic dynamics]]
* [[Kaprekar number]]
* [[p-adic number|''p''-adic number]]
* [[p-adic analysis|''p''-adic analysis]]
* [[Zero-divisor]]

==References==
<references />
* {{PlanetMath |urlname=examplesof1automorphicnumbers |title=examples of 1-automorphic numbers}}

== External links ==
*{{MathWorld | urlname=AutomorphicNumber | title=Automorphic number}}
*{{MathWorld | urlname=TrimorphicNumber | title=Trimorphic Number }}

{{Classes of natural numbers}}
[[Category:Arithmetic dynamics]]
[[Category:Base-dependent integer sequences]]
[[Category:Mathematical analysis]]
[[Category:Modular arithmetic]]
[[Category:Number theory]]
[[Category:P-adic numbers]]
[[Category:Ring theory]]