A 2-Regular Sequence That Counts The Divisors of n^{2} + 1

Anton Shakov Department of Mathematics and Statistics Queen’s University 48 University Avenue, Kingston Ontario K7L 3N6 Canada

                    anton.shakov@queensu.ca

Abstract We introduce the 2-regular integer sequence \underline{A383066} which begins with s(n)_{n≥1} := {0, 1, 1, 2, 3, 3, 2, ⋯ }. We prove that the number of occurrences of an integer m ≥ 0 in this sequence is equal to τ(m^{2} + 1), the number of divisors of m^{2} + 1. Using this fact, we give a generating function for τ(m^{2} + 1). We also discuss other interesting properties of s(n), including its relationship to the Fibonacci sequence.

1 Introduction and proof of the main result

We begin by recalling the definition of k-regular sequences, which were introduced by Allouche and Shallit [?] as a powerful generalization of automatic sequences [?].

Definition 1. A sequence s(n) is k-regular if there exists an integer E such that, for all e_{j} > E and 0 ≤ r_{j} ≤ k^{e_{j}} − 1, every subsequence of s of the form s(k^{e_{j}}n + r_{j}) is expressible as an Z-linear combination

∑_{i} c_{ij}s(k^{f_{ij}}n + b_{ij}),

where f_{ij} ≤ E, and 0 ≤ b_{ij} ≤ k^{f_{ij}} − 1.

In the previous definition, the integers Z can be replaced by any commutative Noetherian ring R′, in which case we would say that s(n) is (R′, k)-regular. However, for the purposes of this paper, we consider only integer sequences. We begin by giving some well-known examples of 2-regular integer sequences.

Example 2. The 2-adic valuation of a positive integer n (\underline{A007814}), defined by v_{2}(n) := sup{k ∈ N_{0} : 2^{k}|n} is a 2-regular sequence since it satisfies the recursions

\begin{cases}v_{2}(2k + 1) = 0 \\ v_{2}(2k) = v_{2}(k) + 1 \end{cases}

with initial condition v_{2}(1) = 0.

Example 3. The Cantor sequence (\underline{A005823}) is a 2-regular sequence which consists of integers whose ternary expansions contain no 1s. The Cantor sequence c(n) satisfies the recursions

\begin{cases}c(2k) = 3c(k) + 2 \\ c(2k + 1) = 3c(k + 1) \end{cases}

with initial condition c(1) = 0.

For more examples of k-regular sequences, see Allouche and Shallit [?, pp. 186–194]. We now state the main result of this paper.

Theorem 4.

∑_{m≥0} τ(m^{2} + 1)x^{m} = ∑_{n≥1} x^{s(n)}

where τ is the usual divisor counting function and s(n)_{n≥1} is a 2-regular sequence defined recursively by

\begin{cases}s(4k) = 2s(2k) − s(k) \\ s(4k + 1) = 2s(2k) + s(2k + 1) \\ s(4k + 2) = 2s(2k + 1) + s(2k) \\ s(4k + 3) = 2s(2k + 1) − s(k) \end{cases}

with initial conditions s(1) = 0, s(2) = 1, s(3) = 1.

In other words, we prove that

#{n : s(n) = m} = τ(m^{2} + 1)

for all integers m ≥ 0.

Proof. Consider the binary tree of integer pairs (d, m) generated in the following way. We begin with the pair (1, 0). Each pair has two children, left and right, given by the maps L(d, m) := (d, m + d) and R(d, m) := (\frac{(m+d)^{2}+1}{d}, m + \frac{m^{2}+1}{d}) . The first four rows of the tree are given below.

(1, 0) (1, 1) (1, 2) ; (1, 3)_{\begin{matrix}⋯ \\ ⋯ \end{matrix}} ; (10, 7)_{\begin{matrix}⋯ \\ ⋯ \end{matrix}} ; (5, 3) ; (5, 8)_{\begin{matrix}⋯ \\ ⋯ \end{matrix}} ; (13, 5)_{\begin{matrix}⋯ \\ ⋯ \end{matrix}} (2, 1) (2, 3) ; (2, 5)_{\begin{matrix}⋯ \\ ⋯ \end{matrix}} ; (13, 8)_{\begin{matrix}⋯ \\ ⋯ \end{matrix}} ; (5, 2) ; (5, 7)_{\begin{matrix}⋯ \\ ⋯ \end{matrix}} ; (10, 3)_{\begin{matrix}⋯ \\ ⋯ \end{matrix}}

Figure 1: Integer pair tree.

The involution map ι(d, m) := (\frac{m^{2}+1}{d}, m) sends each pair to its reflection with respect to the tree’s central line of symmetry, represented by the dotted line in Figure 1. We note that R(d, m) = (ι ∘ L ∘ ι)(d, m), which can either be checked by direct computation or by fixing an integer pair (d, m) on the tree and visually seeing that ι ∘ L ∘ ι (reflection, left-child map, reflection) sends (d, m) to the same pair as the right-child map R(d, m).

Lemma 5. If a pair (d, m) appears on the integer pair tree then d ≥ 1, m ≥ 0, and d divides m^{2} + 1.

Proof. Suppose an integer pair (d, m) appears on the tree with the properties that d ≥ 1, m ≥ 0, and d|(m^{2} +1). We claim that these properties also hold for the transformed pairs L(d, m) and R(d, m). It is easy to see that both transformed pairs L(d, m) and R(d, m) are still integer pairs, that their first components are ≥ 1, and that their second components are ≥ 0. To see that the first component still divides 1+ the square of the second component, it suffices to check that this property is preserved by L and ι, since we saw that R = ι ∘ L ∘ ι. Indeed, the property d|(m^{2} + 1) is preserved by both L and ι since d|(m^{2} + 1) ⟹ d|((m + d)^{2} + 1) and \frac{m^{2}+1}{d}|(m^{2} + 1). The first integer pair on the tree is (1, 0), which satisfies all three properties. Therefore, all of its descendants must also satisfy all three properties.

Lemma 6. Suppose d ≥ 1, m ≥ 0, and d divides m^{2} + 1. Then the pair (d, m) appears on the integer pair tree exactly once.

Proof. We begin by restating the lemma so that it can be proved using induction. We let P (M) denote the statement “If d ≥ 1 divides m^{2} + 1 with 0 ≤ m ≤ M, then the pair (d, m) appears on the tree exactly once.” To prove the lemma we show that P (M) is true for all integers M ≥ 0 by induction on M. As our base case, we see that P (0) is true since the pair (1, 0) appears exactly once on the tree, in the first row. This is because L and R each increase the second component of a pair by at least 1, so there are no more pairs on the tree with second component 0. Now suppose M > 0. Our induction assumption is that P (M − 1) is true. Namely, we assume that for all d ≥ 1 with d|(m^{2}+1) and 0 ≤ m ≤ M −1 we have (d, m) appearing on the tree exactly once. We show that this implies P (M) is true by assuming that some d ≥ 1 divides M^{2} + 1 and using the induction assumption to prove that (d, M) must appear on the tree exactly once. The claim that (d, M) appears on the tree exactly once is equivalent to the statement that there exists a unique path from the root pair (1, 0) to (d, M) in terms of the maps L and R. It is easy to check that L^{−1}(d, M) = (d, M −d) and R^{−1}(d, M) = (\frac{(M−d)^{2}+1}{d}, M − \frac{M^{2}+1}{d}). We show that exactly one of the second components

of these inverse mappings \{M − d, M − \frac{M^{2}+1}{d}\} is nonnegative (which we showed in the previous lemma is a necessary condition for pairs to appear on the tree). The nonnegativity of exactly one of \{M − d, M − \frac{M^{2}+1}{d}\} is a result of the inequalities

inf \{d, \frac{m^{2} + 1}{d}\} ≤ m < sup \{d, \frac{m^{2} + 1}{d}\}

which hold for all positive integers d and m with d|(m^{2}+1). These inequalities can be proved by considering the cases d ≤ m and d > m and using the fact that m^{2} < m^{2}+1 < (m+1)^{2} for all m > 0. Equality occurs in the left inequality when (d, m) ∈ {(1, 1), (2, 1)}. Thus, exactly one of the pairs {L^{−1}(d, M), R^{−1}(d, M)} has a nonnegative second component. Furthermore, this component is strictly less than M. The properties d|(m^{2} + 1) and d ≥ 1 are clearly preserved by L^{−1} and R^{−1}. Therefore, by our induction assumption and Lemma 5, exactly one of the pairs {L^{−1}(d, M), R^{−1}(d, M)} appears on the tree and there exists a unique path from (1, 0) to this pair in terms of L and R. In other words, the pair (d, M) has exactly one parent appearing on the tree, which is guaranteed by our induction assumption to have a unique path back to (1, 0) in terms of L and R. Finally, this proves that (d, M) has a unique path to (1, 0) in terms of L and R and therefore appears on the tree exactly once, which shows that P (M) is true.

We now write only the second pair components as they appear on the integer pair tree.

0 12 ; 3_{\begin{matrix}⋯ \\ ⋯ \end{matrix}} ; 7_{\begin{matrix}⋯ \\ ⋯ \end{matrix}} ; 3 ; 8_{\begin{matrix}⋯ \\ ⋯ \end{matrix}} ; 5_{\begin{matrix}⋯ \\ ⋯ \end{matrix}} 13 ; 5_{\begin{matrix}⋯ \\ ⋯ \end{matrix}} ; 8_{\begin{matrix}⋯ \\ ⋯ \end{matrix}} ; 2 ; 7_{\begin{matrix}⋯ \\ ⋯ \end{matrix}} ; 3_{\begin{matrix}⋯ \\ ⋯ \end{matrix}}

Figure 2: Second component tree.

Let us temporarily define s(n) as the sequence one gets by reading the integers on the second component tree left-to-right or right-to-left, starting from the top. For example, s(1) = 0, s(2) = 1, s(3) = 1, etc. We will show that this agrees with the original definition we gave in Theorem 4. Using the new definition, and in light of Lemmas 5 and 6, this proves that the number of occurrences of an integer m ≥ 0 on the second component tree is equal to #{(d, m) : d ≥ 1, d|(m^{2} + 1)} = τ(m^{2} + 1). To see that s(n) satisfies the recursions we gave in Theorem 4, we keep track of the second components as they are changed by the maps L and R. For example, since L(d, m) = (d, m + d) and R(d, m) = (\frac{(m+d)^{2}+1}{d}, m + \frac{m^{2}+1}{d}), we

write m_{L} for m + d and m_{R} for m + \frac{m^{2}+1}{d}.

m m_{L} \begin{matrix}m_{L^{2}} \\ m_{RL} \end{matrix} m_{R} m_{LR} m_{R^{2}}

Figure 3: Three generations of second pair components.

A direct computation reveals that each integer in the bottom layer can be expressed as a linear combination of integers from previous rows.

m m_{L} \begin{matrix}m_{L^{2}} = 2m_{L} − m \\ m_{RL} = 2m_{L} + m_{R} \end{matrix} m_{R} m_{LR} = 2m_{R} + m_{L} m_{R^{2}} = 2m_{R} − m

Figure 4: Linear dependencies between second pair components.

We now rewrite the parent-child relationships in terms of the sequence s(n). Reading a two-child binary tree left-to-right, we see that for a parent with index k, its left child’s index is 2k while its right child’s index is 2k + 1.

m = s(k) m_{L} = s(2k) \begin{matrix}m_{L^{2}} = s(4k) \\ m_{RL} = s(4k + 1) \end{matrix} m_{R} = s(2k + 1) m_{LR} = s(4k + 2) m_{R^{2}} = s(4k + 3)

Figure 5: Dependencies re-indexed in terms of s(n).

Using the linear dependencies we found, we finally recover the recursions from Theorem 4

\begin{cases}s(4k) = 2s(2k) − s(k) \\ s(4k + 1) = 2s(2k) + s(2k + 1) \\ s(4k + 2) = 2s(2k + 1) + s(2k) \\ s(4k + 3) = 2s(2k + 1) − s(k). \end{cases}

2 Other properties of the sequence

We discuss some other interesting properties of the sequence s(n). From the recursions for s(n), it is easy to show that the row sums of the second component tree satisfy the linear