Thursday, January 18, 2018

Automorphic Numbers

While learning your multiplication tables, you may have noticed a peculiar property that some numbers, when multiplied by itself, ends in the same number.  For example, for 5 · 5 = 25, the product 25 ends in the same way as its square root, 5.  Such a number is called an automorphic number.  There are several methods for finding automorphic numbers.

Method 1 – Testing All Numbers

It is a simple exercise to find all the single-digit automorphic numbers by testing each single digit by hand:

0 · 0 = 0 (yes)
1 · 1 = 1 (yes)
2 · 2 = 4 (no)
3 · 3 = 9 (no)
4 · 4 = 16 (no)
5 · 5 = 25 (yes)
6 · 6 = 36 (yes)
7 · 7 = 49 (no)
8 · 8 = 64 (no)
9 · 9 = 81 (no)

Therefore, the only single-digit automorphic numbers are 0, 1, 5, and 6.

Trying to find automorphic numbers with multiple digits in this way would be very time-consuming, so here is a computer program that tests every number within a given range:

01
# Automorphic Numbers (Method 1)
02
# Python 2.7.3
03
# To find all automorphic numbers less than n, type "automorphic(n)".
04
#   For example, to find all automorphic numbers less than 1000, type
05
#   "automorphic(1000)".
06

07
# find all automorphic numbers less than n
08

09
def automorphic(n):
10
    # set up variables
11
    exponent = 2
12
    total = 0
13

14
    # print a title
15
    print "Automorphic Numbers from 1 to " + str(n) + ":"
16

17
    # go through each number and see if it has the same ending as its square.
18
    for a in range(1, n):
19
        if (str(a ** exponent))[-len(str(a)):] == str(a):
20
            # if it is automorphic, print it and add one to the total
21
            print "  " + str(a)
22
            total += 1
23

24
    # print the total
25
    print "Total: " + str(total)

According to this, the automorphic numbers between 1 and 1,000,000 are:

>> automorphic(1000000)
Automorphic Numbers from 1 to 1000000:
  1
  5
  6
  25
  76
  376
  625
  9376
  90625
  109376
  890625
Total: 11

Method 2 – Modular Arithmetic

As the number of digits increase, the above method becomes slower and slower, even for a computer.  Fortunately, the method for finding automorphic numbers can be shortened significantly by making use of the fact that the last digit of any product is determined by the last digit of its factors only.  Therefore, all double-digit automorphic numbers must end in one of the single-digit automorphic numbers.  A similar argument can be made to show that all three-digit automorphic numbers must end in one of the two-digit automorphic numbers, all four-digit automorphic numbers must end in one of the three-digit automorphic numbers, and so on.

The calculations for finding an automorphic number with multiple digits can be made even faster by making use of algebra.  Let n be an already known automorphic number with k digits, and m be the unknown first digit of an unknown automorphic numbers with k + 1 digits, then the unknown automorphic number can be expressed as 10km + n, and since m is a single digit, 0 ≤ m ≤ 9.  Furthermore, as an automorphic number, the square of 10km + n, when divided by 10k+1, must have a remainder of 10km + n, so (10km + n)2 ≡ 10km + n (mod 10k+1).  Simplifying,

01
(10km + n)2 ≡ 10km + n
(mod 10k+1)
(given)
02
102km + 2·10kmn + n2 ≡ 10km + n
(mod 10k+1)
(expand)
03
2·10kmn + n2 ≡ 10km + n
(mod 10k+1)
(102km (mod 10k+1) = 0)
04
2·10kmn – 10km ≡ n – n2
(mod 10k+1)
(subtract n2 and 10km)
05
(2n – 1)10km ≡ n – n2
(mod 10k+1)
(factor 10km)
06
(2n – 1)m ≡ n – n^2/10^k
(mod 10)
(divide by 10k)

Therefore, if n is an already known automorphic number with k digits, the last digit of (2n – 1)m mod 10 must be the same as the last digit of n – n^2/10^k (mod 10) and 0 ≤ m ≤ 9.

So to find all the double-digit automorphic numbers, test all known single-digit automorphic numbers as n (n = 0, n = 1, n = 5, and n = 6) and let k = 1.  Then:
For n = 0, (2n – 1)m ≡ n – n^2/10^k (mod 10) becomes 9m ≡ 0 (mod 10), which means m = 0 for 0 ≤ m ≤ 9, to make the double-digit automorphic number of 00 (which is a repeat of 0).
For n = 1, (2n – 1)m ≡ n – n^2/10^k (mod 10) becomes m ≡ 0 (mod 10), which means m = 0 for 0 ≤ m ≤ 9, to make the double-digit automorphic number of 01 (which is a repeat of 1).
For n = 5, (2n – 1)m ≡ n – n^2/10^k (mod 10) becomes 9m ≡ 8 (mod 10), which means m = 2 for 0 ≤ m ≤ 9, to make the double-digit automorphic number of 25.
For n = 6, (2n – 1)m ≡ n – n^2/10^k (mod 10) becomes m ≡ 7 (mod 10), which means m = 7 for 0 ≤ m ≤ 9, to make the double-digit automorphic number of 76.

Therefore, the only double-digit automorphic numbers are 25 and 76.  A quick test shows that 25·25 = 625 and 76·76 = 5776.  It should also be noted that when n = 0 and when n = 1, then n – n2 = 0 which means m = 0.  This means that a new automorphic number is never created, so both n = 0 and n = 1 do not need to be tested any more.

For three-digit automorphic numbers, test all known double-digit automorphic numbers as n (n = 25, and n = 76) and let k = 2.  Then:
For n = 25, (2n – 1)m ≡ n – n^2/10^k (mod 10) becomes 9m ≡ 4 (mod 10), which means m = 6 for 0 ≤ m ≤ 9, to make the three-digit automorphic number of 625.
For n = 76, (2n – 1)m ≡ n – n^2/10^k (mod 10) becomes m ≡ 3 (mod 10), which means m = 3 for 0 ≤ m ≤ 9, to make the three-digit automorphic number of 376.

Therefore, the only three-digit automorphic numbers are 625 and 376.  A quick test shows that 625·625 = 390625 and 376·376 = 141376.

Two observations can be made here.  First of all, 2n – 1 (mod 10) is always odd, which means there is exactly one solution for m.  Therefore, for k > 1 digits, there are exactly 2 k-digit automorphic numbers, one always ending in 5 and the other always ending in 6.  (However, sometimes the solution for m is 0, in which case a repeated automorphic number is found.)

Secondly, for k > 1 digits, the 2 k-digit automorphic numbers always add up to 10k + 1.  For example, 25 + 76 = 101 = 102 + 1 for k = 2, and 625 + 376 = 1001 = 103 + 1 for k = 3.  This can be proved by first of all showing that 10k + 1 minus a k-digit automorphic number is another k-digit automorphic number.  Let n be a k-digit automorphic number.  Then by definition, n2 ≡ n (mod 10k).  Then (10k + 1 – n)2 (mod 10k) simplifies to:

01
(10k + 1 – n)2 (mod 10k)
(given)
02
(1 – n)2 (mod 10k)
(10k (mod 10k) = 0)
03
1 – 2n + n2 (mod 10k)
(expand)
04
1 – 2n + n (mod 10k)
(n2 ≡ n (mod 10k))
05
1 – n (mod 10k)
(simplify)
06
10k + 1 – n (mod 10k)
(10k (mod 10k) = 0)

Therefore, (10k + 1 – n)2 ≡ 10k + 1 – n (mod 10k), making it another k-digit automorphic number.  Secondly, since 10k + 1 (mod 10k) is not even, the k-digit automorphic number must be different than its original, and since there are exactly 2 k-digit automorphic numbers (as proved above), the 2 k-digit automorphic numbers must add up to 10k + 1.

Using the shortcuts mentioned above, here is a more efficient computer program that finds all automorphic numbers up to a given digit length long:

01
# Automorphic Numbers (Method 2)
02
# Python 2.7.3
03
# To find all automorphic numbers up to d digits long, type "automorphic(d)".
04
#   For example, to find all automorphic numbers up to 10 digits long, type
05
#   "automorphic(10)".
06

07
# find all automorphic numbers up to d digits long
08
def automorphic(d):
09
    # set up variables
10
    total = 3
11
    n_five = 5
12
    n_six = 6
13

14
    # print a title and the first 3 digits
15
    print "Automorphic Numbers up to " + str(d) + " Digits Long:"
16
    print "  1"
17
    print "  5"
18
    print "  6"
19

20
    # find new n_five and n_six automorphic numbers based on the equations
21
    #  (2n – 1)m (n – n^2)/10^k (mod 10) and n_five + n_six = 10^k + 1
22
    #  for n as a known automorphic number with k digits, and m as the
23
    #  unknown first digit of an automorphic numbers with k + 1 digits.
24
    for k in range(1, d):
25
        m_six = ((n_six - n_six ** 2) / (10 ** k)) % 10
26
        m_five = 9 - m_six
27
        n_six = m_six * 10 ** k + n_six
28
        n_five = m_five * 10 ** k + n_five
29
        # print any new automorphic numbers in order,
30
        #   and add one to the total
31
        if m_six < m_five:
32
            if m_six > 0:
33
                print "  " + str(n_six)
34
                total += 1
35
            if m_five > 0:
36
                print "  " + str(n_five)
37
                total += 1
38
        else:
39
            if m_five > 0:
40
                print "  " + str(n_five)
41
                total += 1
42
            if m_six > 0:
43
                print "  " + str(n_six)
44
                total += 1
45

46
    # print the total
47
    print "Total: " + str(total)

According to this, the automorphic numbers up to 10 digits long are:

>> automorphic(10)
Automorphic Numbers up to 10 Digits Long:
  1
  5
  6
  25
  76
  376
  625
  9376
  90625
  109376
  890625
  2890625
  7109376
  12890625
  87109376
  212890625
  787109376
  1787109376
  8212890625
Total: 19

Method 3 – Automorphic Generator

Another way to find automorphic numbers is to create an automorphic generator using a known automorphic number.  Let n be a known automorphic number of k digits.  Then by definition, n2 – n ≡ 0 (mod 10k) or n(n – 1) ≡ 0 (mod 10k), and squaring this gives n2(n – 1)2 ≡ 0 (mod 102k).  Multiplying by some integer p = p1n + p2 and some integer q = q1n + q2 gives n2(n – 1)2pq ≡ 0 (mod 10k+1).  Then choose p1, p2, q1, and q2 values such that n2(n – 1)2pq = (n2q)2 – n2q (mod 10k+1), then (n2q)2 – n2q ≡ 0 (mod 10k+1) which would make n2q a larger automorphic number by definition.  Given these parameters, some values for p1, p2, q1, and q2 can be found:

01
n2(n – 1)2pq = (n2q)2 – n2q
(mod 10k+1)
(given)
02
n2(n – 1)2pq = n2q(n2q – 1)
(mod 10k+1)
(factor)
03
(n – 1)2p = n2q – 1
(mod 10k+1)
(divide by n2q)
04
(n – 1)2(p1n + p2) = n2(q1n + q2) – 1
(mod 10k+1)
(p = p1n + p2, q = q1n + q2)
05
(n2 – 2n + 1)(p1n + p2) =
q1n3 + q2n2 – 1 (mod 10k+1)
(multiply)
06
p1n3 + (p2–2p1)n2 + (p1–2p2)n + p2 = q1n3 + q2n2 – 1 (mod 10k+1)
(multiply and factor)

One possible solution for this is to set all like terms of n equal to each other, so that p1 = q1 for the n3 terms, p2 – 2p1 = q2 for the n2 terms, p1 – 2p2 = 0 for the n terms, and p2 = -1 for the units.  If p2 = -1 and p1 – 2p2 = 0, then p1 = -2.  If p1 = -2 and p1 = q1, then q1 = -2.  Finally, if p1 = -2 and p2 = -1 and p2 – 2p1 = q2, then q2 = 3.  Therefore, one possible solution is p1 = -2, p2 = -1, q1 = -2, and q2 = 3, which means p = -2n – 1 and q = -2n + 3. 

Therefore, if n is a known automorphic number of k digits, then n2q = -2n3 + 3n2 (mod 10k + 1) is another automorphic number with k + 1 digits.  For example, since 5 is an automorphic number with 1 digit, -2(5)3 + 3(5)2 = -175 ≡ 25 (mod 102) is an automorphic number with 2 digits.

Using the automorphic generator, here is an even more efficient computer program that finds all automorphic numbers up to a given digit length long:

01
# Automorphic Numbers (Method 3)
02
# Python 2.7.3
03
# To find all automorphic numbers up to d digits long, type "automorphic(d)".
04
#   For example, to find all automorphic numbers up to 10 digits long, type
05
#   "automorphic(10)".
06

07
# find all automorphic numbers up to d digits long
08
def automorphic(d):
09
    # set up variables
10
    total = 3
11
    n_five = 5
12
    n_six = 6
13

14
    # print a title and the first 3 digits
15
    print "Automorphic Numbers up to " + str(d) + " Digits Long:"
16
    print "  1"
17
    print "  5"
18
    print "  6"
19

20
    # find new n_five and n_six automorphic numbers based on the equations
21
    #  n' = -2n^3 + 3n^2 (mod 10^(k + 1)) and n_five + n_six = 10^k + 1,
22
    #  for n as a known automorphic number with k digits
23
    for k in range(1, d):
24
        n_five = (-2 * n_five ** 3 + 3 * n_five ** 2) % (10 ** (k + 1))
25
        n_six = 10 ** (k + 1) + 1 - n_five
26
        # print any new automorphic numbers in order,
27
        #   and add one to the total
28
        if n_six < n_five:
29
            if n_six > (10 ** k):
30
                print "  " + str(n_six)
31
                total += 1
32
            if n_five > (10 ** k)::
33
                print "  " + str(n_five)
34
                total += 1
35
        else:
36
            if n_five > (10 ** k):
37
                print "  " + str(n_five)
38
                total += 1
39
            if n_six > (10 ** k):
40
                print "  " + str(n_six)
41
                total += 1
42

43
    # print the total
44
    print "Total: " + str(total)

Its output is the same as the output from Method 2.

This computer program is so efficient that in a relatively short period of time, it can find an automorphic number that is 1000 digits long!  Here it is:

1278125400133690086034889084364023875765936821979626181917833520492704199324875237825867148278905344897440142612317035699548419499444610608146207254036559998271588356035049327795540741961849280952093753026852390937562839148571612367351970609224242398777007574955787271559767413458997537695515862718887941516307569668816352155048898271704378508028434084412644126821848514157729916034497017892335796684991447389566001932545827678000618329854426232827257556110733160697015864984222291255485729879337147866323172405515756102352543994999345608083801190741530060056055744818709692785099775918050075416428527708162011350246806058163276171676765260937528056844214486193960499834472806721906670417240094234466197812426690787535944616698508064636137166384049029219341881909581659524477861846140912878298438431703248173428886572737663146519104988029447960814673760503957196893714671801375619055462996814764263903953007319108169802938509890062166509580863811000557423423230896109004106619977392256259918212890625

Conclusion

An automorphic number has the special property that all of its digits also appear at the end of its square in the same order.  Some interesting properties of automorphic numbers include that there are exactly 2 k-digit automorphic numbers for k > 1 digits, one always ending in 5 and the other always ending in 6, and that these 2 k-digit automorphic numbers always add up to 10k + 1.  Also, if n is a known automorphic number of k digits, then another automorphic number with k + 1 digits can be generated by finding -2n3 + 3n2 (mod 10k + 1).  Finally, although there are several methods for finding an automorphic number, a computer is helpful in each method, especially to find large automorphic numbers.


No comments:

Post a Comment