On Modular Representations of C-Recursive Integer Sequences

M. Prunescu University of Bucharest

Research Center for Logic, Optimization and Security (LOS)

Faculty of Mathematics and Computer Science

Academiei 14 Bucharest (RO-010014)

Romania

and

Institute of Logic and Data Science Bucharest Romania

and

Simion Stoilow Institute of Mathematics of the Romanian Academy Research Unit 5 P. O. Box 1-764

Bucharest (RO-014700)

Romania

mihai.prunescu@imar.ro
mihai.prunescu@gmail.com

J. M. Shunia Independent Researcher

Ann Arbor, MI

USA

jshunia@gmail.com

Abstract

Prunescu and Sauras-Altuzarra showed that all C-recursive sequences of natural numbers have an arithmetic div-mod representation that can be derived from their generating function. This representation consists of computing the quotient of two exponential polynomials and taking the remainder of the result modulo a third exponential polynomial, and works for all integers n ≥ 1. Using a different approach, Prunescu proved the existence of two other representations, one of which is the modmod representation, consisting of two successive remainder computations. This result has two weaknesses: the representation works only ultimately, and a correction term must be added to the first exponential polynomial. We show that a mod-mod representation without inner correction term holds for all integers n ≥ 1. This follows directly from the div-mod representation by an arithmetic short-cut from outside.

1 Introduction

The C-recursive sequences of order d are sequences t : ℕ → ℂ satisfying a relation of recurrence with constant coefficients

t(n + d) + α_{1}t(n + d − 1) + ⋯ + α_{d−1}t(n + 1) + α_{d}t(n) = 0

for all n ∈ ℕ, with α_{d} ≠ 0. With the recurrence rule, we associate the polynomial

B(X) := 1 + α_{1}X + ⋯ + α_{d}X^{d}.

Observe that deg B = d. We let B̃(X) denote the reciprocal polynomial

B̃(X) = X^{d}B(X^{−1}) = X^{d} + α_{1}X^{d−1} + ⋯ + α_{d}.

According to [6, Theorem 4.1.1] and [3, Theorem 1], the C-recursive sequences are exactly the sequences (s(n)) such that the generating function

f(X) = ∑_{n≥0} t(n)X^{n}

is a rational function A(X)/B(X) with deg(A) := k < deg(B) = d. We define Ã(X) = X^{k}A(X^{−1}) to be the reciprocal polynomial of A(X). We observe that

f(X^{−1}) = \frac{X^{d−k}X^{k}A(X^{−1})}{X^{d}B(X^{−1})} = X^{d−k} · \frac{Ã(X)}{B̃(X)}.

Prunescu and Sauras-Altuzarra proved [5] that if f is the generating function of a sequence consisting of natural numbers only, then there exists c ∈ ℕ such that for all n ∈ ℤ^{+}, we have

t(n) = ⌊c^{n^{2}}f(c^{−n})⌋ mod c^{n}.

The exact statement will be given below (see Theorem 2). In brief, if the sequence is Crecurrent, its generating function f is a rational function A(X)/B(X) with A(X), B(X) ∈ ℤ[X], deg(A(X)) = k < deg(B(X)) = d, and such that both polynomials A(X) and B(X) take positive values for real positive X inside the disk of convergence around 0. Then we have a div-mod representation

t(n) = ⌊\frac{c^{n^{2}+dn}A(c^{−n})}{c^{dn}B(c^{−n})}⌋ mod c^{n} = ⌊\frac{c^{n^{2}}c^{n(d−k)}Ã(c^{n})}{B̃(c^{n})}⌋ mod c^{n}.

We note that “div-mod” refers to the successive application of an integer division and a modular reduction.

Prunescu proved in [4] the following mod-mod representation. Let α_{d} ≠ 0 be the constant term of the recurrence rule for a C-recursive sequence, i.e., the constant term of B̃(X). Then there are c, n_{0} ∈ ℕ such that for n ≥ n_{0} we have

t(n) = \frac{((c^{n(d−1)+⌈n/2⌉} − sgn(α_{d}) · c^{n^{2}}c^{n(d−k)}Ã(c^{n})) mod B̃(c^{n})) mod c^{n}}{|α_{d}|} .

This representation has the advantage that

(c^{n(d−1)+⌈n/2⌉} − sgn(α_{d}) · c^{n^{2}}c^{n(d−k)}Ã(c^{n})) mod B̃(c^{n})

can be computed faster by modular arithmetic, but it has two disadvantages:

(i) It needs in general a correction term c^{n(d−1)+⌈n/2⌉} in the innermost exponential polynomial.

(ii) It holds only ultimately, for n greater than or equal to some a priori undetermined n_{0} ∈ ℕ. In fact, such an n_{0} can be determined by conditions used in the proof, but it is not clear that one can always take n_{0} = 1.

In the following we show that this result can be improved. If the constant term of B̃(X) is α_{d} ≠ 0, there exists an integer r ≥ c such that the following holds for all n ≥ 1:

t(n) = \frac{−1 − sgn(α_{d})}{2} + \frac{1}{|α_{d}|} (((− sgn(α_{d}) · r^{n^{2}}r^{n(d−k)}Ã(r^{n})) mod B̃(r^{n})) mod r^{n}) .

Observe that this representation does not contain any correction term and works for n ≥ 1. The proof, done by a short-cut of modular arithmetic, uses only the div-mod representation given above.

Other possibilities and methods to represent C-recursive sequences can be found in the monograph of Kauers and Paule [2].

2 Technical preparations

We define ℕ as the set of natural numbers with 0 included.

The first three useful results refer to C-recursive sequences. The next lemma can also be found in Everest et al. [1].

Lemma 1. [Prunescu & Sauras-Altuzarra, [5, Lemma 4]] If t : ℕ → ℂ is C-recursive, then there is an integer g ≥ 1 such that |t(n)| < g^{n+1} for every integer n ≥ 0.

Theorem 2. [Prunescu & Sauras-Altuzarra, [5, Theorems 1 and 2]] If t : ℕ → ℕ, f(X) is its generating function, R is the radius of convergence of f(X) at zero, and c, m, and n are three integers such that c ≥ 2, n ≥ m ≥ 2, c^{−m} < R, and t(n) < c^{n−2} for every integer n ≥ m, then

t(n) = ⌊c^{n^{2}}f(c^{−n})⌋ mod c^{n}.

Also, if c ≥ 8, c^{−1} < R, and t(n) < c^{n/3} for every n ≥ 1, then the representation works for every n ≥ 1.

The following corollary follows easily from Theorem 2.

Corollary 3. If the representation stated in Theorem 2 holds for some c ∈ ℕ for all n ≥ m, then it holds also if we replace c with any integer r ≥ c for all n ≥ m.

The next three lemmas are easy remarks of modular arithmetic.

Lemma 4. If B ≥ 2, A ≥ 1, B ∤ A, then − ⌊−A/B⌋ = ⌊A/B⌋ + 1.

Lemma 5. If a, y, C ∈ ℕ and 0 ≤ (ay) < C, then ((ay) mod C) = a(y mod C).

Lemma 6. If x, C ∈ ℕ, C ≥ 2, x ≢ (C −1) (mod C), then (x+1) mod C = (x mod C)+1.

The next lemma is the principal tool of this note.

Lemma 7. Let a, A, B, C ∈ ℤ such that A, B > 0, C ≥ 2, C | A, B ∤ A, B mod C ≡ a mod C, a ≠ 0, and |a|(⌊A/B⌋ mod C) < C if a < 0 (respectively, a + a(⌊A/B⌋ mod C) < C if a > 0).

(i) If a < 0, then

(A mod B) mod C = |a|(⌊A/B⌋ mod C).

(ii) If a > 0, then

((−A) mod B) mod C = a(1 + ⌊A/B⌋ mod C).

Proof. For both cases below we apply Lemmas 4 and 5. For the second case we apply also Lemma 6. We proceed with the cases.

(i) a < 0:

(A mod B) mod C = (A mod C − (B mod C)(⌊A/B⌋ mod C)) mod C

= (0 − (−|a|)(⌊A/B⌋ mod C)) mod C = (|a|(⌊A/B⌋ mod C)) mod C = |a|(⌊A/B⌋ mod C).

(ii) a > 0:

((−A) mod B) mod C = ((−A) mod C − (B mod C)(⌊A/B⌋ mod C)) mod C

= (0 − a(⌊(−A)/B⌋ mod C)) mod C = (a · (− ⌊(−A)/B⌋ mod C)) mod C = (a · (1 + ⌊A/B⌋ mod C)) mod C = (a + a ⌊A/B⌋ mod C) mod C = a(1 + ⌊A/B⌋ mod C).

3 Applications to C-recursive sequences

Theorem 8. Suppose that for all natural numbers n ≥ 1, a sequence t : ℕ → ℕ has the div-mod representation

t(n) = ⌊\frac{c^{n^{2}}c^{n(d−k)}Ã(c^{n})}{B̃(c^{n})}⌋ mod c^{n}.

If the constant term of B̃(X) is α_{d} < 0, then there is some natural number r such that for all n ≥ 1 we have

t(n) = \frac{1}{|α_{d}|} (((r^{n^{2}}r^{n(d−k)}Ã(r^{n})) mod B̃(r^{n})) mod r^{n}) .

If the constant term of B̃(X) is α_{d} > 0, then there is some natural number r such that for all n ≥ 1 we have

t(n) = −1 + \frac{1}{α_{d}} (((−r^{n^{2}}r^{n(d−k)}Ã(r^{n})) mod B̃(r^{n})) mod r^{n}) .

Proof. In order to apply Lemma 7, we recall that according to Corollary 3 there is a c_{0} ∈ ℕ such that for all r ≥ c_{0} and for all n ≥ 1 we have

t(n) = ⌊\frac{r^{n^{2}}r^{n(d−k)}Ã(r^{n})}{B̃(r^{n})}⌋ mod r^{n}.

Let r ≥ c_{0} be a natural number to fulfill also other conditions, which will be stated below. We introduce the notations A = r^{n^{2}}r^{n(d−k)}Ã(r^{n}), B = B̃(r^{n}), and C = r^{n} and we prove that for a good choice of r, which has to be sufficiently large, these numbers fulfill the conditions of Lemma 7.

The conditions C | A and B ∤ A are always fulfilled. The conditions A, B > 0 and C ≥ 2 are fulfilled for all n ≥ 1 if r is sufficiently large, as the main coefficients of Ã(X) and B̃(X) are positive. Let α_{d} be the constant term of the polynomial B̃(X) = X^{d}B(\frac{1}{X}), meaning that a = α_{d}. For r sufficiently large, we have B ≡ α_{d} (mod C). By definition, we have α_{d} ≠ 0 because deg(B) = deg(B̃) = d. We have to show that for r sufficiently large, |α_{d}|(⌊A/B⌋ mod C) < C if α_{d} < 0 respectively α_{d} + α_{d}(⌊A/B⌋ mod C) < C if α_{d} > 0, for all n ≥ 1. We recall that ⌊A/B⌋ mod C = t(n).

If α_{d} < 0, the inequality |α_{d}|(⌊A/B⌋ mod C) < C means that |α_{d}|t(n) < r^{n} and must be true for n ≥ 1.

If α_{d} > 0, the inequality α_{d} + α_{d}(⌊A/B⌋ mod C) < C means that α_{d}(t(n) + 1) < r^{n} and must be true for n ≥ 1.

But we know from 1 that if s : ℕ → ℂ is a C-recursive sequence, then there exists a g ∈ ℕ such that for all n ∈ ℕ we have |s(n)| < g^{n+1}. As s(n) = 2|α_{d}|t(n) is itself a Crecursive sequence and its values are natural numbers, there is some positive g ∈ ℕ such that 2|α_{d}|t(n) < g^{n+1} for all n ≥ 1. We can always find an r ∈ ℕ such that g^{n+1} < r^{n} for all n ≥ 1.

If t(n) ≥ 1, as 2|α_{d}|t(n) > |α_{d}|t(n) in the first case, respectively 2|α_{d}|t(n) ≥ |α_{d}|(1+t(n)) in the second case, the conditions of Lemma 7 are fulfilled. If t(n) = 0, the conditions are fulfilled for every r ≥ 1 in the first case and for every r > α_{d} in the second case.

Finally we choose r sufficiently large such that r ≥ c_{0} and all the conditions above are fulfilled.

Below we put both cases in only one formula.

Corollary 9. Suppose that for all natural numbers n ≥ 1, a sequence t : ℕ → ℕ has the representation

t(n) = ⌊\frac{c^{n^{2}}c^{n(d−k)}Ã(c^{n})}{B̃(c^{n})}⌋ mod c^{n}.

If the constant term of B̃(X) is α_{d} ≠ 0, there exists an integer r ≥ c such that, for all n ≥ 1, one has

t(n) = \frac{−1 − sgn(α_{d})}{2} + \frac{1}{|α_{d}|} (((− sgn(α_{d}) · r^{n^{2}}r^{n(d−k)}Ã(r^{n})) mod B̃(r^{n})) mod r^{n}) .

Remark 10. In [4] there is also an application to C-recursive sequences t : ℕ → ℤ. According to Lemma 1, for such a sequence there is an h ∈ ℕ such that for all n ≥ 0 we have |t(n)| < h^{n+1}. The sequence s(n) = t(n) + h^{n+1} has values in ℕ and is also C-recursive. Indeed, the generating function of s is a rational function and can be computed by

f(X) + \frac{h}{1 − hX} ,

where f(X) is the generating function of the sequence t. Consequently, the sequence s has a representation according to Corollary 9, while the sequence t has the representation t(n) = s(n) − h^{n+1}.

In [4], also the following mod-div representation is proved: There exist c, n_{0} ∈ ℕ such that for all n ≥ n_{0} we have

t(n) = ⌊\frac{(c^{n(d−2)+⌈n/2⌉} + c^{n^{2}}c^{n(d−k)}Ã(c^{n})) mod B̃(c^{n})}{c^{n(d−1)}} ⌋ .

Open Problem 11. Is it possible to find a purely arithmetic trick which shows that the mod-div representation (or even an improved version) is only a corollary of the div-mod representation, in a similar way as the short-cut shown here?

4 Examples

In this section, all representations are derived from the respective representations in [5]. In some cases a larger exponentiation base e > c is needed in order to keep the representation true for all natural numbers n ≥ 1.

4.1 Degree 2, natural numbers, negative constant term

The first group of examples consists of sequences of order 2 with a < 0. As in [4] it was shown that this kind of sequence does not need any inner correction term, these representations are not different from the representations displayed there. In what follows, OEIS refers to the On-Line Encyclopedia of Integer Sequences.

Example 12. [Fibonacci numbers, OEIS \underline{A000045}] For all n ∈ ℤ^{+}, we have

s(n) = (3^{n^{2}+n} mod (3^{2n} − 3^{n} − 1)) mod 3^{n}.

Example 13. [Lucas numbers, OEIS \underline{A000032}] The div-mod representation works for c = 3 (see Prunescu and Sauras-Altuzarra [5]). The mod-mod representation works for r = 5: For all n ∈ ℤ^{+}, we have

s(n) = ((2 · 5^{n^{2}+2n} − 5^{n^{2}+n}) mod (5^{2n} − 5^{n} − 1)) mod 5^{n}.

Example 14. [Pell numbers, OEIS \underline{A000129}] For all n ∈ ℤ^{+}, we have

s(n) = (3^{n^{2}+n} mod (3^{2n} − 2 · 3^{n} − 1)) mod 3^{n}.

Example 15. [Pell-Lucas numbers, OEIS \underline{A002203}] For all n ∈ ℤ^{+}, we have

s(n) = ((2 · 9^{n^{2}+2n} − 2 · 9^{n^{2}+n}) mod (9^{2n} − 2 · 9^{n} − 1)) mod 9^{n}.

4.2 Degree 2, natural numbers, positive constant term

Example 16. [Natural numbers, OEIS \underline{A001477}] For all n ∈ ℤ^{+}, we have

(((−4^{n^{2}+n}) mod (4^{2n} − 2 · 4^{n} + 1)) mod 4^{n}) − 1 = n.

Example 17. [All-twos, OEIS \underline{A007395}] For all n ∈ ℤ^{+}, we have

(((−2 · 4^{n^{2}+2n} + 2 · 4^{n^{2}+n}) mod (4^{2n} − 2 · 4^{n} + 1)) mod 4^{n}) − 1 = 2.

Example 18. [Mersenne numbers, OEIS \underline{A000225}] For all n ∈ ℤ^{+}, we have

\frac{1}{2} · (((−6^{n^{2}+n}) mod (6^{2n} − 3 · 6^{n} + 2)) mod 6^{n}) − 1 = 2^{n} − 1.

Example 19. [2^{n} + 1, OEIS \underline{A000051}] The div-mod representation works for c = 6 (see Prunescu and Sauras-Altuzarra [5]). The mod-mod representation works for r = 9: For all n ∈ ℤ^{+}, we have

\frac{1}{2} · ((−2 · 9^{n^{2}+2n} + 3 · 9^{n^{2}+n}) mod (9^{2n} − 3 · 9^{n} + 2) mod 9^{n}) − 1 = 2^{n} + 1.

Example 20. [OEIS \underline{A001081}, OEIS \underline{A001080}] Consider Pell’s equation

X^{2} − kY^{2} = 1.  (1)

The sequence of solutions (x(n), y(n)) with (x(0), y(0)) = (1, 0) are known to be C-recursive sequences (see [5]). It is proved there that the sequences (x(n)) and (y(n)) are C-recursive and can be represented as

x(n) = ⌊\frac{b^{n^{2}+2n} − x(1)b^{n^{2}+n}}{b^{2n} − 2x(1)b^{n} + 1} ⌋ mod b^{n},

y(n) = ⌊\frac{y(1)b^{n^{2}+n}}{b^{2n} − 2x(1)b^{n} + 1}⌋ mod b^{n}.

For k = 7, the fundamental solution is (x(1), y(1)) = (8, 3). If n ∈ ℤ^{+}, then

x(n) = (((−143^{n^{2}+2n} + 8 · 143^{n^{2}+n}) mod (143^{2n} − 16 · 143^{n} + 1)) mod 143^{n}) − 1,
y(n) = (((−3 · 64^{n^{2}+n}) mod (64^{2n} − 16 · 64^{n} + 1)) mod 64^{n}) − 1.

4.3 Degree 2, integers, negative constant term

In this subsection, we obtain formulas for two Lucas sequences that take positive and negative values. They are computed according to Remark 10.

Example 21. [Generalized Gaussian Fibonacci integers, OEIS \underline{A088137}] If n ∈ ℤ^{+}, then

t(n) = \frac{1}{9} ((3 · 91^{n^{2}+3n} − 5 · 91^{n^{2}+2n} + 6 · 91^{n^{2}+n}) mod (91^{3n} − 5 · 91^{2n} + 9 · 91^{n} − 9)) mod 91^{n})
− 3^{n+1}.

The div-mod representation works for c = 32 (see Prunescu and Sauras-Altuzarra [5]). The mod-mod representation works for r = 91, which is a spectacular difference.

Example 22. [OEIS \underline{A002249}] If n ∈ ℤ^{+}, then

s(n) = \frac{1}{4} (((4 · 21^{n^{2}+3n} − 7 · 21^{n^{2}+2n} + 6 · 21^{n^{2}+n}) mod (21^{3n} − 3 · 21^{2n} + 4 · 21^{n} − 4)) mod 21^{n})
− 2^{n+1}.

The div-mod representation works for c = 8 (see Prunescu and Sauras-Altuzarra [5]). The mod-mod representation works for r = 21, so we remark again a big difference.

4.4 Degree 3, natural numbers, negative constant term

We finally apply the theory to some C-recursive natural sequences of degree three, whose recursions do not contain positive coefficients. Consequently, these representations do not need correction terms.

Example 23. [Tribonacci numbers, OEIS \underline{A000073}] If n ∈ ℤ^{+}, then

s(n) = (2^{n^{2}+n} mod (2^{3n} − 2^{2n} − 2^{n} − 1)) mod 2^{n}.

Example 24. [Padovan numbers, OEIS \underline{A000931}] If n ∈ ℤ^{+}, then

s(n) = ((2^{n^{2}+3n} − 2^{n^{2}+n}) mod (2^{3n} − 2^{n} − 1)) mod 2^{n}.

Example 25. [Narayana’s cows sequence, OEIS \underline{A000930}] If n ∈ ℤ^{+}, then

s(n) = (2^{n^{2}+3n} mod (2^{3n} − 2^{2n} − 1)) mod 2^{n}.

5 Acknowledgments

We thank the anonymous referee for their careful reading and helpful suggestions.

References

[1] G. Everest, A. van der Poorten, I. Shparlinski, and T. Ward, Recurrence Sequences, Mathematical Surveys and Monographs, Vol. 104, American Mathematical Society, 2003.

[2] M. Kauers and P. Paule, The Concrete Tetrahedron, Texts and Monographs in Symbolic Computation, Springer, 2011.

[3] M. Petkovšek and H. Zakrajšek, Solving linear recurrence equations with polynomial coefficients, in J. Blümlein and C. Schneider, eds., Computer Algebra in Quantum Field Theory. Integration, Summation and Special Functions, Springer, 2013, pp. 259–284.

[4] M. Prunescu, On other two representations of the C-recursive integer sequences by terms in modular arithmetic, J. Symbolic Comput. 130 (2025).

[5] M. Prunescu and L. Sauras-Altuzarra, On the representation of C-recursive integer sequences by arithmetic terms, J. Difference Equ. Appl. 31 (2025), 1263–1285.

[6] R. P. Stanley, Enumerative Combinatorics, 2nd edition, Cambridge University Press, 2011.

2020 Mathematics Subject Classification: Primary 11B37; Secondary 39A06. Keywords: C-recursive sequence, modular arithmetic, term representation.

(Concerned with sequences \underline{A000032}, \underline{A000045}, \underline{A000051}, \underline{A000073}, \underline{A000129}, \underline{A000225}, \underline{A000930}, \underline{A000931}, \underline{A001080}, \underline{A001081}, \underline{A001477}, \underline{A002203}, \underline{A002249}, \underline{A007395}, and \underline{A088137}.)

Received March 11 2025; revised versions received March 12 2025; September 16 2025. Published in Journal of Integer Sequences, September 16 2025.

Return to Journal of Integer Sequences home page.