In our lab, we like to tease each other with fancy riddles. In our kitchen, we have a large wooden box, filled with some chocolates and locked by a 4-digits lock (Fig. 1). Those who crave for some sugar will just need to solve the riddle and unlock the box.

The last few riddles involved a particular family of numbers which are called automorphic, and the complexity of such riddles was increasing with the size of those numbers in terms of the number of digits. For instance, in the last riddle, we were asked to compute a number with 44444 digits, requiring an enormous computational power.

Here, I will show some properties of automorphic numbers as well as some insights that allowed me to develop a rather efficient algorithm for cutting down the computational complexity of the problem. In particular, I will initially describe three recent riddles and how the first two were solved. Then, I will drive you through the definition of automorphic number and some of their properties. Lastly, I will show how I developed the algorithm to solve the third riddle.

Riddles

It all started a few weeks ago, with a simple riddle (Riddle #1):

“there is one four-digit whole number n, where the last four digits of n²=n”

Before I could even put my hands on this riddle, the solution was already spreading in the lab. It was 9376, because it is the only number which squared contains itself: 9376² = 87909376.

To find this solution, some people relied on their math knowledge: only numbers ending with 0, 1, 5 and 6, end with the same digit if squared. This allowed them to cut down the solution space. Some others relied on the brute force approach. It is pretty quick to square 10000 numbers (actually 9000 as the first 1000 have only 3 digits) and see if they are contained in their squared.

 

From there, it escalated quickly (see Fig 2).

There was a new riddle (Riddle #2):

“there is one 20-digit whole number n, where the last 20 digits of n²=n. The first 4 digits open the box”

Using the brute force would have solved the riddle as there a finite number of solutions, but it was claimed it would have required

“2852 years (assuming testing one 20-digit number takes 1 nanosecond). If you want the answer within an hour, you’d need 25 million PCs and a 1.21 Jiggawatts power supply.”

If brute force is not the way, there must be something else that allows retrieving this number. This challenge captivated me. However, this needed me to go back to Math books as certainly there was a property for this kind of numbers which I was not aware of.

I started googling. I soon discovered that such numbers are called automorphic. I found that, for a given number of digits, there are only two automorphic numbers, one ending in 5 and one in 6 (except that the 1-digit automorphic numbers which include 0 and 1). In the next section, I will describe this kind of numbers more in detail.

Then, I also found a list of pre-computed automorphic numbers (archived version). This list contained all automorphic numbers ending with both 5 and 6 up to 100 digits. For 20 digits, there is only one number, which ends with 5: 92256259918212890625.

92256259918212890625² = 8511217494096854352392256259918212890625

Then, the first 4 digits (9225) opened the lock. Eventually, I did not have to waste the power of 25 million PCs, when I could simply rely on a larger network of PCs with superior knowledge: the Internet.

This time it escalated exponentially. There was again a new riddle (Riddle #3):

“How many k ∈ {1,2,…,44444} are there such that there is exactly one k-digit whole number n, where the last k digits of n²=n?”

Allow me to rephrase it and make it clearer. Given a finite set of digits, from 1 to 44444, for how many digits we have only one automorphic number? In the two previous riddles, we saw that for 4 and 20-digits, there is only one automorphic number. However, 4 and 20 are not the only ones. In the table below, we can see that for 4, 5, 12, 13 and 20 there is one k-digit automorphic number (see Table 1). From 1 to 100 digits 33 digits have only one automorphic number. Instead, from 1 to 1000, we can find 216. Then, how many from 1 to 44444?

 

Table 1. List of automorphic numbers for a given digit.

Digits	Automorphic numbers	Quantity
1	0, 1, 5, 6	4
2	25, 76	2
3	376, 625	2
4	9376	1
5	90625	1
6	109376, 890625	2
7	2890625, 7109376	2
…	…	…
12	918212890625	1
13	9918212890625	1
…	…	…
20	92256259918212890625	1

 

This time, there was no list. Those numbers need to be computed.

In the next section, I will show some insights and strategies that allowed me to cut down the computational complexity of the problem and therefore solve this third riddle.

 

What is an Automorphic Number?

An n-digit number is said to be automorphic if the last n digits of its square are the same as the original number. For instance, 5² = 25, 6² = 36, 25² = 625, 76² = 5776 and many others.

There are infinite automorphic numbers and we can find them also with a large number of digits, such as 18212890625² = 331709384918212890625 or 81787109376² = 6689131260081787109376.

In particular, we can find four 1-digit automorphic numbers, two trivial numbers: 0² = 0, and 1² = 1, and two nontrivial numbers: 5² = 25, and 6² = 36. However, for numbers with more than one digit (n > 1), there are at most two automorphic numbers, meaning that from 10 to 99 there are only two automorphic numbers: 25 and 76. Also from 100 to 999, there are only two automorphic numbers: 376 and 625. However, from 1000 to 9999 we can find only 9376.

 

Properties of Automorphic Numbers

In this section, I will show some characteristics for automorphic numbers and then I will make a few considerations on how those particular properties can be exploited to cut down the complexity of the problem.

 

Nine’s complement

The first property of these automorphic numbers jumping to the eye is their nine’s complement, for all digits except the last. The nine’s complement of a given number is formed by replacing each digit with nine minus that digit. In Fig. 3, below you can observe the two 30-digits automorphic numbers. For each digit, except the last (in the red rectangle), they are complementing each other (see green rectangles): 3->6, 5->4, 2->7, 1->8, and 9->0.

Considering this complementarity, we just need to compute the sequence of numbers that end with 5. The sequence of 6, will be generated by subtracting each digit from 9 and replacing the last digit with 6.

 

Formula

There is a formula that allows to compute the two numbers:

\(\begin{aligned}
a u t_{5}^{n} &=5^{2^{n}} \bmod 10^{n} \\
a u t_{6}^{n} &=10^{n}-a u t_{5}^{n}+1
\end{aligned}\)

In particular, to get the automorphic number ending with 5 hiving n digits (\(a u t_{5}^{n}\)), is the remainder when computing 5 to the power of 2ⁿ divided by 10ⁿ. Because these numbers are complemented, the automorphic number ending with 6 and having n digits (\(a u t_{6}^{n}\)) is computed by subtracting the first (\(a u t_{5}^{n}\)) from 10ⁿ+1.

In Python, we can use these formulas within in a for-loop to retrieve the list of automorphic numbers up to 20 digits:

limit = 20
for i in range(2, limit):
    a = 5**(2**i) % 10**i
    b = 10**i - a + 1
    print("5:",a)
    print("6:",b)

However, this python code works up until a certain number of digits, as there is a limit on the number of digits an integer can be represented in Python.

Nonetheless, this tells us that to identify automorphic numbers we can simply apply such formulas without the need of using brute force.

You can read more info from here.

 

Extension

Another interesting property for the automorphic numbers is that they extend themselves including the number with fewer digits. Specifically, each n-digit automorphic number contains the previous number (n-1 digits) with a digit prepended. As you can see from Fig. 4 the automorphic number of 9 digits contains the automorphic number of 8 digits and prepends the digit 2: 212890625.

Similar for the automorphic number of 10 digits, which contains one of 9 digits and prepends an 8: 8212890625. This pattern is valid for any n-digit automorphic number, as shown in Fig. 4.

 

This characteristic of the automorphic numbers is telling us that we can potentially start from a seed number (let’s say 12890625 as in the example below), and iteratively prepending one digit from 0 to 9, to find which of them produces a squared number which includes itself, as shown in Table 2.

 

Table 2. Examples when prepending a digit to the current automorphic number.

Prepending to 12890625	Squared
0128906252	166168212890625	–
1128906252	12744293212890625	–
2128906252	45322418212890625	OK
3128906252	97900543212890625	–
4128906252	170478668212890625	–
5128906252	263056793212890625	–
6128906252	375634918212890625	–
7128906252	508213043212890625	–
8128906252	660791168212890625	–
9128906252	833369293212890625	–

 

Autogeneration

Automorphic numbers of the sequence of 5 generate automatically. In particular, the sequence of 5 grows by iteratively squaring automorphic numbers having n digits and keeping the digit at position n+1.

In the picture below, we can observe that to generate the automorphic sequence of 5, we can start from squaring 5 (1 digit), and then we keep the value at the second digit, generating 25. Then, we can process 25 which has 2 digits and we keep the 3^rd digits of its squared, generating 625. Again, we process 625 and we keep the fourth digit of its squared, generating 0625. This is a special case, the value 0 is because there is no 4-digit automorphic number in the sequence of 5. Then again, we re-square 625, and we take the 5^th digit of its squared, generating 90625, and so forth. This process is exemplified in Fig. 5.

In this case, one can save computational time by squaring the n-digit number and stopping when the digit n+1 is computed, as it will feature the consecutive automorphic number is such sequence.

Unfortunately, this property is not true for the sequence of 6, as 6² = 36 rather than 76.

You can read more info from here.

 

Solving the Riddle

At this stage, we know the riddle and we have gone through some characteristics of automorphic numbers. The question on how to solve the riddle remains.

Because of the extension property, the first consideration to make is that potentially we do not need to compute all numbers for the whole sets of digits {1,2,…,44444}. The 44444-digits number will contain the nested sequence of its previous 44443 solution numbers. And whenever, the sequence does not have a solution for a given digit, it will contain a 0, like for instance at the fourth digit 890625. In this case, if we manage to compute this large number with 44444 digits and we count the number of zeros, we will know how many times the sequence of 5 did not produce a solution: therefore, there was exactly one solution. However, this is not enough, because we need to know also the number of times the sequence of 6 contains a 0. In this case, the nine’s complement comes handy. Thanks to this property we know that all digits (except the last) complement each other. Therefore, if we know the 5-sequence of 44444 digits, we will just need to count both zeros and nines, meaning that they will be zeros in the 44444-digits automorphic number of sequence 6.

So now, the question comes down to: how do we compute the 44444-digit automorphic number of sequence 5?

We can definitely use the brute force approach: try out all numbers from 10⁴⁴⁴⁴³ to 10⁴⁴⁴⁴⁴, square them and find the one which is automorphic. I am not sure about the number of machines one needs to use to compute this number in a reasonable time.

To cut down the number of tests, we can rely on the formula:

\(a u t_{5}^{44444}=5^{2^{44444}} \bmod 10^{44444}\)

However, computing \(5^{2^{44444}}\) is extremely challenging too.

At this stage, we might take advantage of the extension property. We can start from 5, and we can iteratively test all possible solutions when prepending one digit at a time, e.g.: 05, 15, 25, 35, 45, 55, 65, 75, 85, 95. After we find which of these 10 numbers is automorphic, we proceed with the 3^rd digit and so on until 44444 digits. This strategy reduces our domain to at most 444440 tests.

However, the autogeneration property allows to further cut down the number of tests. We just need to start from 5, as seed number, and then we repeatedly square this number to identify the n+1 digit. This strategy will then allow us to test only 44444 numbers.

 

Algorithms

It is clear from the discussion above that the algorithm to solve the riddle need to perform several squares, or more in general multiplications. Considering that we are treating very long numbers, we cannot pretend to use normal data types and operators. The algorithm needs to be customised to the problem: our numbers will be represented by arrays (which length is limited by the size of the memory) and we need to develop the algorithm performing the multiplication of such arrays from scratch.

In this section, I will drive you through the different versions of the algorithms that allowed me to cut down the computational complexity of the problem from days to seconds. In order to have a fair comparison of the performance of those algorithms, I will show the amount of time it took them to compute the first 1000 digits on the same machine.

 

Multiplication

The initial version of the algorithm was a very basic multiplication between strings. This algorithm implements the simple grade-school multiplication, like in the example in Fig. 6.

In this particular case, the algorithm is computing the squared of a 6-digits automorphic number 890625, with the aim of generating the 7^th digit, which is 2 (green box).

In brief, this algorithm consists of finding a new digit each iteration. It squares the input number (of length n) and it takes the n+1 digit, it then prepends this digit to the current number, for the next iteration. The computation of the square is performed by multiplying the number by itself. Specifically, this consists of two for loops, implementing the grade-school multiplication.

Here is a small snippet in Python:

 
def square(number): 
    num_length = len(number) 
    
    # variable hosting the result
    result = [0] * (num_length*2)
    # two indexes used to find positions in result
    index1 = 0
    index2 = 0
  
    # iterating in reverse order
    for i in range(num_length - 1, -1, -1): 
        carry = 0
        n1 = number[i]
  
        # for shift position each iteration
        index2 = 0
  
        # iterating in reverse order
        for j in range(num_length - 1, -1, -1): 
             
            n2 = number[j]
          
            # multiply the two digits and sum their result 
            # with the previous carry and the current value in result
            summ = n1 * n2 + result[index1 + index2] + carry 
  
            # computing the next carry
            carry = summ // 10
  
            # Store its modulo in result 
            result[index1 + index2] = summ % 10
  
            index2 += 1
  
            # hold carry for next iteration
        if (carry > 0): 
            result[index1 + index2] += carry 
  
        index1 += 1
  
    # returning the inverted array
    return result[::-1]

The full code of this algorithm is available at https://github.com/angelosalatino/computing-automorphic-numbers/blob/master/square.py

The computational complexity of this algorithm is O(N²) and to compute the first 1000 digits took 71 seconds. Since the complexity is strongly dependent on the squared number of digits (N²), every new iteration would add a new digit and therefore require more time to be computed. I estimated that to compute the 44444-digit automorphic number would have requires at least one week.

 

Partial multiplication

We might argue that since we are looking for the n+1 digit, we can simply stop the computation of the squared number once this particular value has been identified. Specifically, we should avoid computing all n+k digits where k > 1 (red box in Fig. 7) as they are purposeless. And perhaps, we might also avoid performing all multiplications of single digits (orange box).

This can be achieved, by avoiding multiplying all digits which their added-up position is higher than the position of the digit we are interested: n+1. For instance, looking at Fig. 8, if we multiply the value at position 4 (first row, orange box) with the value at position 3 (second row, blue box), their added-up position makes 7, which is greater than 6.

In brief, also this algorithm generates a new digit each iteration. It partially squares the input number (of length n) up until the n+1 digit, which will then be prepended to the current number, for the next iteration. The implementation of the partial square is similar to the grade-school multiplication, but it has a stop criteria.

The full code of this algorithm is available at https://github.com/angelosalatino/computing-automorphic-numbers/blob/master/partial-square.py

The computational complexity of this algorithm is O(\(\sqrt{2}\)N) and to compute the first 1000 digits took 43 seconds.

 

Ultimate partial multiplication

At this stage, we have a better understanding of automorphic numbers that we couldn’t help but notice of another way to simplify the complexity of the problem.

If we pay particular attention to the multiplication process in the figure above, because of the principal characteristic of the automorphic numbers: the last n digits of its square are the same of the original number; we can definitely state that:

\(z_{i}=x_{i} \quad \forall i \leq n\)

Can we just compute the value \(z_{n+1}\) without re-computing \(z_{i}, ~\forall i \leq n\)?

It is indeed possible since we are generating those number iteratively, we can “carry” enough information from one iteration to the next so that we can compute only the \(z_{n+1}\) digit.

To better understand the process, allow me to take advantage of the picture below (Fig. 9).

Let’s assume we just found x₅ at the previous iteration, and at this iteration, instead, we want to identify the digit x₆. To achieve this, we firstly need to compute z₆, and then we will take its modulo 10 (i.e. the last digit of z₆, e.g. 22 -> 2)

The equation to compute z₆ is:

\(\begin{aligned} z_{6} =\color{blue} {\left(t_{15}+t_{24}+t_{33}+t_{42}+t_{51}\right)  \text { mod } 10}+\color{orange} {\left\lfloor\frac{t_{05}+t_{50}}{10}\right\rfloor}+\color{green} {\left\lfloor\frac{t_{14}+t_{23}+t_{23}+t_{14}}{10}\right\rfloor} \\
+\color{red} {\left\lfloor\frac{\left(t_{14} m o d 10+t_{23} \bmod 10+t_{32} \bmod 10+t_{41} \bmod 10\right)}{10}\right\rfloor}
\end{aligned}\)

\( x_6 = z_6~ mod10 \\ z_5^{‘} = z_5 – x_5 \\ \text {where } t_{i j}=x_{i} \cdot x_{j}, \text { and } t_{i j}=t_{j i} \)

This equation consists of four components, which colours match with the boxes in the figure above. The first component \(\left(t_{15}+t_{24}+t_{33}+t_{42}+t_{51}\right) \bmod 10\) (in blue) allows to compute the columns that produces the \(z_6\) value (\(x_6\) digit). However, this is not enough, as we need to consider few other components, coming from the column of the previous digit (\(x_5\)). These values affect the column of  through their “carry” value, this is why each of these components firstly are divided by 10 and then we take its integral part (i.e. floor value), using the symbol \(\lfloor~\rfloor\). In particular, the second component \(\left\lfloor\left(t_{05}+t_{50}\right) / 10\right\rfloor\) (in orange) considers the effect of the newly added digit (\(x_5\)) in the prior column. Since \(x_5\) has just been discovered, it was not part of the of the previous iteration. Considering that we are computing \(z_6\), the value of \(x_5\) will not change at this stage, the new value of \(x_{5}=\left(t_{05}+t_{50}\right) \bmod 10+x_{5}\), and therefore \(t_{05}\) can be either 0 or 5.

The third component \(\left\lfloor\left(t_{14}+t_{23}+t_{23}+t_{14}\right) / 10\right\rfloor\) (in green) is the carry from the previous iteration. This is the sum of the carries of each single component\(t_{ij}\). All these multiplications have already been computed at the previous iteration and therefore we just need to transfer this carry value from one iteration to the next.

The last component, also known as, \(z_5^{‘} \) (in red) is the carry of \(z_5\). \(z_5\) and, in general, any \(z_i\) is split into two parts: i) its modulo 10 that will become the \(x_i\) digit, and ii) the remainder that will be carried to the next iteration. This carry consists of summing all last digits of  \(t_{ij}\) (modulo 10) in column \(x_5\), then divided by ten and taken the integral part.

The whole equation for computing z₆ and, in general, any z_i can be generalised with the following:

\(\begin{aligned}
&z_{n+1}=\color{blue} {\left(\sum_{i=1}^{n}\left(x_{i} \cdot x_{n-i}\right)\right) \bmod 10}+\color{orange} {\left\lfloor\left(x_{0} \cdot x_{n}\right) / 5\right\rfloor}+\operatorname{carry}_{n}\\
&\operatorname{carry}_{n+1}=\color{green} {\left\lfloor\sum_{i=1}^{n}\left(x_{i} \cdot x_{n-i}\right) / 10\right\rfloor}+\color{red} {\left\lfloor z_{n+1} / 10\right\rfloor}\\
&x_{n+1}=z_{n+1} \bmod 10
\end{aligned}\)

There is only one exception to this equation, which is when computing the value \(x_1\). From Fig. 9 we can see that \(t_{00}\) appears only once, therefore the second component (in orange), will be just \(\left\lfloor t_{00} / 10\right\rfloor\). In this case \(carry_0 = 0\).

The full code of this algorithm is available at https://github.com/angelosalatino/computing-automorphic-numbers/blob/master/ultimate-partial-square.py

The computational complexity of this algorithm is O(N) and to compute the first 1000 digits took 0.06 seconds. The whole 44444-digit automorphic number was computed in 162 seconds.

You can download the 44444-digits automorphic numbers from here:

 

Algebraic Solution

Professor Stefan Rueger, who set the previous riddles, pushed to the limit the approach I developed above by further increasing its complexity. The riddle stayed the same, but the number of digits increased to 10¹⁰. This means that given a finite set of digits, from 1 to 10¹⁰, we need to count the number of times we have only one solution for a fixed number of digits. With the same rationale explained above we just needed to compute a 10-billion-digit number, and count the number of 0s and 9s. Unfortunately, the solution designed above did not scale enough to compute this number in a manageable time. Even its implementation in C++, which revealed to be 100x faster (the 44444 automorphic number was indeed computed in 1.66 seconds), did not produce satisfactory results. After 2 weeks it managed to compute only 15 million digits. This is because even if the complexity is down to O(N) per iteration, to every new iteration we add a new digit which leads to an increase of the computational time.

Later, in a meeting with Stefan, he showed me his notes on how to tackle the problem from a different angle: algebra.

I will attempt here to explain the math behind his notes, using a simple running example, and then I will generalise it to any value of digits. In this particular case, I will try to identify the automorphic number with 4 digits.

This exercise is then equivalent to find a number n in {1000, 1001, …, 9999} such that:

\(n^{2} = n~(mod~10000)\)

We can factorise this equation as:

\(n(n-1) = 0~(mod~10000)\)

The trivial solutions are 0 and 1, but they are not in the range set {1000, 1001, …, 9999}. To find the solution n, we are going to take advantage of certain properties of the modulo, including the Chinese Remainder Theorem.

First, the 10000 we are using as modulo, can be factored into prime powers \(2^{4} \cdot 5^{4}= 16 \cdot 625\).

According to the Chinese Remainder Theorem:

For any a, b and coprime m, n, there exists a unique x (mod mn) such that x ≡ a (mod m) and x ≡ b (mod n)

we can rewrite the above equation which need to simultaneously hold:

\(n^2 = n~(mod~16)~~~and~~~n^2= n~(mod~625)\)

which can be rewritten as:

\(n(n-1) = 0~(mod~16)~~~and~~~n(n-1) = 0~(mod~625)\)

The value of n that simultaneously satisfy the above equation is either:

\(\textbf{(1a)}~~ n = 0~(mod~16)~~~and~~~\textbf{(1b)} ~~ n = 1~(mod~625)\)

or:

\(\textbf{(2a)} ~~ n = 1~(mod~16)~~~and~~~\textbf{(2b)} ~~ n = 0~(mod~625)\)

or:

\(\textbf{(3a)} ~~ n = 0~(mod~16)~~~and~~~\textbf{(3b)} ~~ n = 0~(mod~625)\)

or:

\(\textbf{(4a)} ~~ n = 1~(mod~16)~~~and~~~\textbf{(4b)} ~~ n = 1~(mod~625)\)

We can observe that Eq. 3a and 3b correspond to the case of a=b=0, and Eq. 4a and 4b correspond to the case of a=b=1, which lead to the trivial solution in which n=0 and n=1, respectively.

Instead, let’s concentrate on Eq. 1a and 1b for now and I will explain later what Eq. 2a and 2b are useful for.

Writing \(a = b~(mod~m)\), according to the modulo property, means to say that there exists an integer i such that \(a = b + mi\).

To this end, we can rewrite Eq. 1b as:

\(\textbf{(1c)}~~n = 1 + 625i ~\exists i \in \mathbb{Z}\)

we then can use Eq. 1a to state that:

\(0 = 1 + 625i~(mod~16)\)

and because of the multiplication compatibility property of modulo numbers, and because \(625~(mod~16) = 1\), we can rewrite the previous equation in:

\(0 = 1 + i~(mod~16)\)

solving this for i, creates:

\(i = 15~ (mod~16)\)

which can be rewritten as:

\(i = 15 + 16j~\exists j \in \mathbb{Z}\)

Joining it with Eq. 1c, we obtain:

\(n = 1 + 625(15+16j) = 9376 + 10000j\)

In this case we obtained the 4-digits automorphic number (9376) of the 6 sequence.

Solving Eq. 2a and 2b we can obtain the 5 sequence automorphic number. Indeed, Eq. 2b can be rewritten as:

\(\textbf{(2c)}~~n = 0 + 625i~\exists i \in \mathbb{Z}\)

joining it with Eq. 2a, we obtain:

\(1 = 0 + 625i~(mod~16)\)

As before, since \(625~(mod~16) = 1\), we can rewrite it in:

\(1 =  i~(mod~16)\)

which can be rewritten as:

\(i = 1 + 16j~\exists j \in \mathbb{Z}\)

Joining it with Eq. 2c, we obtain:

\(n = 625(1+16j) = 625 + 10000j\)

The solution obtained here is 625, which is not in the range set {1000, 1001, …, 9999}, because there is no solution for the automorphic number in the 5 sequence for 4 digits. Indeed, according to the fundamental theorem of algebra, a polynomial equation of degree m (in this case 2), has exactly m (here 2) zeros in the field of complex numbers and at most m (again 2) zeros with real coefficients.

In general, if we want to compute the automorphic number of a given number of digits k, the modulo value is basically 10^k, which can always be factored in \(2^{k} \cdot 5^{k}\). Therefore, in all previous equations, each 16 needs to be swapped with 2^k, and each 625 with 5^k.

All these equations can be written in a more compact form like:

\(\begin{array}{l}
{x_{5 \text {seq}}=1+5^{k}\left(2^{k}-\left(5^{k}\right)^{-1} \bmod 2^{k}\right)\left(\bmod 10^{k}\right)} \\
{x_{6 s e q}=1+2^{k}\left(5^{k}-\left(2^{k}\right)^{-1} \bmod 5^{k}\right)\left(\bmod 10^{k}\right)}
\end{array}\)

The advantage of using this algebraic solution compared to the previously designed algorithmic approaches is that we do not need to compute each single digit iteratively. In this solution, we just need to replace k with the number of digits of our desired automorphic number (e.g. 4, 20, 44444, 10¹⁰) and with a limited number of operations, it will generate the number. We will still need to perform multiplication of large numbers (e.g. 10¹⁰-digit numbers), however we can take advantage of some libraries available in the state of the art, like the GMP (The GNU Multiple Precision Arithmetic Library), which can perform large multiplications in O(N logN).

Stefan provided me with his implementation of this algorithm using GMP, and the computation of the 10¹⁰-digits automorphic number took 13138.4 seconds (just over 3h and a half), on the same machine in which I performed the previous tests (specifications below).

Here you can find a more detailed version of Stefan notes.

Limitations

In this article, we kept pushing the boundaries of our knowledge to cope against the limitations set by the methodologies we were using for computing large automorphic numbers. We reached a very good stage in which we can compute 10 billion digits in a matter of a few hours.

However, the question remains: to what extent we can actually push the computation of the automorphic number? Is there a limit in the number of digits we can actually compute?

In this, we foresee two major limitations.

The first is certainly due to the library for computing multiplications of large numbers. GMP currently supports numbers that can fit in 2³⁷ bits of memory (16Gb ca). One might need to rewrite the library to be able to push this further.

The second limitation is due to the RAM memory one has available in his or her own machine. These very long numbers need to be kept in memory, and you don’t want to incur in memory swapping which will further increase the computational time.

 

Conclusions

Solving this riddle turned out to be exciting and challenging at the same time. Many people in the lab got the chance to get acquainted with this kind of numbers and learn their properties.

The initial versions of my algorithms would need several days to complete the computation of such number. The obstinacy in wanting to improve the algorithm so that it could be computed in less time, allowed me to analyse the problem more deeply so that I could design a more efficient algorithm to solve the riddle.

 

Acknowledgements

I would like to thank Prof. Stefan Rueger for setting up the riddles and for the insightful conversations.

 

Material

Code

I published all the code on a Github repo: https://github.com/angelosalatino/computing-automorphic-numbers

Numbers

I uploaded the two 44444-digits automorphic numbers of both sequence 5 and 6 on Zenodo. You can download them from here:

Machine Specifications

Model Name: MacBook Pro
Processor Name: Intel Core i7
Processor Speed: 3.5 GHz
Number of Processors: 1
Total Number of Cores: 2
L2 Cache (per Core): 256 KB
L3 Cache: 4 MB
Hyper-Threading Technology: Enabled
Memory: 16 GB