This post is a complete change from my usual subjects.
Many years ago a man named Mike Mudge wrote a monthly column for Personal Computer World called "Numbers Count". There seems to be very little about him on the web, except for other fans like me. One such column inspired the following paper written jointly by my father[1] and I.
This work has just come to light during a recent house move that caused me to search through old papers, and despite it being 20 years ago, a quick search of the web shows that it still contains some original stuff, so I thought it would be interesting to publish it here. I am publishing it here unaltered, though obviously computing power has improved a lot over the years. I have tried to reproduce it exactly, but I may have made some transcribing errors, and if you see any please let me know.
Nb 20 years ago this work was unique to the best of our knowledge, but I can't promise that is still so.
For any value of n, there exists only two n-digit automorphic numbers and these end in the digits 5 or 6.
Proof: Let n= 10a+b represent a two digit number. If n is automorphic then
n^2=100a^2+20ab+b^2=1000z+100y+10a+b ............................. (1)
and b^2=b+10x
where x is an integer. Only b=5 or b=6 satisfy this condition and therefore all 2 digit automorphic numbers must end in 5 or 6.
Substituting b=5 in equation (1) above gives
100a^2+90a=1000z+100y-20
90a must end in the digits 80 and therefore a=2 and n=25.
Substituting b=6 in equation (1) above gives
100a^2+110a=1000z+100y-30
110a must end in the digits 70 and therefore a=7 and n=76.
Let n=100a+10b+c represent a 3 digit number. If n is automorphic then
n^2=10^4*a^2+2ab*10^3+b^2*10^2+2ac*10^2+20bc+c^2=10^5z+10^4y+10^3x+100a+10b+c ........ (2)
and c^2=c+10j where j is an integer, therefore the digit c must be either 5 or 6.
Substituting c=5 in equation (2) gives us
10^4*a^2+2ab*10^3+b^2*10^2+10^3a+10^2b+25=10^5*z+10^4*y+10^3*x+100a+10b+5 ...... (3)
and 90b must end in the digits 80, therefore b must have the value 2.
By the same procedure substituting b=2 into equation (3) gives the value a=6. Substitution of c=6 in equation (2) and repetition of the same procedure gives values of 7 and 3 for b and a respectively.
Therefore to digit automorphic numbers can only be 25 and 76, and 3 digit automorphic numbers can only be 625 and 376.
Proof: Let pq=1000a+100b+10c +d and p^2=1000f+100g+p
Then p^2-pq=1000f+100g+p-1000a-100b-10c-e=p
1000f+100g=1000a+100b+10c+e
Therefore c and d must be zero, and a=f, b=g, and pq=100s where s is an integer.
Proof: Let p=10a+b. If p is automorphic then
p^2=1000l+100m+10a+b=100(10l+m)+p
Let x=10l+m then p^2=100x+p and 100x=p^2-p
Let the 3 digit number be 100A+p, then if this number is automorphic
10^4A^2+200pA+p^2=10^5*z+10^4*y+10^3*x+100A+p and 200pA-100A=p-p^2+1000k
Therefore A(2p-1)+x=10k
By the same procedure it can be shown that for the 4-digit number 1000B+100A+10a+b the leading digit B is given by the expression
B(2p-1)+j=k*10^2 where p=100A+10a+b, j*10^3=p^2-p, and k is an integer.
Proof: Let p=10a+b where p is a 2-digit automorphic number, then p^2=1000l+100m+10a+b
Let the corresponding 3-digit automorphic number 100A+p
From Theorem 3 above we know
A(2p-1)+10l+m=10k where k is an integer
Substituting p=76 we get 151A+10l+m=10k and A*l+m=10
Therefore A=10-m
Substituting p=25 we get 49A+10l+m=10k and A*9+m=10k
Therefore A=m
Proof: Let n=10a+b then 3n^2=300a^2+60ab+3b^2
If n is tri-automorphic then:
300a^2+60ab+3b^2=1000z+100y+10a+b .................. (4)
and 3b^2-b=10x ............................ (5)
where x is an integer. This condition is only satisfied by b=2, b=5, or b=7
Substituting b=2 in equation (4), it follows that a=9
Substituting b=5 in equation (4), it follows that a=7
Substituting b=7 in equation (4), it follows that a=6
Corollary:
For di-automorphic numbers, equation (5) becomes
2b^2-b=10x and b=8
For tetra-automorphic numbers, equation (5) becomes
4b^2-b=10x and b=4
For penta-automorphic numbers, equation (5) becomes
5b^2-b=10x and b=5
1. Only two n-digit automorphic numbers exist for each value of n
2. Such numbers form two series in which successive members differ from their predecessors only in the leading digit.
The first 8 members are shown for example below
In order to convert an n-digit automorphic number into the corresponding (n+1)-digit automorphic number it is necessary only to test the digits 0 to 9 for suitability as the leading digit of the next number. This obviously facilitates the computer generation of automorphic numbers. Furthermore it appears from the above table that the sum of a pair of n-digit automorphic numbers is equal to 10^n+1 (see Conjecture A above), and therefore a sequence of automorphic numbers is uniquely determined by the corresponding pairing sequence.
Theorem 3 allows the calculation of the leading digit of the next automorphic number in the series. If for example p=625 then A*1249+390=10k implies A=0 giving 0625 as the next automorphic number in the sequence. If p=0625 then A*1249+39=10k gives A=9 making the next automorphic number in the sequence 90625.
Theorem 4 provides a simple alternative method for the calculation of the next leading digit in automorphic numbers terminating in the digit 6. If p=376 then p^2=141376 and m, the coefficient of 10^3 is equal to 1. Therefore A=10-1=9 giving 9376 as the 4 digit number.If p=9376 then p^2=87909376 and m the coefficient of 10^4 is equal to zero. Therefore A=10-0=10 giving 09376 as the 5-digit number. If p=625 then p^2=390625 and m, the coefficient of 10^3 is equal to zero giving 0625 as the 4-digit number.The same procedure gives 90625 as the 5-digit number in the sequence.
The programme listing for this procedure is shown in Appendix 2 [5]. Using this procedure, the series of automorphic numbers up to 20,000 digits in length was generated in a run time of 54 minutes. Repetition of the procedure using an AST 486DX running at 50Mhz generated automorphic numbers of up to 32,000 digits in length in a run time of 75 minutes. As a point of interest it may be noted that the leading ten digits and the trailing ten digits of the two 32,000-digit automorphic numbers are as follows:
6351634399..............................................................................8212890625
3648365600..............................................................................1787109376
Appendix 3 lists all the n-automorphic numbers to base b where b=2 to 10 and n=1 to b-1 [6]. The following points may be noted:
1. No base 2 automorphic numbers are apparent.
2. It is conjectured that an (n+1)-automorphic number to the base (n+2) is of the form:
.......nnn(n+1). For the cases n=5, b=6 and n=9, b=10 there are two accompanying numbers while single numbers only occur for all the other cases.
[1] http://www.google.com/patents/US4877732
http://www.google.com/patents/US3636037
http://www.google.com/patents/US4249015
http://www.google.com/patents/US3701779
and others...................
[2] Note the timings given in this paper were from the initial work carried out approximately 20 years ago, and obviously would be very different if repeated these days.
[3] Unfortunately this appendix has been lost, if I find it I will add it here later for the sake of completeness.
[4] I have just run a very simple python script and using a brute force method it generated the first 16 in 128.222 seconds!
[5] Again this programme listing was not found, sparing people from seeing my lack of coding skills from 20 years ago!!
[6] The loss of this appendix is a great shame as this gives some interesting information. I will try to recreate this data at some time.
Many years ago a man named Mike Mudge wrote a monthly column for Personal Computer World called "Numbers Count". There seems to be very little about him on the web, except for other fans like me. One such column inspired the following paper written jointly by my father[1] and I.
This work has just come to light during a recent house move that caused me to search through old papers, and despite it being 20 years ago, a quick search of the web shows that it still contains some original stuff, so I thought it would be interesting to publish it here. I am publishing it here unaltered, though obviously computing power has improved a lot over the years. I have tried to reproduce it exactly, but I may have made some transcribing errors, and if you see any please let me know.
Nb 20 years ago this work was unique to the best of our knowledge, but I can't promise that is still so.
Some properties of Automorphic numbers
Abstract:
An automorphic number is is a number whose square ends in the same digits as number itself. Automorphic numbers form two series ending respectively in the digits 5 and 6. Successive members of each series have the same sequence of trailing digits and are formed simply by appending a new leading digit to their predecessor. Corresponding numbers in the two series bear a simple numerical relation to one another and are co-prime. Consequently, the sequence of one series uniquely determines the sequence of the other series. Some properties of automorphic numbers are discussed and these properties used to develop rapid and efficient methods for the generation of automorphic numbers. One such method generates numbers of up to 32,000 digits in length in a run time of 75 minutes[2]. n-Automorphic numbers to bases other than 10 are briefly discussed.
Introduction:
The computer generation of automorphic numbers using a simple trial and error process soon indicates that there are only three n-digit automorphic numbers for any value of n. One of these consists of the digit 1 with a string of leading zeros and may be regarded as trivial. In the case of the other two, it is found that with the exception of the leading digit, each n-digit automorphic number is identical with the corresponding n-1-digit number, and it is therefore only necessary to determine the leading digit for any n-digit automorphic number. The following describes some properties of automorphic numbers and which lead to more efficient methods for their generation.
Methods
The generation of automorphic numbers was carried out with a Packard-Bell 445 elite 486Ssx running at 33mHz using programmes implemented in turbo pascal.Results
Theorem 1 :For any value of n, there exists only two n-digit automorphic numbers and these end in the digits 5 or 6.
Proof: Let n= 10a+b represent a two digit number. If n is automorphic then
n^2=100a^2+20ab+b^2=1000z+100y+10a+b ............................. (1)
and b^2=b+10x
where x is an integer. Only b=5 or b=6 satisfy this condition and therefore all 2 digit automorphic numbers must end in 5 or 6.
Substituting b=5 in equation (1) above gives
100a^2+90a=1000z+100y-20
90a must end in the digits 80 and therefore a=2 and n=25.
Substituting b=6 in equation (1) above gives
100a^2+110a=1000z+100y-30
110a must end in the digits 70 and therefore a=7 and n=76.
Let n=100a+10b+c represent a 3 digit number. If n is automorphic then
n^2=10^4*a^2+2ab*10^3+b^2*10^2+2ac*10^2+20bc+c^2=10^5z+10^4y+10^3x+100a+10b+c ........ (2)
and c^2=c+10j where j is an integer, therefore the digit c must be either 5 or 6.
Substituting c=5 in equation (2) gives us
10^4*a^2+2ab*10^3+b^2*10^2+10^3a+10^2b+25=10^5*z+10^4*y+10^3*x+100a+10b+5 ...... (3)
and 90b must end in the digits 80, therefore b must have the value 2.
By the same procedure substituting b=2 into equation (3) gives the value a=6. Substitution of c=6 in equation (2) and repetition of the same procedure gives values of 7 and 3 for b and a respectively.
Therefore to digit automorphic numbers can only be 25 and 76, and 3 digit automorphic numbers can only be 625 and 376.
Conjecture A
If p and q are any pair of n-digit automorphic numbers then p+q=10^n+1Conjecture B
If p and q are any pair of n-digit automorphic numbers then p and q are co-prime.Theorem 2
If p is an n-digit automorphic number and q=p-1 then pq=100s where s is an integer.Proof: Let pq=1000a+100b+10c +d and p^2=1000f+100g+p
Then p^2-pq=1000f+100g+p-1000a-100b-10c-e=p
1000f+100g=1000a+100b+10c+e
Therefore c and d must be zero, and a=f, b=g, and pq=100s where s is an integer.
Theorem 3
If p is an n-digit automorphic number and 10^nA+p is the corresponding n+1-digit automorphic number, then A(2p-1)+x=k*10^n-1 where k is an integer and 100x=p^2-pProof: Let p=10a+b. If p is automorphic then
p^2=1000l+100m+10a+b=100(10l+m)+p
Let x=10l+m then p^2=100x+p and 100x=p^2-p
Let the 3 digit number be 100A+p, then if this number is automorphic
10^4A^2+200pA+p^2=10^5*z+10^4*y+10^3*x+100A+p and 200pA-100A=p-p^2+1000k
Therefore A(2p-1)+x=10k
By the same procedure it can be shown that for the 4-digit number 1000B+100A+10a+b the leading digit B is given by the expression
B(2p-1)+j=k*10^2 where p=100A+10a+b, j*10^3=p^2-p, and k is an integer.
Theorem 4
If k is the square of an n-digit automorphic number j ending with the digit 6, then the le4ading digit in the corresponding (n+1)-digit automorphic number is 10-m where m is the coefficient of 10^n in k. For the corresponding n-digit number ending with the digit 5, the leading digit in the corresponding (n+1)-digit number is m where m is the coefficient of 10^n.Proof: Let p=10a+b where p is a 2-digit automorphic number, then p^2=1000l+100m+10a+b
Let the corresponding 3-digit automorphic number 100A+p
From Theorem 3 above we know
A(2p-1)+10l+m=10k where k is an integer
Substituting p=76 we get 151A+10l+m=10k and A*l+m=10
Therefore A=10-m
Substituting p=25 we get 49A+10l+m=10k and A*9+m=10k
Therefore A=m
Theorem 5
For any value of n there exists only three-n-digit tri-automorphic numbers and these end in the digits 2, 5 or 7.Proof: Let n=10a+b then 3n^2=300a^2+60ab+3b^2
If n is tri-automorphic then:
300a^2+60ab+3b^2=1000z+100y+10a+b .................. (4)
and 3b^2-b=10x ............................ (5)
where x is an integer. This condition is only satisfied by b=2, b=5, or b=7
Substituting b=2 in equation (4), it follows that a=9
Substituting b=5 in equation (4), it follows that a=7
Substituting b=7 in equation (4), it follows that a=6
Corollary:
For di-automorphic numbers, equation (5) becomes
2b^2-b=10x and b=8
For tetra-automorphic numbers, equation (5) becomes
4b^2-b=10x and b=4
For penta-automorphic numbers, equation (5) becomes
5b^2-b=10x and b=5
Discussion
Initial computer studies were carried out by testing numbers in sequence for automorphic character. The programme listing is shown in Appendix 1 [3]. As might be expected run times were very long and only 16 automorphic numbers were generated in a run time of 3 hours [4]. These studies did however demonstrate two important properties of automorphic numbers.1. Only two n-digit automorphic numbers exist for each value of n
2. Such numbers form two series in which successive members differ from their predecessors only in the leading digit.
The first 8 members are shown for example below
| Series 1 | 5 | 25 | 625 | 0625 | 90625 | 890625 | 2890625 | 12890625 |
| Series 2 | 6 | 76 | 376 | 9376 | 09376 | 109376 | 7109376 | 87109376 |
| Total | 11 | 101 | 1001 | 10001 | 100001 | 1000001 | 10000001 | 100000001 |
Theorem 3 allows the calculation of the leading digit of the next automorphic number in the series. If for example p=625 then A*1249+390=10k implies A=0 giving 0625 as the next automorphic number in the sequence. If p=0625 then A*1249+39=10k gives A=9 making the next automorphic number in the sequence 90625.
Theorem 4 provides a simple alternative method for the calculation of the next leading digit in automorphic numbers terminating in the digit 6. If p=376 then p^2=141376 and m, the coefficient of 10^3 is equal to 1. Therefore A=10-1=9 giving 9376 as the 4 digit number.If p=9376 then p^2=87909376 and m the coefficient of 10^4 is equal to zero. Therefore A=10-0=10 giving 09376 as the 5-digit number. If p=625 then p^2=390625 and m, the coefficient of 10^3 is equal to zero giving 0625 as the 4-digit number.The same procedure gives 90625 as the 5-digit number in the sequence.
The programme listing for this procedure is shown in Appendix 2 [5]. Using this procedure, the series of automorphic numbers up to 20,000 digits in length was generated in a run time of 54 minutes. Repetition of the procedure using an AST 486DX running at 50Mhz generated automorphic numbers of up to 32,000 digits in length in a run time of 75 minutes. As a point of interest it may be noted that the leading ten digits and the trailing ten digits of the two 32,000-digit automorphic numbers are as follows:
6351634399..............................................................................8212890625
3648365600..............................................................................1787109376
Appendix 3 lists all the n-automorphic numbers to base b where b=2 to 10 and n=1 to b-1 [6]. The following points may be noted:
1. No base 2 automorphic numbers are apparent.
2. It is conjectured that an (n+1)-automorphic number to the base (n+2) is of the form:
.......nnn(n+1). For the cases n=5, b=6 and n=9, b=10 there are two accompanying numbers while single numbers only occur for all the other cases.
[1] http://www.google.com/patents/US4877732
http://www.google.com/patents/US3636037
http://www.google.com/patents/US4249015
http://www.google.com/patents/US3701779
and others...................
[2] Note the timings given in this paper were from the initial work carried out approximately 20 years ago, and obviously would be very different if repeated these days.
[3] Unfortunately this appendix has been lost, if I find it I will add it here later for the sake of completeness.
[4] I have just run a very simple python script and using a brute force method it generated the first 16 in 128.222 seconds!
[5] Again this programme listing was not found, sparing people from seeing my lack of coding skills from 20 years ago!!
[6] The loss of this appendix is a great shame as this gives some interesting information. I will try to recreate this data at some time.
No comments:
Post a Comment