A Digit-Based Algorithm for Computing Square Roots of Perfect Squares
, , , , , ,
DOI 10.5433/1679-0375.2026.v47.54706
Citation Semin., Ciênc. Exatas Tecnol. 2026, v. 47: e54706
Received: February 27, 2026 Received in revised for: June 3, 2026 Accepted: June 9, 2026 Available online: July 16, 2026
Abstract:
This paper presents a new method for computing square roots of perfect squares, originally devised by two students from Basic Education during their mathematics studies. Motivated by numerical patterns observed in the decimal representation of perfect squares, the method combines classical properties of unit digits with a novel block-based structure derived from arithmetic progressions. These patterns allow the construction of an explicit algorithm that recovers the square root of a perfect square using only elementary operations. The work provides a rigorous mathematical formalization of the method, including proofs of correctness, an analysis of its asymptotic behavior, and a discussion of its computational complexity. Beyond its theoretical interest, the proposed approach highlights the mathematical creativity of young students and illustrates how elementary observations can lead to meaningful mathematical structures, reinforcing connections between school mathematics, undergraduate research, and outreach activities.
Keywords: square root algorithms, perfect squares, digit patterns, arithmetic progressions, asymptotic complexity
Introduction
The square root is among the most iconic functions in the field of mathematics and is presented to students, in one way or another, at the earliest stages of education. However, the definition of square root cannot be taken for granted. The traditional approach is to start with the complete ordered field of the real numbers \(\mathbb{R}\), and establish the intermediate value theorem. Then we consider the function \[\begin{align} f : \mathbb{R}_{\geq 0} &\to \mathbb{R} \notag\\ x &\to f(x) = x^2. \end{align}\]
It can be proven that \(f\) is continuous and increasing, and thus, injective. It follows that for any number \(a \geq 0\) the equation \[\begin{equation} f(x) = a, \end{equation}\] has at most one solution.
The necessity of the intermediate value theorem is to prove the existence of a solution. Since \(a\geq 0\) and therefore \(f(0) \leq a < f(a+1) = a^2 + 2a + 1\), there exists some value \(b \in [0, a + 1)\) such that \(f(b) = a\). This value \(b\) is called the square root of \(a\) and we denote \(b = \sqrt{a}\). The mapping \(\mathbb{R}_{\geq 0} \ni x \to \sqrt{x}\) is called the square root function.
This definition has a pedagogical limitation: it is utterly inaccessible for young students. Besides that, it obfuscates the algebraic properties of the mapping \(x \mapsto x^2\).
In this article we present a new definition of the square root based upon two patterns. This approach also draws on a broader mathematical and pedagogical context. The usual definition of the square root relies on the analytical structure of the real numbers, as presented in standard texts in mathematical analysis(Rudin, 1976), whereas the method developed here is based on elementary properties of integers and decimal representations, in the spirit of classical number theory (Niven et al., 1991). Its formulation as an explicit computational procedure connects the work to the study of seminumerical algorithms and computational complexity (Sipser, 2012; Knuth, 1997). Moreover, the way in which the method emerged from the recognition of numerical patterns reflects the problem-solving approach advocated by Pólya (1945), in which exploration, observation, and generalization play a central role in mathematical discovery.
The proposed definition is grounded on structural features of square numbers, a topic that has received attention in recent literature concerning their properties and detection criteria (Brown, 2021).
The approach developed here differs in that it leads to an explicit algorithmic procedure for root extraction derived directly from decimal digit structure. Alternative procedures for extracting square roots of perfect squares have also appeared in recent publications (Savarimuthu et al., 2023), indicating continued interest in structural and digit-based perspectives on this classical problem. Furthermore, recent investigations into constructive frameworks for integer root extraction (Pareth, 2026) suggest that approaches grounded in explicit arithmetic structure continue to attract research interest.
The motivation for the present work, however, originated from the observation of patterns in the decimal representation of perfect squares by the ninth-grade students Felipe Kenji Iokota and Fabrício Ventura da Silva. The analysis of these structures revealed numerical relationships that led to the formulation of a method for determining square roots using only elementary arithmetic operations, whose mathematical foundation is developed throughout this article.
In September 2024, these observations were presented to the PET Matemática group, initiating the investigation process that ultimately culminated in the algorithm studied in this work. Earlier algorithmic treatments of the problem of identifying perfect squares have also appeared in the literature (Norris, 1974), highlighting the historical development of computational approaches to this classical question.
The first pattern they observed is a well known fact concerning the units digit of a perfect square. That is, if \(n\) is a positive integer, the units digit of \(n^2\) depends on the units digit of \(n\). It is easy to prove, writing \(n= 10k + u\) with \(0 \leq u \leq 9\) being the units digit of \(n\), we have that
\[\begin{align} n^2 &= (10k + u)^2 \notag\\ &= 100k^2 + 20ku + u^2. \end{align}\] So that the units digit of \(n^2\) is the same as that of \(u^2\).
The second pattern, to our knowledge, has not been previously reported in the literature. Consider the sequence obtained by listing the perfect squares in base \(10\) and replacing their units digit by zero. The first values of this sequence are displayed in Table 1.
The second pattern is, to our knowledge, still unpublished. This pattern shows up when one lists the perfect squares, written in base \(10\), and replaces its units digit by zero. Table 1 lists its values up to \(10000\), from which the block structure described below becomes apparent.
| 0 | 0 | 0 | 10 | 20 | 30 | 40 | 60 | 80 | 100 |
| 120 | 140 | 160 | 190 | 220 | 250 | 280 | 320 | 360 | 400 |
| 440 | 480 | 520 | 570 | 620 | 670 | 720 | 780 | 840 | 900 |
| 960 | 1020 | 1080 | 1150 | 1220 | 1290 | 1360 | 1440 | 1520 | 1600 |
| 1680 | 1760 | 1840 | 1930 | 2020 | 2110 | 2200 | 2300 | 2400 | 2500 |
| 2600 | 2700 | 2800 | 2910 | 3020 | 3130 | 3240 | 3360 | 3480 | 3600 |
| 3720 | 3840 | 3960 | 4090 | 4220 | 4350 | 4480 | 4620 | 4760 | 4900 |
| 5040 | 5180 | 5320 | 5470 | 5620 | 5770 | 5920 | 6080 | 6240 | 6400 |
| 6560 | 6720 | 6880 | 7050 | 7220 | 7390 | 7560 | 7740 | 7920 | 8100 |
| 8280 | 8460 | 8640 | 8830 | 9020 | 9210 | 9400 | 9600 | 9800 | 10000 |
| ⋮ |
Notice that, as shown in Table 1, \(10, 20, 30, 40\) are in arithmetic progression with common difference \(10\); we also have that the numbers \(60, 80, 100, 120, 140, 160\) are also in arithmetic progression with common difference \(20\). They are followed by \(190, 220, 250, 280\) in arithmetic progression with common difference \(30\) and so on.
So, if we break up this sequence into infinitely many blocks, with the zeroth having 3 elements, the first with 4, the second with 6, the third with 4, the fourth with 6, and so on, the numbers of each block would be in arithmetic progression with common difference \(10k\). The pattern does hold for all perfect squares, as we prove later in the text. Furthermore, this implies that it is possible to calculate the last element of the \(k\)th block by the formula
\[\begin{equation} \label{rk}\tag{1} r_k = 40 + 2 \cdot 60 + 3 \cdot 40 + \dots + k \cdot [50 + 10(-1)^k]. \end{equation}\]
We can use that to calculate the square root of a perfect square in the following way: if \(m\) is a perfect square, we let \(k\) be the smallest integer such that \(\lfloor m\rfloor_{10} \leq r_k\). In this way \(r_k\) is the last element in the block that \(m\) belongs to. And the square root of the perfect square that becomes \(r_k\) when its units digit is replaced by zero is given by \(3 + 4 + 6 + 4 + \dots + [5 + (-1)^k]\). To find the square root of \(m\) we subtract \(\dfrac{r_k - \lfloor m\rfloor_{10}}{10k}\) from that.
Materials and methods
We begin with some basic notation that will be used throughout the text.
Definition 1. Let \(a,b \in \mathbb{Z}\) and let ⟦\(a, b\)⟧ denote the interval of all integers between \(a\) and \(b\) included, more specifically, ⟦\(a, b\)⟧ = \(\left[a,b \right] \cap \mathbb{Z} = \{a, \dots, b\}\).
Example 1. The interval ⟦\(3,11\)⟧ consists of all integers between \(3\) and \(11\), including both endpoints. Therefore,
\[ ⟦3,11⟧ = \{3,4,5,6,7,8,9,10,11\}. \]
Our next step is to introduce a variant of the floor function. This function “rounds down” a number to the nearest multiple of \(10\) that does not exceed it.
Definition 2. We define \(\lfloor \cdot \rfloor_{10}: \mathbb{R}_{\geq0} \to \mathbb{Z}_{\geq 0}\) by \[\begin{equation} \lfloor x \rfloor_{10} =10 \left\lfloor\frac{x}{10} \right\rfloor, \end{equation}\] for every \(x \in \mathbb{R}_{\geq0}\). Less formally, \(\lfloor x \rfloor_{10}\) is obtained by removing the units digit and any fractional part of \(x\).
Example 2. The following examples illustrate different situations covered by Definition (2): a number whose units digit is removed, a multiple of \(10\) that remains unchanged, and a positive real number smaller than \(10\).
\(\lfloor 42 \rfloor_{10} = 40\);
\(\lfloor 120 \rfloor_{10} = 120\);
\(\lfloor \pi\rfloor_{10} = 0\).
We’ll make use of the following property for \(\lfloor \cdot \rfloor_{10}\).
(prop:floor10)
Proposition 1. For an integer \(n\) and a positive real number \(x\) it follows that \(\lfloor 10n + x \rfloor_{10} = 10n + \lfloor x\rfloor_{10}\).
Proof. Notice that
\[\begin{align} \lfloor 10n + x\rfloor_{10} &= 10\left\lfloor \frac{10n + x}{10} \right\rfloor \notag\\ &= 10\left\lfloor n + \frac{x}{10} \right\rfloor \notag\\ &= 10\left( n + \left\lfloor \frac{x}{10} \right\rfloor \right) \notag\\ &= 10n + 10\left\lfloor \frac{x}{10} \right\rfloor \notag\\ &= 10n + \lfloor x \rfloor_{10}. \end{align}\] ◻
Now we define a sequence \(\{ r_k \}\). At this point, we do not imply any connection between \(\{r_k\}\) and the blocks mentioned in the introduction, see equation (1). This connection will only be established at Proposition (3).
Definition 3. We define \(\{ r_k \}\) as the sequence indexed by the set of non-negative integers and defined by the sum \[\begin{equation} r_k = \sum_{q=0}^k 10 \left[ 5 + (-1)^q\right]q. \end{equation}\]
Example 3. The first terms of the sequence \({r_k}\) are \(r_0 = 0\), \(r_1 = 40\), \(r_2 = 160\), \(r_3 = 280\), and so on.
Using the parity of \(k\), we can find explicit formulas for the values of \(r_k\).
(prop:evenoddrk)
Proposition 2. Let \(k\) be a non-negative integer. Then \(r_k = 25k^2 + 30k\) when \(k\) is even and \(r_k = 25k^2 + 20k - 5\) when \(k\) is odd.
Proof. The proof is carried out using the formulas for partial sums of arithmetic progressions. First, in the case where \(k\) is even, we assume \(k = 2\ell\) for some \(\ell \in \mathbb{N}\), and we have:
\[\begin{align} r_k &= r_{2\ell} \notag\\ &= 40 + 2 \cdot 60 + 3 \cdot 40 + \cdots + 2\ell \cdot 60 \notag\\ &= 40(1 + 3 + \cdots + (2\ell-1)) + 60(2 + 4 + \cdots + 2\ell) \notag\\ &= 40\ell^2 + 60\ell(\ell+1) \notag\\ &= 100\ell^2 + 60\ell \notag\\ &= 25k^2 + 30k. \end{align}\]
When \(k\) is odd, we suppose that \(k = 2 \ell -1\) for some \(\ell \in \mathbb{N}\), and then we have:
\[\begin{align} r_k &= r_{2\ell-1} \notag\\ &= 40 + 2\cdot60 + 3\cdot40 + \cdots + (2\ell-1)\cdot40 \notag\\ &= 40(1 + 3 + \cdots + (2\ell-1)) + 60(2 + 4 + \cdots + 2(\ell-1)) \notag\\ &= 40\ell^2 + 60(\ell-1)\ell \notag\\ &= 100\ell^2 - 60\ell \notag\\ &= 25(k+1)^2 - 30(k+1) \notag\\ &= 25k^2 + 50k + 25 - 30k - 30 \notag\\ &= 25k^2 + 20k - 5. \end{align}\] ◻
Definition 4. We define a mapping \(k : \mathbb{R}_{\geq 0} \to \mathbb{Z}_{\geq 0}\) associating each non-negative real number \(x\) to the smallest integer \(k(x) \geq 0\) such that \(\lfloor x \rfloor_{10} \leq r_{k(x)}\). Furthermore, in order to better comprehend the behavior of \(k\) on square numbers, we define \(k_2 : \mathbb{Z}_{\geq 0} \to \mathbb{Z}_{\geq 0}\) by \(k_2(x) = k(x^2)\).
Throughout the text we may denote \(k(x)\) by \(k\), omitting \(x\) when it’s clear. In other words, \(k=k(x)\) when there is no risk of confusion.
Example 4. For \(x = 81\), we have \(k(x) = 2\) because \(r_0 = 0\), \(r_1 = 40\) and \(r_2 = 160\) and \(\lfloor x\rfloor_{10} = 80\) is greater than \(r_0\) and \(r_1\) but \(\lfloor x\rfloor_{10} \leq r_2 = 160\).
To motivate our next step, we compute the \(k_2(n)\) for \(n\) between \(1\) and \(47\). This can be done either by calculating the values of \(r_k\) using the recursive formula, or by applying the closed-form expression established in Proposition (2). Organizing this data in a Table 2, we have:
| \(k_2^{-1}(p)\) | \(r_p\) | |
|---|---|---|
| \(0\) | \(1, 2, 3\) | \(0\) |
| \(1\) | \(4, 5, 6, 7\) | \(40\) |
| \(2\) | \(8, 9, 10, 11, 12, 13\) | \(160\) |
| \(3\) | \(14, 15, 16, 17\) | \(280\) |
| \(4\) | \(18, 19, 20, 21, 22, 23\) | \(520\) |
| \(5\) | \(24, 25, 26, 27\) | \(720\) |
| \(6\) | \(28, 29, 30, 31, 32, 33\) | \(1080\) |
| \(7\) | \(34, 35, 36, 37\) | \(1360\) |
| \(8\) | \(38, 39, 40, 41, 42, 43\) | \(1840\) |
| \(9\) | \(44, 45, 46, 47\) | \(2200\) |
| \(\vdots\) | \(\vdots\) | \(\vdots\) |
Proposition 3. Let \(p\) be a positive integer, then \[\begin{equation} k_2^{-1}(p) = \begin{cases} \left\{ 5(p-2) + j : j \in ⟦8,13⟧ \right\}, &\text{ if $p$ is even}, \\ \left\{ 5(p-1) + j : j \in ⟦4,7⟧ \right\}, &\text{ if $p$ is odd}. \end{cases} \end{equation}\]
Moreover,
If \(p\) is even, the numbers in the set \(\left\{ \left\lfloor \big(5(p - 2) + j\big)^2 \right\rfloor_{10} : j \in ⟦8,13⟧ \right\}\) are in arithmetic progression with common difference \(10p\), and are given by the relation \[\begin{align} \lfloor \big(5(p - 2) + j\big)^2 \rfloor_{10} = r_p - (13 - j)\cdot 10p, \end{align}\] for \(j \in ⟦7,13⟧\).
If \(p\) is odd, the numbers in the set \(\left\{ \left\lfloor \big(5(p-1) + j\big)^2 \right\rfloor_{10}: j \in ⟦4,7⟧ \right\}\) are in arithmetic progression with common difference \(10p\), and are given by the relation \[\begin{equation} \left\lfloor (5(p-1) + j)^2 \right\rfloor_{10} = r_p - (7-j) \cdot 10p \end{equation}\] for \(j \in ⟦3,7⟧\).
Proof. First, we prove the claims about arithmetic progression.
In the case that \(p\) is even, by the Proposition (2), we have that \(r_p = 25p^2 + 30p\). Besides that, with arithmetic manipulations and using Proposition (1), we have:
\[\begin{align} \begin{split} \left\lfloor (5(p-2) + j)^2 \right\rfloor_{10} &= \left\lfloor 25(p-2)^2 + 10(p-2)j + j^2 \right\rfloor_{10} \\ &= 25(p-2)^2 + 10(p-2)j + \lfloor j^2 \rfloor_{10} \\ &= 25p^2 -100p + 100 + 10pj - 20j + \lfloor j^2\rfloor_{10} \\ &= r_p - 130p + 100 + 10pj - 20j + \lfloor j^2 \rfloor_{10}\\ &= r_p - (13-j)10p + 100 - 20j + \lfloor j^2 \rfloor_{10}. \end{split} \end{align}\] By inspection, we have that \(100 - 20j + \lfloor j^2 \rfloor_{10} = 0\) for \(j \in ⟦7,13⟧\). Therefore,
\[\begin{equation} \label{eq:eqA}\tag{2} \lfloor (5(p-2) + j)^2 \rfloor_{10} = r_p - (13-j)10p, \end{equation}\] for \(j \in ⟦7,13⟧\), as desired.
Although equation (2) holds for every \(j \in ⟦7,13⟧\), the strict inequality required to guarantee membership in \(k_2^{-1}(p)\) only holds for \(j \in ⟦8,13⟧\). Indeed, for \(j = 7\) we obtain \[\lfloor (5(p-2)+7)^2 \rfloor_{10} = r_p - 6 \cdot 10p = r_{p-1},\] which does not satisfy the strict inequality \[\lfloor (5(p-2)+j)^2 \rfloor_{10} > r_{p-1}.\] Therefore, the elements of \(k_2^{-1}(p)\) in the even case are precisely those corresponding to \(j \in ⟦8,13⟧\).
In the case that \(p\) is odd, by Proposition (2), we have that \(r_p = 25p^2 + 20p - 5\). With similar calculations as those of the last case, we have that \[\begin{equation} \left\lfloor (5(p-1) + j)^2 \right\rfloor_{10} = r_p - (7-j)10p + 30 - 10j + \left\lfloor j^2 \right\rfloor_{10}. \end{equation}\] Again, by inspection, we have that \(30 - 10j + \lfloor j^2 \rfloor_{10} = 0\) for \(j \in ⟦3,7⟧\). Then, \[\begin{equation} \left\lfloor (5(p-1) + j)^2 \right\rfloor_{10} = r_p - (7-j)10p \end{equation}\] for \(j \in ⟦3,7⟧\), as desired.
Using that, now we prove the claims about the elements of \(k_2^{-1}(p)\).
In the case that \(p\) is even, to prove that \(\{ 5(p-2) + j : j \in ⟦8,13⟧ \} \subseteq k_2^{-1}(p)\) we need to show that for those values of \(j\) we have simultaneously that \(\lfloor (5(p-2) + j)^2 \rfloor_{10} \leq r_p\) and \(\lfloor (5(p-2) + j)^2 \rfloor_{10} > r_{p-1}\). The first inequality is a consequence of equation (2): \[\begin{equation} \lfloor (5(p-2) + j)^2 \rfloor_{10} =r_p - (13-j)10p \leq r_p, \end{equation}\] for \(j \in ⟦7,13⟧\). For the second inequality, we remember that from the definition of \(r_p\), we can calculate \(r_{p-1} = r_p - 60p\), and from equation (2), we have that the inequality \[\begin{equation} \lfloor (5(p-2) + j)^2 \rfloor_{10} =r_p - (13-j)10p > r_{p-1} = r_p - 60p, \end{equation}\] holds for \(j \in ⟦8,13⟧\) but not for \(j = 7\).
To establish the inclusion \(k_2^{-1}(p) \subseteq \left\{5(p-2) + j : j \in ⟦8,13⟧ \right\}\), it is sufficient to show that \(5(p-2) +7 \not \in k_2^{-1}(p)\) and that \(5(p-2) +14 \not \in k_2^{-1}(p)\). We have already shown that \(5(p-2) +7 \not \in k_2^{-1}(p)\). For \(5(p-2) +14 \not \in k_2^{-1}(p)\), notice that \(\lfloor (5(p-2) + 13)^2 \rfloor_{10} =r_p\), then \(\lfloor (5(p-2) + 14)^2 \rfloor_{10} > r_p\). Therefore, \(5(p-2) +14 \not \in k_2^{-1}(p)\).
The case where \(p\) is odd
,follows from the even case, as \(k\) is an increasing function and in this case, we already know \(k_2^{-1}(p-1)\) and \(k_2^{-1}(p+1)\). Therefore \(k_2^{-1}(p)\) consists of the positive integers between \(\max k_2^{-1}(p-1)\) and \(\min k_2^{-1}(p+1)\). This is to say that \(k_2^{-1}(p) = \{ 5(p-1) + j : j \in ⟦4,7⟧ \}\).
◻
Corollary 1. Let \(p\) be a positive integer, then \(\text{card }k_2^{-1}(p) = 5 + (-1)^p\). That is: \(\text{card }k_2^{-1}(p) = 6\) if \(p\) is even and \(\text{card }k_2^{-1}(p) = 4\) if \(p\) is odd.
Corollary 2. Let \(g : \mathbb{Z}_{\geq 1} \to \mathbb{Z}\) be defined by the rule \(g(n) = \lfloor n^2 \rfloor_{10} - \lfloor (n-1)^2 \rfloor_{10}\). Then, \(g(n) = 10 k_2(n) = 10k(n^2)\) for every \(n \in \mathbb{Z}_{\geq 1}\).
Proof. Let us assume that \(n \in \mathbb{Z}_{\geq 4}\) and \(p = k_2(n)\) is even, in light of the fact that the proof of the case of \(p\) being odd proceeds in a similar manner, and when \(n \in \{1,2,3\}\), the result holds by inspection. Therefore, we can write \(n = 5(p-2)+j\), where \(j \in ⟦8,13⟧\). In this case, we have two possibilities:
If \(k_2(n-1) = k_2(n)\), then \((n-1) = 5(p-2)+(j-1)\) and
\[\begin{align} g(n) &= \lfloor n^2 \rfloor_{10} - \lfloor (n-1)^2 \rfloor_{10} \notag\\ &= [r_p - (13-j)10p] - [r_p - (13-(j-1))10p] \notag\\ &= 10p \notag\\ &= 10k_2(n). \end{align}\]
If \(k_2(n-1) = k_2(n)-1\), then we are in a frontier case, where \(n = \min k_2^{-1}(p)\) and \(n-1 = \max k_2^{-1}(p-1)\). Therefore, we have \((n-1) = 5[(p-1)-1]+i\), where \(i \in ⟦4,7⟧\). It is clear that \(i = j-1\), \(j=8\) and
\[\begin{align} g(n) &= \lfloor n^2 \rfloor_{10} - \lfloor (n-1)^2 \rfloor_{10} \notag\\ &= [r_p - (13-j)10p] - [r_{p-1} - (7 - i)10p] \notag\\ &= [r_p - 5\cdot10p] - [r_p-(5+(-1)^p)10p] \notag\\ &= 10p \notag\\ &= 10k_2(n). \end{align}\]
◻
Figure 1 provides a graphical representation of the sequence of differences \(\lfloor n^2\rfloor_{10}-\lfloor (n-1)^2\rfloor_{10}\), highlighting the alternating block lengths that underlie the construction developed throughout the paper.
Corollary 3. Let \(p\) be a positive integer, then \(r_p = \lfloor \max (k_2^{-1}(p))^2 \rfloor_{10}\).
Proof. We will prove the case where \(p\) is even, in light of the fact that the proof of the case of \(p\) being odd proceeds in a similar manner. From Proposition (3), it follows that:
\[\begin{equation} r_p = \lfloor (5(p-2)+13)^2\rfloor_{10} = \lfloor \max \{5(p-2) + j : j \in ⟦8,13⟧\}^2 \rfloor_{10} = \lfloor \max(k_2^{-1}(p))^2 \rfloor_{10}. \end{equation}\] ◻
We are now in position to justify the method we presented in the introduction for computing square roots of perfect squares that are greater than 11.
Definition 5. For values \(x \geq 11\) we define \[\begin{equation} f(x) = 3 + 6a + 4b - \frac{r_{k(x)} - \lfloor x \rfloor_{10}}{10k(x)} \end{equation}\] where \(a\) is the number of even numbers between \(1\) and \(k(x)\), namely \(a = a(k) = \left\lfloor \frac{k}{2} \right\rfloor\), and \(b\) is the number of odd numbers between \(1\) and \(k(x)\), namely \(b = b(k) = k - a(k)\).
Remark 1. For values \(x \geq 11\), we have that
\[\begin{equation} \label{fformula}\tag{3} f(x) = \begin{cases} 3 + 5k(x) - \dfrac{r_{k(x)} - \lfloor x \rfloor_{10}}{10k(x)} & \text{if } k(x) \text{ is even}, \\ 2 + 5k(x) - \dfrac{r_{k(x)} - \lfloor x \rfloor_{10}}{10k(x)} & \text{if } k(x) \text{ is odd}. \end{cases} \end{equation}\]
Theorem 1. Let \(f\) be defined as in Definition (5) and \(n \geq 4\) be a positive integer, then \(f(n^2) = n\).
Proof. If \(n \geq 4\), then \(k = k(n^2) \geq 1\). Suppose that \(k\) is even, from Corollary (3) we have that \(r_k = \left\lfloor (5(k-2) + 13)^2 \right\rfloor_{10}\) and \(n\) is of the form \(5(k-2) + j\) with \(j \in ⟦8,13⟧\). Because of Proposition (3), we know that \((13-j)10k = r_k - \lfloor n^2\rfloor_{10}\), thus
\[\begin{align} n &= 5(k-2) + j \notag\\ &= 5(k-2) + 13 + (j-13) \notag\\ &= 3+5k - \frac{r_k - \lfloor n^2\rfloor_{10}}{10k} \notag\\ &= f(n^2). \end{align}\]
Now suppose that \(k\) is odd. Similarly, we have that \(r_k = \left\lfloor (5(k-1) + 7)^2 \right\rfloor_{10}\) and \(n\) is of the form \(5(k-1) + j\) with \(j \in ⟦4,7⟧\). We also have that \((7-j)10k = r_k -\lfloor n^2\rfloor_{10}\), so that \[\begin{align} n &= 5(k-1) + j \notag\\ &= 5(k-1) + 7 + (j-7) \notag\\ &= 2 + 5k - \frac{r_k - \lfloor n^2 \rfloor_{10}}{10k} \notag\\ &= f(n^2). \end{align}\] ◻
Example 5. Applying the proposed digit-based procedure to the perfect square \(1849\), we obtain \(f(1849)~=~43\).
Proof. Notice that \(r_8 = 1840\), we then know that the termination index of \(1849\) is \(8\), that is the index \(k(1849)\) equals 8. As \(k\) is an even number, we can use the formula in equation (\(3\)): \[\begin{align} f(1849) &= 3 + 5k - \dfrac{r_k - \lfloor x \rfloor_{10}}{10k} \notag\\ &= 3 + 5 \cdot 8 - \frac{1840 - \lfloor 1849 \rfloor_{10}}{10 \cdot 8} \notag\\ &= 3 + 5 \cdot 8 - \frac{1840 - 1840}{10 \cdot 8} \notag\\ &= 3 + 5 \cdot 8 \notag\\ &= 43. \end{align}\] ◻
We’ll now discuss the behavior of \(f\) for numbers that are not perfect squares. One can easily check that the relation \(f(x^2) = x\) does not hold in general: for instance, \(f(x)\) is rational for every \(x\), therefore we can assure \(f(y^2) \neq y\), for all \(y \in \mathbb{R}\setminus \mathbb{Q}\). Nevertheless, using Lemma (1), we can show asymptotic convergence to the square root.
(lemma1)
Lemma 1. Let \(I, J \subseteq \mathbb{R}\) be sets, and let \(\varphi : I \to \mathbb{R}_{\ge 0}\) and \(\psi : J \to \mathbb{R}_{\ge 0}\) be monotonically non-decreasing functions. Suppose there exists an integer \(m\) such that \(\mathbb{Z}_{>m} \subseteq I \cap J\). If for every integer \(n\) such that \(n^2 > m\), we have \[\varphi(n^2) = \psi(n^2) = n,\] then \(\varphi\) is asymptotically equivalent to \(\psi\), that is: \[\begin{equation} \lim_{x \to +\infty} \frac{\varphi(x)}{\psi(x)} = 1. \end{equation}\]
Proof. For any sufficiently large real number \(x\), we can find an integer \(n\) such that \(n^2 > m\), \((n+1)^2 > m\), and \[\begin{align} n^2 \le x < (n+1)^2. \end{align}\] Since \(\varphi\) is a monotonically non-decreasing function, we can apply it to the inequality: \[\begin{align} \varphi(n^2) \leq \varphi(x) < \varphi((n+1)^2). \end{align}\] But by hypothesis, \(\varphi(n^2) = n\) for \(n^2 > m\), then we have \[\begin{align} n \leq \varphi(x) < n+1. \end{align}\] Similarly for \(\psi\) we have, \[\begin{align} n \leq \psi(x) < n+1. \end{align}\] Now, \[\begin{align} \frac{n}{n+1} < \frac{\varphi(x)}{\psi(x)} < \frac{n+1}{n}. \end{align}\] Therefore, considering the limit as \(x \to \infty\) we have \(n \to \infty\) as well. Then by squeeze theorem we get \[\begin{align} \lim_{x \to \infty} \frac{\varphi(x)}{\psi(x)} = 1. \end{align}\] Because \(\displaystyle \lim_{n \to \infty} \frac{n}{n+1} = \lim_{n \to \infty} \frac{n+1}{n} =1\). ◻
Remark 2. The hypothesis of Lemma (1) can be slightly relaxed. It is not necessary to assume that \(\mathbb{Z}_{>m} \subseteq I \cap J\). It suffices to require the existence of an integer \(m\) such that for every integer \(n > m\) we have \(n^2 \in I \cap J\), and \[\varphi(n^2) = \psi(n^2) = n.\] Indeed, the proof only relies on the possibility of choosing, for sufficiently large \(x\), an integer \(n\) satisfying \[n^2 \le x < (n+1)^2\] with both \(n^2\) and \((n+1)^2\) belonging to the domains of \(\varphi\) and \(\psi\). Therefore, the stronger assumption \(\mathbb{Z}_{>m} \subseteq I \cap J\) may be replaced by this weaker condition without affecting the conclusion.
Proposition 4. The function \(f\) converges asymptotically to the square root function restricted to \([11, \infty)\).
Proof. Setting \(\varphi(x) = f(x)\) and \(\psi(x) =\sqrt{x}\) for all \(x \geq 11\), the proposition follows from the Lemma (1) and Theorem (1). ◻
Results and discussion
The preceding results establish the correctness of the proposed method for perfect-square inputs and its asymptotic agreement with the square root function. We now examine the algorithmic implications of this construction. In particular, we derive a characterization of the termination index \(k(n)\) and use it to determine the computational complexity of the proposed procedure.
Theorem 2. Let \(n \in \mathbb{Z}_{\geq 16}\) be a perfect square. It follows that \(k(n)\) is of either form:
\[\begin{equation} k(n) = \left \lceil \frac{\sqrt{r_{k(n)}} - 3}{5} \right \rceil, \; \text{when $k(n)$ is even} \end{equation}\]
\[\begin{equation} k(n) = \left \lceil \frac{\sqrt{r_{k(n)}} - 2}{5} \right \rceil, \; \text{when $k(n)$ is odd} \end{equation}\]
Proof. We will prove the case where \(k(n)\) is even, in light of the fact that the proof of the case of \(k(n)\) being odd proceeds in a similar manner. From Corollary (3), it follows:
\[\begin{equation} r_{k(n)} = \left \lfloor \max(k_2^{-1} (k(n)))^2 \right \rfloor_{10} = \left \lfloor (5(k(n)-2)+13)^2 \right \rfloor_{10} = \left \lfloor (5k(n)+3)^2 \right \rfloor_{10}. \end{equation}\]
By the definition of \(\lfloor\cdot\rfloor_{10}\), we have that there is \(j \in ⟦0,9⟧\) such that:
\[\begin{equation} r_{k(n)} = (5k(n) + 3)^2 - j \Rightarrow k(n) = \frac{\sqrt{r_{k(n)} + j} - 3}{5}. \end{equation}\]
It can be noted that \(j\) is necessarily equal to \(9\). Indeed, observe that, by definition of \(\lfloor \cdot \rfloor_{10}\), the quantity \(j\) corresponds precisely to the units digit of \((5k(n)+3)^2\). Since removing the units digit amounts to subtracting an integer \(j \in \{0,\dots,9\}\), we necessarily have \[r_{k(n)} = (5k(n)+3)^2 - j \quad \text{with} \quad j \in \{0,\dots,9\}.\] Moreover, when \(k(n)\) is even, the integer \(5k(n)+3\) is odd and ends in the digit \(3\), hence \((5k(n)+3)^2\) ends in the digit \(9\). Therefore \(j=9\).
Note that \(k(n) \in \mathbb{Z}_{\geq 0}\) and \(k(n) \geq q(n)\), with:
\[\begin{equation} q(n) = \frac{\sqrt{r_{k(n)}} - 3}{5}. \end{equation}\]
Therefore, it is sufficient to show that \(|k(n) - q(n)| < 1\) to conclude that \(k(n) = \lceil q(n)\rceil\). Indeed:
\[\begin{align} |k(n) - q(n)| &= \frac{\sqrt{r_{k(n)} + j} - 3}{5} - \frac{\sqrt{r_{k(n)}} - 3}{5} = \frac{\sqrt{r_{k(n)} + j} - \sqrt{r_{k(n)}}}{5} \notag\\ &\leq \frac{\sqrt{r_{k(n)}} + \sqrt{j} - \sqrt{r_{k(n)}}}{5} = \frac{\sqrt{j}}{5} = \frac{3}{5} < 1. \end{align}\] ◻
Corollary 4. Let \(n \in \mathbb{Z}_{\geq 16}\) be a perfect square. If \(n\) is the input value of the proposed algorithm, then its time complexity is \(\Theta(\sqrt{n})\).
Proof. Let \(n \in \mathbb{Z}_{\geq 16}\) be a perfect square. Since after determining \(k(n)\), the remaining processes of the algorithm are of constant time, it is sufficient to show that the time complexity of determining \(k(n)\) is \(\Theta(\sqrt{n})\), or better yet, that of \(r_{k(n)}\), taking into account Theorem (2).
Let \(T(n)\) be the number of steps in the algorithm to determine the value of \(r_{k(n)}\). We aim to show that there are \(c_1,c_2 > 0\) and \(n_0 \in \mathbb{Z}_{\geq 0}\) such that:
\[\begin{equation} c_1 \sqrt{n} \leq T(n) \leq c_2 \sqrt{n},\; \forall \, n \geq n_0. \end{equation}\]
Note that \(T(n) = \min \{i \in \mathbb{Z}_{\geq 0} : r_i \geq \lfloor n \rfloor_{10} \} = k(n)\). With this in mind, it follows that:
\[\begin{equation} \sqrt{n} = f(n) \leq 3+ 5k(n) - \frac{r_{k(n)} - \lfloor n\rfloor_{10}}{10 k(n)} \leq 3+ 5k(n). \end{equation}\]
Therefore, determining that \(n_1 = 36\), it follows that:
\[\begin{equation} k(n) \geq \frac{\sqrt{n} -3}{5} \geq \frac{1}{10} \sqrt{n}, \; \forall \, n \geq n_1. \end{equation}\]
Similarly, observe that:
\[\begin{equation} k(n) \leq 2 \sqrt{n}, \; \forall \, n \geq n_2 = 16. \end{equation}\]
Indeed, we prove the inequality over \(m \in \mathbb{Z}_{\geq 4}\), where \(m^2 = n\), using induction. Firstly, note that:
\[\begin{equation} k(4^2) = k(16) = 1 \leq 8 = 2 \sqrt{4^2}. \end{equation}\]
Now observe that \[(m+1)^2 - m^2 = 2m+1,\] and therefore \[\lfloor (m+1)^2 \rfloor_{10} - \lfloor m^2 \rfloor_{10} \le 2m+1.\]
Since the blocks determined by the sequence \((r_k)\) grow with increments of order \(10k\), moving from \(m^2\) to \((m+1)^2\) can increase the value of \(\lfloor n \rfloor_{10}\) by at most one block. Hence the index \(k(n)\) can increase by at most one unit, which establishes the desired inequality.
Now, suppose that the statement is valid for \(m \in \mathbb{Z}_{\geq 4}\), note that:
\[\begin{equation} { k((m+1)^2) \le k(m^2)+1 \le \sqrt{m^2}+1 = m+1 \le 2(m+1) = 2\sqrt{(m+1)^2}.} \end{equation}\]
Therefore, we conclude that there are constants \(c_1 = \frac{1}{10},c_2 = 2 \in \mathbb{R}_{\geq 0}\) and a positive integer \(n_0 = 36\) such that:
\[\begin{equation} c_1 \sqrt{n} \leq k(n) = T(n) \leq c_2 \sqrt{n}, \; \forall \, n \geq n_0. \end{equation}\]
On this account, it follows that the proposed algorithm has a time complexity of order \(\Theta(\sqrt{n})\). ◻
Algorithmic aspects of integer square root computation have also been considered in earlier work (Rolfe, 1987), where efficiency and performance considerations are discussed from a computational standpoint.
Conclusions
In this work, we presented and formally justified a new method for computing square roots of perfect squares, originally conceived by students from Basic Education. Starting from simple numerical observations, the method was rigorously developed using elementary number-theoretic tools, leading to the construction of an explicit algorithm whose correctness was proven for all perfect squares. An analysis of its asymptotic behavior and computational complexity showed that the proposed procedure is consistent with classical approaches to square root computation.
Beyond its mathematical validity, the method illustrates how accessible patterns can give rise to nontrivial mathematical structures when properly explored. This highlights the pedagogical value of encouraging exploratory thinking and pattern recognition in early stages of mathematical education. The collaboration between school students and the PET Matemática group proved to be a fruitful environment for transforming intuitive ideas into mathematically rigorous results.
Finally, this work reinforces the role of university outreach and undergraduate research programs in bridging school mathematics and academic production. By valuing student-generated ideas and subjecting them to formal analysis, such initiatives contribute both to mathematical dissemination and to the formation of future researchers.
Acknowledgments
The authors would like to express their sincere gratitude to Felipe Kenji Iokota and Fabrício Ventura da Silva, the Basic Education students who conceived the original idea that inspired this work. Their curiosity, creativity, and enthusiasm for Mathematics were fundamental to the development of this study. The authors also thank the PET Matemática group, the Department of Mathematics, and the Universidade Estadual de Londrina for providing the academic and institutional environment that made possible the discussion, refinement, and formalization of the proposed method. Financial support from the Ministry of Education (MEC), through the Tutorial Education Program (PET), and from the National Fund for Education Development (FNDE), is gratefully acknowledged
Author Contributions
J. A. Z. Garcia and P. M. A. Nogueira: methodology, formal analysis, writing – original draft preparation, writing – review & editing.
F. K. Iokota and F. V. Silva: conceptualization, investigation, methodology.
P. Liboni: funding acquisition, project administration, supervision, formal analysis, writing – original draft preparation, writing – review & editing.
L. R. C. Moreira: conceptualization, investigation, methodology, formal analysis.
E. H. Santana: methodology, software, formal analysis, writing – original draft preparation, writing – review & editing.
Conflicts of Interest
The authors declare no conflict of interest.
References
Brown, P. R. (2021). Detecting square numbers. Quaestiones Mathematicae, 44(2), 163–185. https://doi.org/10.2989/16073606.2019.1678530
Knuth, D. E. (1997). The art of computer programming (Vol. 2, 3rd ed.): Seminumerical Algorithms. Addison-Wesley.
Niven, I., Zuckerman, H. S., & Montgomery, H. L. (1991). An introduction to the theory of number. John Wiley & Sons.
Norris, F. R. (1974). An algorithm for determining perfect squares. ACM SIGCSE Bulletin, 6(3), 8–12. https://doi.org/10.1145/988881.988882
Pareth, S. (2026). Exact constructive digit-by-digit algorithms for integer e-th root extraction (arXiv:2601.02703) [Preprint]. Arxiv, 1-27. https://arxiv.org/pdf/2601.02703
Pólya, G. (1945). How to solve it: A new aspect of mathematical method. Princeton University Press.
Rolfe, T. J. (1987). On a fast integer square root algorithm. ACM SIGNUM Newsletter, 22(4), 6–11. https://doi.org/10.1145/37523.37525
Rudin, W. (1976). Principles of mathematical analysis. McGraw-Hill.
Savarimuthu, S. R., Muthuraji, K. C., & Eswaran, P. M. (2023). Square root for perfect square numbers using Vedic mathematics. AIP Advances, 13(1), 020047. https://doi.org/10.1063/5.0164287
Sipser, M. (2012). Introduction to the theory of computation. Cengage Learning.