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 10^km + n, and since m is a single digit, 0 ≤ m ≤ 9.  Furthermore, as an automorphic number, the square of 10^km + n, when divided by 10^k+1, must have a remainder of 10^km + n, so (10^km + n)² ≡ 10^km + n (mod 10^k+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 – n² = 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 10^k + 1.  For example, 25 + 76 = 101 = 10² + 1 for k = 2, and 625 + 376 = 1001 = 10³ + 1 for k = 3.  This can be proved by first of all showing that 10^k + 1 minus a k-digit automorphic number is another k-digit automorphic number.  Let n be a k-digit automorphic number.  Then by definition, n² ≡ n (mod 10^k).  Then (10^k + 1 – n)² (mod 10^k) 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, (10^k + 1 – n)² ≡ 10^k + 1 – n (mod 10^k), making it another k-digit automorphic number.  Secondly, since 10^k + 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 10^k + 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, n² – n ≡ 0 (mod 10^k) or n(n – 1) ≡ 0 (mod 10^k), and squaring this gives n²(n – 1)² ≡ 0 (mod 10^2k).  Multiplying by some integer p = p₁n + p₂ and some integer q = q₁n + q₂ gives n²(n – 1)²pq ≡ 0 (mod 10^k+1).  Then choose p₁, p₂, q₁, and q₂ values such that n²(n – 1)²pq = (n²q)² – n²q (mod 10^k+1), then (n²q)² – n²q ≡ 0 (mod 10^k+1) which would make n²q a larger automorphic number by definition.  Given these parameters, some values for p₁, p₂, q₁, and q₂ 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 p₁ = q₁ for the n³ terms, p₂ – 2p₁ = q₂ for the n² terms, p₁ – 2p₂ = 0 for the n terms, and p₂ = -1 for the units.  If p₂ = -1 and p₁ – 2p₂ = 0, then p₁ = -2.  If p₁ = -2 and p₁ = q₁, then q₁ = -2.  Finally, if p₁ = -2 and p₂ = -1 and p₂ – 2p₁ = q₂, then q₂ = 3.  Therefore, one possible solution is p₁ = -2, p₂ = -1, q₁ = -2, and q₂ = 3, which means p = -2n – 1 and q = -2n + 3. 

Therefore, if n is a known automorphic number of k digits, then n²q = -2n³ + 3n² (mod 10^{k + 1}) is another automorphic number with k + 1 digits.  For example, since 5 is an automorphic number with 1 digit, -2(5)³ + 3(5)2 = -175 ≡ 25 (mod 10²) 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 10^k + 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 -2n³ + 3n² (mod 10^{k + 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.