Automorphic Bases

Number Theory Level 4

An automorphic number is a number whose square ends in the same digits as the number itself. For example, the number 25 is an automorphic number (in base 10) because its square, 6 25 , ends with the original number.

For the first 100 positive integers, five numbers are automorphic numbers for base 10 (1, 5, 6, 25, and 76), while only one number is automorphic for base 2 (1).

Which of the following bases has the most automorphic numbers for the first 100 positive integers?

10 7 6 12 15

2 solutions

A Former Brilliant Member
Apr 19, 2019

Here are the lists of *automorphic bases" for the first one hundred (decimal) positive integers for bases from 2 to 100, selected for the list not being just {1}, sorted first by length of the list descending and then by base value for equal length lists. This was done by direct computation, in a single line of code.

$\text{SortBy}\left[\text{Select}\left[\text{Table}\left[\left\{\text{base},\text{Table}\left[n=\text{IntegerDigits}[i,\text{base}];\text{If}\left[n=\text{Take}\left[\text{IntegerDigits}\left[i^2,\text{base}\right],-\text{Length}[n]\right],i,\text{Nothing}\right],\{i,100\}\right]\right\}, \\ \{\text{base},2,100\}\right],\text{\$\#\$1}[[2]]\neq \{1\}\&\right],\{-\text{Length}[\text{\$\#\$1}[[2]]]\&,\text{\$\#\$1}[[1]]\&\}\right] \Rightarrow \\ \left( \begin{array}{rl} 30 & \{1,6,10,15,16,21,25,100\} \\ 42 & \{1,7,15,21,22,28,36\} \\ 60 & \{1,16,21,25,36,40,45\} \\ 66 & \{1,12,22,33,34,45,55\} \\ 70 & \{1,15,21,35,36,50,56\} \\ 78 & \{1,13,27,39,40,52,66\} \\ 84 & \{1,21,28,36,49,57,64\} \\ 90 & \{1,10,36,45,46,55,81\} \\ 6 & \{1,3,4,9,28,81\} \\ 10 & \{1,5,6,25,76\} \\ 12 & \{1,4,9,64,81\} \\ 14 & \{1,7,8,49\} \\ 15 & \{1,6,10,100\} \\ 18 & \{1,9,10,81\} \\ 21 & \{1,7,15,99\} \\ 24 & \{1,9,16,64\} \\ 28 & \{1,8,21,49\} \\ 35 & \{1,15,21,50\} \\ 36 & \{1,9,28,81\} \\ 20 & \{1,5,16\} \\ 22 & \{1,11,12\} \\ 26 & \{1,13,14\} \\ 33 & \{1,12,22\} \\ 34 & \{1,17,18\} \\ 38 & \{1,19,20\} \\ 39 & \{1,13,27\} \\ 40 & \{1,16,25\} \\ 44 & \{1,12,33\} \\ 45 & \{1,10,36\} \\ 46 & \{1,23,24\} \\ 48 & \{1,16,33\} \\ 50 & \{1,25,26\} \\ 51 & \{1,18,34\} \\ 52 & \{1,13,40\} \\ 54 & \{1,27,28\} \\ 55 & \{1,11,45\} \\ 56 & \{1,8,49\} \\ 57 & \{1,19,39\} \\ 58 & \{1,29,30\} \\ 62 & \{1,31,32\} \\ 63 & \{1,28,36\} \\ 65 & \{1,26,40\} \\ 68 & \{1,17,52\} \\ 69 & \{1,24,46\} \\ 72 & \{1,9,64\} \\ 74 & \{1,37,38\} \\ 75 & \{1,25,51\} \\ 76 & \{1,20,57\} \\ 77 & \{1,22,56\} \\ 80 & \{1,16,65\} \\ 82 & \{1,41,42\} \\ 85 & \{1,35,51\} \\ 86 & \{1,43,44\} \\ 87 & \{1,30,58\} \\ 88 & \{1,33,56\} \\ 91 & \{1,14,78\} \\ 92 & \{1,24,69\} \\ 93 & \{1,31,63\} \\ 94 & \{1,47,48\} \\ 95 & \{1,20,76\} \\ 96 & \{1,33,64\} \\ 98 & \{1,49,50\} \\ 99 & \{1,45,55\} \\ 100 & \{1,25,76\} \\ \end{array} \right)$

Wow, nice work!

David Vreken - 2 years, 1 month ago

Eric Nordstrom
Apr 27, 2019

The following code first defines a function to represent any number in any base, provided the base is less than 37. Another function is defined to test whether a number is automorphic in a given base. Finally, the first 100 positive integers are tested for automorphism in each base, and the automorphic numbers and their squares are displayed both in base 10 and the tested base. The result of the code is displayed at the bottom.

def rep(n, base=10):  # represent the number in the given base as a string
    # The number of digits will depend on the highest power of the base that is not greater than n. The resulting exponent can be seen as the order of a polynomial equal to n, which is in terms of the base, and in which the coefficients are the digits of the number in that base.

    # find the order of the polynomial
    order = 0
    power_of_base =  1
    while power_of_base <= n:
        power_of_base *= base
        order += 1
    order -= 1
    power_of_base //= base

    # find each digit as represented in the given base
    s = ''
    remainder = n
    for exponent in range(order, -1, -1):  # starting from the maximum power (order) and working our way down to the "ones" place (0th power)
        digit = remainder // power_of_base
        if digit > 9:
            digit = chr(87 + digit)  # The digit should not, itself, have two digits, so we use letters a-z for digits greater than 9. For example, if, at first, digit = 10 (a two-digit number), it should be changed to chr(87+10)=chr(97)="a".
        s += str(digit)
        remainder %= power_of_base
        power_of_base //= base

    return s

def is_automorphic(n, base=10):  # whether n is automorphic in the given base
    rep_n = rep(n, base)
    return rep(n ** 2, base)[-len(rep_n):] == rep_n

bases = (6, 7, 10, 12, 15)

for base in bases:
    # find automorphic numbers in each base and store (1) the number in base 10, (2) the number in the given base, (3) the square of the number, and (4) the square of the number in the given base
    auto = []  # list of automorphic numbers in the base
    for n in range(1, 101):  # first 100 positive integers
        if is_automorphic(n, base):
            auto.append(f'{n} ({rep(n, base)}) --> {n ** 2} ({rep(n ** 2, base)})')  # n (n in base) --> n^2 (n^2 in base)
    print(f'Base {base} (total = {len(auto)}): {", ".join(auto)}')

Base 6 (total = 6): 1 (1) --> 1 (1), 3 (3) --> 9 (13), 4 (4) --> 16 (24), 9 (13) --> 81 (213), 28 (44) --> 784 (3344), 81 (213) --> 6561 (50213)
Base 7 (total = 1): 1 (1) --> 1 (1)
Base 10 (total = 5): 1 (1) --> 1 (1), 5 (5) --> 25 (25), 6 (6) --> 36 (36), 25 (25) --> 625 (625), 76 (76) --> 5776 (5776)
Base 12 (total = 5): 1 (1) --> 1 (1), 4 (4) --> 16 (14), 9 (9) --> 81 (69), 64 (54) --> 4096 (2454), 81 (69) --> 6561 (3969)
Base 15 (total = 4): 1 (1) --> 1 (1), 6 (6) --> 36 (26), 10 (a) --> 100 (6a), 100 (6a) --> 10000 (2e6a)

Nice solution! I wonder if I should change the topic of this question to "Computer Science"

David Vreken - 2 years, 1 month ago

That might make sense, but I feel like there is some discussion that could be had on it regarding number theory. I was intending to come back to this and add more ways of looking at it. But honestly even those are mostly in the realm of computer science. I haven't figured out anything purely mathematical that reduces the amount of work to solve the problem, but I am curious to know if there is anything.

Eric Nordstrom - 2 years, 1 month ago

So yes, it looks like there was a lot of computer science involved, but there was some number theory as well. Ultimately, I think it's number theory, because any improvements to the process come from number theory. I might even say it's reasonable to do it by hand once you really whittle it down.

Eric Nordstrom - 2 years, 1 month ago

I found another way to test for automorphism. For some reason I doubted that I had it right at first, thinking there were many exceptions, so I didn't post it, but it turns out it's pretty straightforward. It still involves figuring out some properties of the number represented in the tested base, so it's not actually that much easier, and you still have to test for each for the same quantity of numbers.

The test is simply that $n^2-n$ be divisible by $b^k$ , where $b$ is the base and $k$ is the number of digits in $n$ when represented in base $b$ . If this is true, then the $n$ is automorphic; the same is true for the converse. The proof is simply that if $n^2-n$ is divisible by $b^k$ , then $n^2$ mod $b^k$ is $n$ ; since $b^k$ in base $b$ is simply $100\cdots0$ with $k$ zeros, this removes from $n^2$ (base $b$ ) all digits preceding the last $k$ , and thus the last $k$ digits of $n^2$ (base $b$ ) are the same as those of $n$ .

The tricky part is just figuring out $k$ , but this is simpler than completely representing numbers in the given base. So the new code could be written as below. This method reduces lines of code and computation time (although, as written, this is not an apples-to-apples comparison because I have also simplifies the output):

def ndigits(n, base=10):  # This is k.
    # The number of digits is simply 1 plus the order of the polynomial described in the previous code.
    exponent = 0
    power_of_base =  1
    while power_of_base <= n:
        power_of_base *= base
        exponent += 1
    return exponent

def is_automorphic(n, base=10):  # whether n is automorphic in the given base
    return n * (n - 1) % base ** ndigits(n, base) == 0

bases = (6, 7, 10, 12, 15)

for base in bases:
    # find automorphic numbers in each base
    auto = []  # list of automorphic numbers in the base
    for n in range(1, 101):  # first 100 positive integers
        if is_automorphic(n, base):
            auto.append(str(n))
    print(f'Base {base} (total = {len(auto)}): {", ".join(auto)}')

Base 6 (total = 6): 1, 3, 4, 9, 28, 81
Base 7 (total = 1): 1
Base 10 (total = 5): 1, 5, 6, 25, 76
Base 12 (total = 5): 1, 4, 9, 64, 81
Base 15 (total = 4): 1, 6, 10, 100

Eric Nordstrom - 2 years, 1 month ago

Wow, very nice!

David Vreken - 2 years, 1 month ago

Another way to reduce computation time is by eliminating numbers that can't be automorphic as you go. There are two examples I found:

Any whole-number power of the base cannot be automorphic in that base because it will appear as a 1 followed by zeros and its square will appear as a 1 followed by more zeros.
Numbers that end in a number previously found not to be automorphic. For example, since 4 isn't automorphic in base 10, 14 can't be, either, because its square must end with the same ( $k=$ )1 digit as the square of 4. (That is, both $4^2=16$ and $14^2=196$ end in $6$ .)

This is basically dynamic programming (#2), plus a little extra speed (#1). An interesting thing here is that now we have to keep track of the number of digits for two reasons:

to perform the test of automorphism
to determine whether to perform the test of automorphism

With all these changes, it is easiest to combine everything into a single set of nested loops; there is no need to define functions like before.

We also might as well automatically start with "1" in each list of automorphic numbers since 1 will be automorphic in all bases (but this improvement doesn't scale). Finally, we modify the code as follows, which gives the same output as before but faster:

bases = (6, 7, 10, 12, 15)

for base in bases:
    # find automorphic numbers in each base
    auto = [[1]]  # list of lists of automorphic numbers, separated by number of digits
    ndigits = 1
    n = 2
    while n < 101:  # <while> loop now because we want to skip some of the numbers
        if n == base ** ndigits:
            ndigits += 1
            n += 1  # skip any powers of the base since none of these will be automorphic
            auto.append([])
        if (len(auto) == 1 or n % base ** (ndigits - 1) in auto[-2]) and n * (n - 1) % base ** ndigits == 0:  # test for automorphism ONLY if we are still in the single digits OR the last (k-1) digits are a number previously found to be automorphic
            auto[-1].append(n)
        n += 1

    # reformat into single list and change to strings, then produce output
    reformat_auto = []
    for sublist in auto:
        for item in sublist:
            reformat_auto.append(str(item))
    print(f'Base {base} (total = {len(reformat_auto)}): {", ".join(reformat_auto)}')

Eric Nordstrom - 2 years, 1 month ago

Automorphic Bases

2 solutions

0 pending reports