Automorphic number
An automorphic number is a natural number n with d digits such that the square n^2 ends with the digits of n, or equivalently, n^2 \equiv n \pmod{10^d}. These numbers are the nontrivial idempotents in the ring of integers modulo $10^d, satisfying n^2 \equiv n \pmod{10^d} besides the trivial solutions 0 and 1.[1][2]
These numbers include the trivial cases 0 and 1, as $0^2 = 0 and $1^2 = 1, both of which end in themselves.[1] For each positive integer d \geq 1, there are exactly two nontrivial automorphic numbers modulo $10^d (excluding the trivial 0 and 1), which can be represented as d-digit strings (possibly with leading zeros), one ending in 5 and the other in 6.[1] Examples include 5 ($5^2 = 25) and 6 ($6^2 = 36) for one digit; 25 ($25^2 = 625) and 76 ($76^2 = 5776) for two digits; 376 ($376^2 = 141376) and 625 ($625^2 = 390625) for three digits; and 9376 ($9376^2 = 87909376) and 0625 ($0625^2 = 390625, ending in 0625) for four digits, with the pattern continuing to arbitrarily large sizes.[1] The two d-digit automorphic numbers (in their padded representations) sum to $10^d + 1, such as 25 + 76 = 101 and 625 + 376 = 1001.[1]
A key property is that if n is automorphic, then so is n^k for any positive integer k, meaning powers of automorphic numbers also end with n.[3] Automorphic numbers are also known as "curious numbers" and have connections to broader number theory, including p-adic numbers, where infinite expansions to the left of the decimal point allow for constructions of automorphic numbers with infinitely many digits.[1][3]
The concept was formalized and popularized in modern mathematics by Maurice Kraitchik in his 1942 book Mathematical Recreations, building on work by Kurt Hensel in the late 19th century linking it to p-adic analysis.[3] They appear in recreational mathematics and have been cataloged extensively, with sequences like A003226 in the Online Encyclopedia of Integer Sequences providing lists up to very large terms.[1]
Definition
In base 10
In base 10, an automorphic number n with d digits satisfies the congruence n^2 \equiv n \pmod{10^d}, meaning the last d digits of n^2 are precisely the digits of n.[2] This property implies that n(n-1) \equiv 0 \pmod{10^d}, so n must be congruent to 0 or 1 modulo both $2^d and $5^d, as $10^d = 2^d \times 5^d.[2] For each increasing digit level, solutions arise by solving these simultaneous congruences via the Chinese Remainder Theorem, yielding exactly two non-trivial automorphic numbers per digit length beyond the trivial cases of 0 and 1.[1]
Trivial examples include 0 and 1, as their squares end with themselves for any number of digits. Non-trivial 1-digit automorphic numbers are 5, since $5^2 = 25 ends with 5, and 6, since $6^2 = 36 ends with 6.[2] For 2 digits, the examples are 25, with $25^2 = 625 ending in 25, and 76, with $76^2 = 5776 ending in 76.[1] Three-digit cases include 376, as $376^2 = 141376 ends in 376, and 625, as $625^2 = 390625 ends in 625.[2]
In base b
In base b \geq 2, where b is an integer, an automorphic number is defined as a natural number n having exactly d digits in base b, so b^{d-1} \leq n < b^d, such that the base-b representation of n^2 ends with the same d digits as n. This condition is mathematically captured by the congruence n^2 \equiv n \pmod{b^d}, or equivalently, b^d divides n^2 - n (i.e., n(n-1) is divisible by b^d). To ensure n is precisely a d-digit automorphic number without trailing zeros in a higher-digit context, b^{d+1} does not divide n^2 - n, which relates to the b-adic valuation of n(n-1) being exactly d.[4]
This general framework extends the concept beyond base 10 to any integer base, allowing the study of automorphic numbers through modular arithmetic in the ring of b-adic integers, where solutions to n^2 \equiv n \pmod{b^d} correspond to idempotents in that ring. The trivial solutions n \equiv 0 \pmod{b^d} and n \equiv 1 \pmod{b^d} always exist but typically yield numbers with leading zeros unless d = 1. Nontrivial solutions depend on the prime factorization of b, as determined by solving the equation via the Chinese Remainder Theorem for the prime power factors of b^d.[4]
Illustrative examples appear in small bases. In base 2, the 1-digit automorphic number is 1 (binary '1'), since $1^2 = 1, which ends with '1'. In base 3, the only 1-digit automorphic number is similarly 1, as $1^2 = 1 ends with 1, while other candidates like 2 fail ($2^2 = 4 = 11_3, ending with 1 ≠ 2). In base 6, the 1-digit automorphic numbers include 1, 3, and 4: $1^2 = 1 (ends with 1), $3^2 = 9 = 13_6 (ends with 3), and $4^2 = 16 = 24_6 (ends with 4). These examples highlight how the property manifests differently across bases, with more nontrivial cases emerging when b has multiple distinct prime factors.[4]
Properties
Uniqueness and existence
In base 10, for each integer d \geq 1, there exist exactly two non-trivial d-digit automorphic numbers (as d-digit strings, possibly with leading zeros in their numerical representation but excluding the trivial all-zero and ending-in-1 paddings); these satisfy n^2 \equiv n \pmod{10^d}. The trivial solutions 0 and 1 also satisfy the condition for every d, but 0 is conventionally excluded as non-positive, and for d=1, 1 is a separate trivial 1-digit solution alongside the non-trivial 5 and 6. For d \geq 2, the trivial solutions correspond to padded strings with leading zeros. For d \geq 2, the two non-trivial solutions are: one congruent to 1 modulo $2^d and 0 modulo $5^d (the "5-type," ending in 25), and the other congruent to 0 modulo $2^d and 1 modulo $5^d (the "6-type," ending in 76).[2][4]
This uniqueness follows from solving n(n-1) \equiv 0 \pmod{10^d}, where $10^d = 2^d \cdot 5^d. Since 2 and 5 are coprime, the Chinese Remainder Theorem decomposes the problem into independent systems modulo $2^d and $5^d. For each modulus p^e with p \in \{2,5\} and e=d, the equation n(n-1) \equiv 0 \pmod{p^e} has exactly two solutions: n \equiv 0 \pmod{p^e} or n \equiv 1 \pmod{p^e}, because n and n-1 are coprime, so one must absorb the full p-adic valuation e. Combining via CRT yields four solutions modulo $10^d: n \equiv 0 \pmod{10^d}, n \equiv 1 \pmod{10^d}, and the two non-trivial pairs above. The trivial solutions correspond to strings with leading zeros when padded to d digits for d > 1, leaving exactly two non-trivial d-digit (padded) automorphic numbers.[5][6]
In a general base b > 1, the existence and count of automorphic numbers modulo b^d depend on the prime factorization of b. If b = p^e is a prime power, there are exactly two solutions to n^2 \equiv n \pmod{b^d}: the trivial n \equiv 0, 1 \pmod{b^d}, with no non-trivial automorphic numbers, as solutions lift uniquely from modulo p via Hensel's lemma (since the derivative f'(n) = 2n - 1 is invertible at both roots for p \neq 2, and separately verifiable for p=2). For composite b with k distinct prime factors, there are $2^k total solutions modulo b^d (decomposed via CRT into choices of 0 or 1 modulo each prime power factor), yielding $2^k - 2 non-trivial d-digit automorphic numbers in base b, excluding leading zeros. Thus, in base 10 (k=2), exactly two non-trivial per digit length.[4]
Construction and patterns
Automorphic numbers in base 10 can be constructed recursively by starting with the one-digit solutions: 0, 1, 5, and 6, each of which satisfies the condition that its square ends with itself.[2] To extend a d-digit automorphic number n to a (d+1)-digit automorphic number, solve for the digit x (where $0 \leq x \leq 9) in the equation (n + x \cdot 10^d)^2 \equiv n + x \cdot 10^d \pmod{10^{d+1}}. This equation simplifies to finding x such that x (2n - 1) \equiv - (n^2 - n) / 10^d \pmod{10} after accounting for the known automorphicity of n modulo $10^d, where (n^2 - n) / 10^d is an integer, and it yields a unique solution for x in each branch due to the invertibility of $2n - 1 modulo 10.[6]
The trivial branches lift straightforwardly: the sequence beginning with 0 extends to strings of zeros (e.g., 00, 000), and the sequence beginning with 1 extends to strings ending in 1 (e.g., 01, 001). The non-trivial branches produce two distinct infinite families. The "5-branch," starting from 5, generates numbers such as 5, 25, 625, 0625, 90625, and 890625, where each subsequent number appends a digit to preserve the automorphic property, often resulting in endings like ...25 or ...625 as the digit length increases.[2] Similarly, the "6-branch," starting from 6, yields 6, 76, 376, 9376, 09376, and 109376, with patterns featuring recurring endings such as ...76 or ...376.[2] These families continue indefinitely, forming the complete set of non-trivial automorphic numbers in base 10.[6]
Explicit formulas facilitate direct computation without full recursion for the non-trivial branches. For the 5-branch, the d-digit number is given by $5^{2^{d-1}} \mod 10^d; for example, $5^{2^{3-1}} = 5^4 = 625 \mod [1000](/page/1000) = 625. For the 6-branch, it is $6^{5^{d-1}} \mod 10^d; for instance, $6^{5^{2-1}} = 6^5 = 7776 \mod 100 = 76. These methods confirm that automorphic numbers form exactly two infinite non-trivial families in base 10, beyond the trivial 0 and 1 extensions.[6][2]
Generalizations
k-automorphic numbers
A k-automorphic number in base b is a positive integer n having d digits in that base such that nk ≡ n (mod bd), meaning the base-b representation of nk ends with the digits of n. This congruence is equivalent to bd dividing nk − n, or n (nk−1 − 1) ≡ 0 (mod bd).
In base 10, the equation nk ≡ n (mod 10d) always has the trivial solutions n ≡ 0 and n ≡ 1 (mod 10d), independent of k. For k = 2, there are exactly four solutions modulo 10d for each d ≥ 1 (the two trivial ones and two nontrivial), corresponding to two infinite families of d-digit automorphic numbers.
For k = 3 in base 10, the one-digit solutions are 0, 1, 4, 5, 6, and 9, as 43 = 64 ends with 4 and 93 = 729 ends with 9 (in addition to the square-automorphic 0, 1, 5, 6). For larger d, additional solutions appear beyond the square-automorphic ones; for example, among three-digit numbers, 875 is a 3-automorphic number since 8753 = 669921875 ends with 875. These are known as trimorphic numbers.[7]
All 2-automorphic numbers satisfy the condition for any k ≥ 2, since if n2 ≡ n (mod m), then multiplying both sides by nk−2 yields nk ≡ nk−1 (mod m), and by induction on k (base case k=2 holds, and assuming it for k−1 gives nk = n · nk−1 ≡ n · n = n2 ≡ n (mod m)), the property holds for all higher powers. The converse does not hold, as evidenced by the extra solutions like 4, 9, and 875 for k=3 that are not 2-automorphic.[1]
Generalization: numbers where n^2 ends with the digits of a n
In base b, consider natural numbers n with d digits such that the square n^2 ends with the same digits as a \times n, where a is a fixed integer multiplier. Mathematically, this is expressed by the congruence
n^2 \equiv a n \pmod{b^d},
which rearranges to
n(n - a) \equiv 0 \pmod{b^d}.
This condition implies that b^d divides the product n(n - a), distributing the prime factors of b^d between n and n - a.
This concept generalizes standard automorphic numbers, which arise when a = 1.
In base b = 10, the case a = 0 yields the trivial solutions where n^2 \equiv 0 \pmod{10^d}, satisfied by any n divisible by $10^{\lceil d/2 \rceil }, as the 2-adic and 5-adic valuations of n^2 must each meet or exceed d. For instance, with d = 1, n = [0](/page/0) (mod 10) works, since $0^2 = 0 ends with 0 and $0 \times 0 = 0. Larger multiples of 10 provide solutions for higher d, such as n = 10 for d = 2, where $10^2 = 100 ends with 00 and $0 \times 10 = 0 ends with 00.
For a = 2, examples in base 10 include n = 2 (d = 1), as $2^2 = 4 ends with 4 and $2 \times 2 = 4; and n = 52 (d = 2), as $52^2 = 2704 ends with 04 and $2 \times 52 = 104 ends with 04. Another is n = 50 (d = 2), where $50^2 = 2500 ends with 00 and $2 \times 50 = 100 ends with 00. These illustrate how the ending digits of n^2 match those of $2n.
The construction parallels that of standard automorphics, relying on the Chinese Remainder Theorem to solve the congruence modulo the prime power factors of b^d (e.g., $2^d and $5^d for base 10). For each prime power p^k dividing b^d, the equation n(n - a) \equiv 0 \pmod{p^k} is solved by distributing the valuation k between v_p(n) and v_p(n - a). If p does not divide a, the solutions are precisely n \equiv 0 \pmod{p^k} or n \equiv a \pmod{p^k}, yielding two solutions per prime. Combining via CRT gives $2^r solutions modulo b^d, where r is the number of distinct primes dividing b; for base 10, this is 4 solutions when \gcd(a, 10) = 1.
When \gcd(a, b) > 1, the number of solutions varies, as n and n - a may share prime factors with b, allowing more flexible valuation distributions and potentially more than $2^r solutions. For example, with a = 2 and base 10 (\gcd(2, 10) = 2), there are 4 solutions modulo $10^2 (0, 2, 50, 52), but the pairing differs from the coprime case due to shared 2-adic factors. This variability highlights how the multiplier a influences existence and count, with coprime a and b producing pairings analogous to the idempotent structure in standard automorphics.
Trimorphic numbers
Trimorphic numbers are integers n such that n^3 ends with the digit sequence of n itself, meaning if n has d digits, then n^3 \equiv n \pmod{10^d}. This condition positions trimorphic numbers as the specific instance of 3-automorphic numbers in base 10, where the power is raised to 3 rather than 2.[8][7]
In base 10, the one-digit trimorphic numbers are 0, 1, 4, 5, 6, and 9, as their cubes end in themselves (for example, $5^3 = 125). For two digits, representative examples include 24 ($24^3 = 13824), 25 ($25^3 = 15625), 49 ($49^3 = 117649), 76 ($76^3 = 438976), and 99 ($99^3 = 970299). Three-digit examples encompass 125 ($125^3 = 1953125), 376 ($376^3 = 53157376), 625 ($625^3 = 244140625), and 875 ($875^3 = 669921875). These illustrate how trimorphic numbers extend beyond trivial cases like 0 and 1.[7][8]
A key property of trimorphic numbers is their greater prevalence compared to automorphic numbers for squares, as every solution to n^2 \equiv n \pmod{10^d} also satisfies the cubic condition via multiplication, but the reverse does not hold, yielding additional solutions. The equation n^3 - n \equiv 0 \pmod{10^d} factors as n(n-1)(n+1) \equiv 0 \pmod{10^d}, and by the Chinese Remainder Theorem, solutions modulo $2^d and $5^d combine to produce more than the typical pair of non-trivial automorphic numbers per digit length. For instance, the count of d-digit trimorphic numbers in base 10 increases with d, reflecting the lifting of solutions in p-adic settings for p=2 and p=5. A full characterization for base 10 and general bases confirms that trimorphic numbers form a structured set tied to these modular roots.[4][7]
Broader extensions
Automorphic numbers arise as the non-trivial solutions to the congruence n^2 \equiv n \pmod{b^d} in base b, which precisely identifies them as idempotent elements in the ring \mathbb{Z}/b^d\mathbb{Z}. For the case a=1 in more general a-automorphic definitions, these idempotents satisfy n^k \equiv n \pmod{b^d} for all integers k \geq 1, since if n^2 \equiv n \pmod{b^d}, then by induction n^{k+1} = n^k \cdot n \equiv n \cdot n = n^2 \equiv n \pmod{b^d}. Thus, numbers automorphic under squaring are simultaneously automorphic under all higher powers, providing a natural extension beyond single-exponent cases.[2]
In the ring-theoretic framework, the structure of \mathbb{Z}/b^d\mathbb{Z} decomposes via the Chinese Remainder Theorem when b has multiple prime factors. If b = p_1^{e_1} \cdots p_r^{e_r} with distinct primes p_i, then \mathbb{Z}/b^d\mathbb{Z} \cong \prod_{i=1}^r \mathbb{Z}/p_i^{d e_i}\mathbb{Z}, and each component \mathbb{Z}/p_i^{d e_i}\mathbb{Z} has exactly two idempotents: 0 and 1. Consequently, the total number of idempotents—and thus automorphic numbers of "length" up to d digits in base b—is $2^r, comprising the trivial solutions 0 and 1 along with $2^r - 2 non-trivial ones. These non-trivial idempotents pair as e and $1 - e, where e is constructed to be congruent to 1 modulo some prime power factors and 0 modulo others.[9][1]
This ring-theoretic perspective extends automorphic numbers to the b-adic integers \mathbb{Z}_b, the completion of \mathbb{Z} with respect to the b-adic valuation. By Hensel's lemma, each idempotent solution modulo b lifts uniquely to an idempotent in \mathbb{Z}_b, yielding infinite b-adic expansions that approximate the finite-digit automorphic numbers as truncations. For prime power bases b = p^e, the only idempotents are the trivial 0 and 1, which lift straightforwardly; for composite b like 10, the non-trivial lifts correspond to the familiar sequences ending in ...25 and ...76 (modulo higher powers of 10). These b-adic idempotents connect automorphic numbers to broader algebraic number theory, particularly the decomposition of rings of b-adic integers into products over prime factors.[2][9]
An open question concerns the distribution of digits in these infinite b-adic expansions of non-trivial idempotents. For base b = pq with distinct primes p, q (e.g., b=10), numerical computations of millions of digits suggest uniform distribution across 0 to b-1, with chi-squared tests confirming statistical randomness at high confidence levels. However, whether these expansions are normal (containing every finite digit sequence with the expected frequency) remains unsolved, with potential links to problems in symbolic dynamics like Ulam's cellular automaton conjecture. In general bases b, the density of automorphic numbers among all d-digit numbers is $2^r / b^d, which approaches zero exponentially as d increases, but finer asymptotic behaviors or existence patterns in non-standard bases (e.g., non-integer) lack comprehensive study.[9]
Computation
Algorithms for generation
Generating automorphic numbers for small numbers of digits d can be accomplished using a brute-force approach, where all integers n from 0 to b^d - 1 are checked to determine if n^2 \equiv n \pmod{b^d}, with b denoting the base (typically 10). This method is feasible for d \leq 6 due to the manageable search space of up to $10^6 candidates, but it becomes computationally prohibitive for larger d as the complexity grows exponentially with O(b^d).[10]
For scalable generation, recursive lifting algorithms based on Hensel's lemma provide an efficient alternative, enabling the extension of solutions from modulo b^d to modulo b^{d+1}. Consider the polynomial f(n) = n^2 - n, where a solution n_d satisfies f(n_d) \equiv 0 \pmod{b^d}. To lift to n_{d+1} = n_d + x \cdot b^d \pmod{b^{d+1}} for an unknown digit x, substitute into f to obtain the congruence f(n_{d+1}) \equiv 0 \pmod{b^{d+1}}, which simplifies to (2n_d - 1)x \equiv -f(n_d)/b^d \pmod{b} under the assumption that the derivative f'(n_d) = 2n_d - 1 is invertible modulo b. Solving for x requires computing the modular inverse of $2n_d - 1 modulo b, yielding a unique lift provided the inverse exists. This process iterates from initial trivial solutions (e.g., n = 0, 1 modulo b), with each step requiring O(d) operations for modular arithmetic on d-digit numbers, resulting in overall complexity of O(d^2) to generate up to d digits.[11][12]
In base 10, where b = 10 = 2 \cdot 5, an optimized variant exploits the Chinese Remainder Theorem (CRT) by separately lifting solutions modulo $2^d and $5^d, then combining them. Starting from base solutions modulo 2 and 5 (e.g., 0 and 1 modulo both), Hensel lifting is applied independently: for the sequence ending in 5, solutions modulo $5^d are trivial (n ≡ 0 mod 5), while modulo $2^d they are lifted recursively; the reverse holds for the sequence ending in 6. Closed-form expressions facilitate this: for the "6-branch," n \equiv 1 + 5^d (2^d - (5^d)^{-1} \pmod{2^d}) \pmod{10^d}, and for the "5-branch," n \equiv 1 + 2^d (5^d - (2^d)^{-1} \pmod{5^d}) \pmod{10^d}, with inverses computed via the extended Euclidean algorithm. Precomputing inverses iteratively reduces per-step cost, achieving O(d \log d) complexity using fast multiplication, and enabling generation of automorphic numbers with millions of digits on standard hardware.[12][10][11]
These lifting methods necessitate arbitrary-precision arithmetic libraries (e.g., GMP) for large d, as standard fixed-precision types overflow beyond approximately 18 digits; without such handling, computations halt at modest scales, a limitation often overlooked in basic descriptions. For instance, generating 10,000-digit automorphic numbers requires managing multi-gigabyte integers, yet remains practical with optimized implementations.[12][10]
Programming implementation
Generating automorphic numbers programmatically relies on iteratively lifting initial solutions modulo the base b to higher powers b^d by solving the congruence x^2 \equiv x \pmod{b^d}, a direct application of Hensel's lemma to the polynomial f(x) = x^2 - x. This approach ensures efficiency, particularly for base 10, by extending solutions one digit at a time rather than exhaustively checking all possible d-digit numbers.[13]
In Python, which natively supports arbitrary-precision integers, the following function implements this lifting process. It starts with the base cases modulo b and iteratively finds extensions that satisfy the condition modulo b^{m+1} by testing possible digits x (feasible since b is typically small, like 10). Trivial solutions (0 and 1) are included but can be filtered; non-trivial ones from the 5 and 6 branches are the focus for base 10.
python
def generate_automorphic(b, d):
"""
Generate all automorphic numbers modulo b^d (padded to d digits).
Returns list of integers representing the solutions.
"""
if d == 0:
return []
# Initial solutions modulo b
current = [x for x in range(b) if (x * x % b) == x]
for m in range(1, d):
bm = b ** m
bmp1 = bm * b
new_current = []
for n in current:
for x in range(b):
candidate = n + x * bm
if (candidate * candidate % bmp1) == candidate % bmp1:
new_current.append(candidate)
current = new_current
# Filter non-trivial (exclude 0 and 1)
non_trivial = [num for num in current if num not in (0, 1)]
return non_trivial
# Example usage for base 10, d=5
b = 10
d = 5
sols = generate_automorphic(b, d)
padded = [str(s).zfill(d) for s in sols]
print(padded) # Outputs: ['09376', '90625']
def generate_automorphic(b, d):
"""
Generate all automorphic numbers modulo b^d (padded to d digits).
Returns list of integers representing the solutions.
"""
if d == 0:
return []
# Initial solutions modulo b
current = [x for x in range(b) if (x * x % b) == x]
for m in range(1, d):
bm = b ** m
bmp1 = bm * b
new_current = []
for n in current:
for x in range(b):
candidate = n + x * bm
if (candidate * candidate % bmp1) == candidate % bmp1:
new_current.append(candidate)
current = new_current
# Filter non-trivial (exclude 0 and 1)
non_trivial = [num for num in current if num not in (0, 1)]
return non_trivial
# Example usage for base 10, d=5
b = 10
d = 5
sols = generate_automorphic(b, d)
padded = [str(s).zfill(d) for s in sols]
print(padded) # Outputs: ['09376', '90625']
This code produces the non-trivial 5-digit automorphic numbers in base 10: 09376 and 90625. Verification confirms $9376^2 = 87909376 (ends in 09376) and $90625^2 = 8212890625 (ends in 90625).[3]
For a general base b, the pseudocode mirrors the Python implementation but requires a modular inverse or linear congruence solver for larger b to find x without brute-force looping:
ALGORITHM GenerateAutomorphic(b, d):
current ← {x | 0 ≤ x < b AND x² ≡ x (mod b)}
FOR m = 1 TO d-1:
bm ← b^m
bmp1 ← b^(m+1)
new_current ← empty list
FOR each n IN current:
k ← (n² - n) / bm // integer division, exact
deriv ← 2*n - 1
target ← -k (mod b)
FOR x = 0 TO b-1: // or solve x * deriv ≡ target (mod b) efficiently
IF (x * deriv ≡ target (mod b)):
candidate ← n + x * bm
APPEND candidate TO new_current
current ← new_current
RETURN non-trivial elements of current (exclude 0, 1), padded to d digits in base b
ALGORITHM GenerateAutomorphic(b, d):
current ← {x | 0 ≤ x < b AND x² ≡ x (mod b)}
FOR m = 1 TO d-1:
bm ← b^m
bmp1 ← b^(m+1)
new_current ← empty list
FOR each n IN current:
k ← (n² - n) / bm // integer division, exact
deriv ← 2*n - 1
target ← -k (mod b)
FOR x = 0 TO b-1: // or solve x * deriv ≡ target (mod b) efficiently
IF (x * deriv ≡ target (mod b)):
candidate ← n + x * bm
APPEND candidate TO new_current
current ← new_current
RETURN non-trivial elements of current (exclude 0, 1), padded to d digits in base b
This pseudocode uses the derived lifting equation x (2n - 1) \equiv -k \pmod{b} at each step, where k is the carry from the previous square. For bases where b is large or composite, implement a general solver for the linear congruence, ensuring the gcd of the coefficient and b divides the target.[13]
In languages like C++ or Java without built-in big integers, use libraries such as GMP (for C++) or BigInteger (in Java) to handle large exponents and modular operations for d > 20. For instance, a C++ snippet might employ __int128 for moderate d or GMP's mpz_t for arbitrary size, adapting the lifting loop similarly. This ensures scalability, as each lift is O(1) per branch (typically two non-trivial branches in base 10), leading to O(d) overall time excluding big-integer costs.