\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{amsmath} \usepackage{amsthm} \usepackage{amsfonts} \usepackage{amscd} \usepackage{graphicx} \usepackage[colorlinks=true, linkcolor=webgreen, filecolor=webbrown, citecolor=webgreen]{hyperref} \definecolor{webgreen}{rgb}{0,.5,0} \definecolor{webbrown}{rgb}{.6,0,0} \usepackage{color} \usepackage{fullpage} \usepackage{float} \usepackage{psfig} \usepackage{graphics} \usepackage{latexsym} \usepackage{epsf} \usepackage{breakurl} \setlength{\textwidth}{6.5in} \setlength{\oddsidemargin}{.1in} \setlength{\evensidemargin}{.1in} \setlength{\topmargin}{-.1in} \setlength{\textheight}{8.4in} \newcommand{\seqnum}[1]{\href{https://oeis.org/#1}{\rm \underline{#1}}} \DeclareMathOperator\sgn{sgn} \newcommand{\abs}[1]{\left| #1 \right|} \newcommand{\floor}[1]{\left\lfloor #1 \right\rfloor} \newcommand{\ceil}[1]{\left\lceil #1 \right\rceil} \newcommand{\Z}{\mathbb{Z}} \newcommand{\ahref}[2]{\href{#1}{\rm #2}} \begin{document} \theoremstyle{plain} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \theoremstyle{definition} \newtheorem{definition}[theorem]{Definition} \newtheorem{example}[theorem]{Example} \newtheorem{question}[theorem]{Question} \newtheorem{observation}[theorem]{Observation} \newtheorem{openprob}[theorem]{Open Problem} \theoremstyle{remark} \newtheorem{remark}[theorem]{Remark} \newtheorem{note}[theorem]{Note} \begin{center} \epsfxsize=4in \leavevmode\epsffile{logo129.eps} \end{center} \begin{center} \vskip 1cm{\LARGE\bf On Modular Representations of \\ \vskip .1in C-Recursive Integer Sequences } \vskip 1cm 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\\ \href{mailto:mihai.prunescu@imar.ro}{\tt mihai.prunescu@imar.ro} \\ \href{mailto:mihai.prunescu@gmail.com}{\tt mihai.prunescu@gmail.com} \\ \bigskip J.~M.~Shunia\\ Independent Researcher\\ Ann Arbor, MI\\ USA\\ \href{mailto:jshunia@gmail.com}{\tt jshunia@gmail.com}\\ \end{center} \vskip .2 in \begin{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 \geq 1$. Using a different approach, Prunescu proved the existence of two other representations, one of which is the mod-mod 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 \geq 1$. This follows directly from the div-mod representation by an arithmetic short-cut from outside. \end{abstract} \section{Introduction}\label{SectionIntroduction} The \textit{C-recursive sequences of order $d$} are sequences $t:\mathbb N \rightarrow \mathbb C$ satisfying a relation of recurrence with constant coefficients $$ t(n+d) + \alpha_1 t(n+d-1) + \dots + \alpha_{d-1} t(n+1) + \alpha_d t(n) = 0 $$ for all $n \in \mathbb{N}$, with $\alpha_d \neq 0$. With the recurrence rule, we associate the polynomial $$ B(X):= 1 + \alpha_1 X + \dots + \alpha_d X^d . $$ Observe that $\deg B = d$. We let $\tilde{B}(X)$ denote the {\it reciprocal polynomial} $$\tilde{B}(X) = X^dB(X^{-1})= X^d + \alpha_1X^{d-1} + \dots + \alpha_d .$$ According to \cite[Theorem 4.1.1]{stanley} and \cite[Theorem 1]{PetkovsekZakrajsek}, the C-recursive sequences are exactly the sequences $(s(n))$ such that the generating function $$f(X) = \sum_{n \geq 0} t(n) X^n$$ is a rational function $A(X)/B(X)$ with $\deg(A):= k < \deg(B) = d$. We define $\tilde{A}(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} \cdot \frac{\tilde{A}(X)}{\tilde{B}(X)} .$$ Prunescu and Sauras-Altuzarra proved \cite{prunescusauras2024representationcrecursive} that if $f$ is the generating function of a sequence consisting of natural numbers only, then there exists $c \in \mathbb{N}$ such that for all $n \in \Z^+$, we have \begin{align*} t(n) = \floor{ c^{n^2} f(c^{-n}) } \bmod c^n . \end{align*} The exact statement will be given below (see Theorem \ref{ThmExtraction1}). In brief, if the sequence is C-recurrent, its generating function $f$ is a rational function $A(X) / B(X)$ with $A(X), \, B(X) \in \mathbb Z[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 {\it div-mod representation} \begin{align*} t(n) = \floor{ \frac{c^{n^2 + dn} A(c^{-n})}{c^{dn} B(c^{-n})} } \bmod c^n = \floor{ \frac{c^{n^2} c^{n(d-k)} \tilde A(c^{n})}{ \tilde B(c^n)} } \bmod c^n . \end{align*} We note that ``\textit{div-mod}'' refers to the successive application of an integer division and a modular reduction. Prunescu proved in \cite{prunescu2024representationscrecursive} the following \textit{mod-mod representation}. Let $\alpha_d \not= 0$ be the constant term of the recurrence rule for a C-recursive sequence, i.e., the constant term of $\tilde B(X)$. Then there are $c, \, n_0 \in \mathbb N$ such that for $n \geq n_0$ we have \begin{align*} t(n) = \frac{\left( \left( c^{n(d-1)+\ceil{n/2}} - \sgn(\alpha_d) \cdot c^{n^2} c^{n(d-k)} \tilde A(c^n) \right) \bmod \tilde B(c^n) \right) \bmod c^n}{|\alpha_d|} . \end{align*} This representation has the advantage that $$(c^{n(d-1)+\ceil{n/2}} - \sgn(\alpha_d) \cdot c^{n^2} c^{n(d-k)} \tilde A(c^n)) \bmod \tilde B(c^n)$$ can be computed faster by modular arithmetic, but it has two disadvantages: \begin{enumerate} \item[(i)] It needs in general a correction term $c^{n(d-1)+\ceil{n/2}}$ in the innermost exponential polynomial. \item[(ii)] It holds only ultimately, for $n$ greater than or equal to some a priori undetermined $n_0 \in \mathbb{N}$. 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$. \end{enumerate} In the following we show that this result can be improved. {\it If the constant term of $\tilde B(X)$ is $\alpha_d \neq 0$, there exists an integer $r \geq c$ such that the following holds for all $n \geq 1$}: \begin{align*} t(n) = \frac{-1 -\sgn(\alpha_d)}{2} + \frac{1}{|\alpha_d|} \left( \left( (- \sgn (\alpha_d) \cdot r^{n^2} r^{n(d-k)} \tilde A(r^n)) \bmod \tilde B(r^n) \right) \bmod r^n \right). \end{align*} Observe that this representation does not contain any correction term and works for $n \geq 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 \cite{kauerspaule}. \section{Technical preparations}\label{SectionPrerequisites} We define $\mathbb{N}$ 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.\ \cite{everestandal}. \begin{lemma}\label{LemmaGeneralInequality} [Prunescu \& Sauras-Altuzarra, \cite[Lemma 4]{prunescusauras2024representationcrecursive}] If $t:\mathbb{N} \rightarrow {\mathbb{C}} $ is C-recursive, then there is an integer $ g \geq 1 $ such that $ | t(n) | < g^{n+1} $ for every integer $ n \geq 0 $. \end{lemma} \begin{theorem}\label{ThmExtraction1} [Prunescu \& Sauras-Altuzarra, \cite[Theorems 1 and 2]{prunescusauras2024representationcrecursive}] If $t:\mathbb N \rightarrow \mathbb{N} $, $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 \geq 2 $, $ n \geq m \geq 2 $, $ c^{- m} < R $, and $ t ( n ) < c^{n - 2} $ for every integer $ n \geq m $, then $$t(n) = \floor{ c^{n^2} f ( c^{- n} ) } \bmod c^n . $$ Also, if $ c \geq 8 $, $c^{-1} < R$, and $ t ( n ) < c^{n / 3} $ for every $ n \geq 1 $, then the representation works for every $n \geq 1$. \end{theorem} The following corollary follows easily from Theorem \ref{ThmExtraction1}. \begin{corollary}\label{CorBiggerBase} If the representation stated in Theorem \ref{ThmExtraction1} holds for some $c \in \mathbb N$ for all $n \geq m$, then it holds also if we replace $c$ with any integer $r \geq c$ for all $n \geq m$. \end{corollary} The next three lemmas are easy remarks of modular arithmetic. \begin{lemma} \label{lemma1} If $B \geq 2$, $A \geq 1$, $B \nmid A$, then $- \floor{-A/B} = \floor{A/B} + 1$. \end{lemma} \begin{lemma} \label{lemma2} If $a, \, y, \, C \in \mathbb{N}$ and $0 \leq (a y) < C$, then $\left( (ay) \bmod C\right) = a ( y \bmod C )$. \end{lemma} \begin{lemma} \label{lemma3} If $x, \, C \in \mathbb N $, $C \geq 2$, $x \not\equiv (C-1) \pmod{C}$, then $(x+1) \bmod C = (x \bmod C) + 1$. \end{lemma} The next lemma is the principal tool of this note. \begin{lemma} \label{LemmaMain} Let $a, \, A, \, B, \, C \in \mathbb{Z}$ such that $A, \, B > 0$, $C \geq 2$, $C \,|\,A$, $B \nmid A$, $B \bmod C \equiv a \bmod C$, $a \not= 0$, and $|a| (\floor{A / B} \bmod C) < C$ if $a < 0$ (respectively, $a + a (\floor{A / B} \bmod C) < C$ if $a > 0$). \begin{enumerate} \item[(i)] If $a < 0$, then \begin{align*} (A \bmod B) \bmod C = |a| (\floor{A / B} \bmod C) . \end{align*} \item[(ii)] If $a > 0$, then \begin{align*} \left( (-A) \bmod B \right) \bmod C = a (1 + \floor{A/B} \bmod C ) . \end{align*} \end{enumerate} \end{lemma} \begin{proof} For both cases below we apply Lemmas \ref{lemma1} and \ref{lemma2}. For the second case we apply also Lemma \ref{lemma3}. We proceed with the cases. \begin{enumerate} \item[(i)] $a < 0$: \begin{align*} (A \bmod B) \bmod C &= \left( A \bmod C - (B \bmod C) ( \floor{A / B} \bmod C) \right) \bmod C \\ &= \left( 0 - (- |a| ) ( \floor{A / B} \bmod C) \right) \bmod C \\ &= \left( |a| ( \floor{A / B} \bmod C) \right) \bmod C \\ &= |a| ( \floor{A / B} \bmod C ) . \end{align*} \item[(ii)] $a > 0$: \begin{align*} \left( (-A) \bmod B \right) \bmod C &= \left( (-A) \bmod C - (B \bmod C) ( \floor{A / B} \bmod C) \right) \bmod C \\ &= \left( 0 - a ( \floor{(-A) / B} \bmod C) \right) \bmod C \\ &= ( a \cdot ( - \floor{(-A) / B} \bmod C ) ) \bmod C \\ &= ( a \cdot (1 + \floor{A / B} \bmod C ) ) \bmod C \\ &= ( a + a \floor{A / B} \bmod C ) \bmod C \\ &= a ( 1 + \floor{A / B} \bmod C ) . \qedhere \end{align*} \end{enumerate} \end{proof} \section{Applications to C-recursive sequences}\label{SectionApplications} \begin{theorem}\label{TheoApplication} Suppose that for all natural numbers $n \geq 1$, a sequence $t:\mathbb N \rightarrow \mathbb N$ has the div-mod representation \begin{align*} t(n) = \floor{\frac{c^{n^2} c^{n(d-k)} \tilde A(c^n)}{\tilde B(c^n)}} \bmod c^n . \end{align*} If the constant term of $\tilde B(X)$ is $\alpha_d < 0$, then there is some natural number $r$ such that for all $n \geq 1$ we have \begin{align*} t(n) = \frac{1}{|\alpha_d|} \left(\left((r^{n^2} r^{n(d-k)} \tilde A(r^n)) \bmod \tilde B(r^n) \right) \bmod r^n \right). \end{align*} If the constant term of $\tilde B(X)$ is $\alpha_d > 0$, then there is some natural number $r$ such that for all $n \geq 1$ we have \begin{align*} t(n) = -1 + \frac{1}{\alpha_d} \left( \left( (- r^{n^2} r^{n(d-k)} \tilde A(r^n)) \bmod \tilde B(r^n) \right) \bmod r^n \right). \end{align*} \end{theorem} \begin{proof} In order to apply Lemma \ref{LemmaMain}, we recall that according to Corollary \ref{CorBiggerBase} there is a $c_0 \in \mathbb N$ such that for all $r \geq c_0$ and for all $n \geq 1$ we have \begin{align*} t(n) = \floor{\frac{r^{n^2} r^{n(d-k)}\tilde A(r^n)}{\tilde B(r^n)}} \bmod r^n . \end{align*} Let $r \geq 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)} \tilde A(r^n)$, $B = \tilde 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 \ref{LemmaMain}. The conditions $C \,|\,A$ and $B \nmid A$ are always fulfilled. The conditions $A, B > 0$ and $C \geq 2$ are fulfilled for all $n \geq 1$ if $r$ is sufficiently large, as the main coefficients of $\tilde A(X)$ and $\tilde B(X)$ are positive. Let $\alpha_d$ be the constant term of the polynomial $\tilde B(X) = X^d B(\frac{1}{X})$, meaning that $a = \alpha_d$. For $r$ sufficiently large, we have $B \equiv \alpha_d$ (mod $C$). By definition, we have $\alpha_d \neq 0$ because $\deg (B) = \deg (\tilde B) = d$. We have to show that for $r$ sufficiently large, $|\alpha_d| (\floor{A / B} \bmod C) < C$ if $\alpha_d < 0$ respectively $\alpha_d + \alpha_d (\floor{A / B} \bmod C) < C$ if $\alpha_d > 0$, for all $n \geq 1$. We recall that $\floor{A/B} \bmod C = t(n)$. If $\alpha_d < 0$, the inequality $|\alpha_d| (\floor{A / B} \bmod C) < C$ means that $|\alpha_d| t(n) < r^n$ and must be true for $n \geq 1$. If $\alpha_d > 0$, the inequality $\alpha_d + \alpha_d (\floor{A / B} \bmod C) < C$ means that $\alpha_d (t(n) + 1) < r^n$ and must be true for $n \geq 1$. But we know from \ref{LemmaGeneralInequality} that if $s: \mathbb N \rightarrow \mathbb C$ is a C-recursive sequence, then there exists a $g \in \mathbb N$ such that for all $n \in \mathbb N$ we have $|s(n)| < g^{n+1}$. As $s(n) = 2|\alpha_d| t(n)$ is itself a C-recursive sequence and its values are natural numbers, there is some positive $g \in \mathbb N$ such that $2|\alpha_d| t(n) < g^{n+1}$ for all $n \geq 1$. We can always find an $r \in \mathbb N$ such that $g^{n+1} < r^n$ for all $n \geq 1$. If $t(n) \geq 1$, as $2|\alpha_d| t(n) > |\alpha_d| t(n)$ in the first case, respectively $2 |\alpha_d| t(n) \geq |\alpha_d|(1 + t(n)) $ in the second case, the conditions of Lemma \ref{LemmaMain} are fulfilled. If $t(n) = 0$, the conditions are fulfilled for every $r \geq 1$ in the first case and for every $r > \alpha_d$ in the second case. Finally we choose $r$ sufficiently large such that $r \geq c_0$ and all the conditions above are fulfilled.\qedhere \end{proof} Below we put both cases in only one formula. \begin{corollary}\label{CorOneFormula} Suppose that for all natural numbers $n \geq 1$, a sequence $t:\mathbb N \rightarrow \mathbb N$ has the representation \begin{align*} t(n) = \floor{\frac{c^{n^2} c^{n(d-k)} \tilde A(c^n)}{\tilde B(c^n)}} \bmod c^n . \end{align*} If the constant term of $\tilde B(X)$ is $\alpha_d \neq 0$, there exists an integer $r \geq c$ such that, for all $n \geq 1$, one has \begin{align*} t(n) = \frac{-1 -\sgn(\alpha_d)}{2} + \frac{1}{|\alpha_d|} \left( \left( (- \sgn (\alpha_d) \cdot r^{n^2} r^{n(d-k)} \tilde A(r^n)) \bmod \tilde B(r^n) \right) \bmod r^n \right). \end{align*} \end{corollary} \begin{remark}\label{oscillant} \rm In \cite{prunescu2024representationscrecursive} there is also an application to C-recursive sequences $t:\mathbb N \rightarrow \mathbb Z$. According to Lemma \ref{LemmaGeneralInequality}, for such a sequence there is an $h \in \mathbb N$ such that for all $n \geq 0$ we have $|t(n)| < h^{n+1}$. The sequence $s(n) = t(n) + h^{n+1}$ has values in $\mathbb N$ 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 \ref{CorOneFormula}, while the sequence $t$ has the representation $t(n) = s(n) - h^{n+1}$. \end{remark} In \cite{prunescu2024representationscrecursive}, also the following {\it mod-div representation} is proved: {\it There exist $c, \, n_0 \in \mathbb N$ such that for all $n\geq n_0$ we have} \begin{align*} t(n) = \left \lfloor \frac{\left ( c^{n(d-2) + \left \lceil n/2 \right \rceil} + c^{n^2} c^{n(d-k)} \tilde A(c^n ) \right ) \bmod \tilde B(c^n)}{c^{n(d-1)}} \right \rfloor . \end{align*} \begin{openprob} 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? \end{openprob} \section{Examples}\label{SectionExamples} In this section, all representations are derived from the respective representations in \cite{prunescusauras2024representationcrecursive}. In some cases a larger exponentiation base $e > c$ is needed in order to keep the representation true for all natural numbers $n \geq 1$. \subsection{Degree 2, natural numbers, negative constant term} The first group of examples consists of sequences of order $2$ with $a < 0$. As in \cite{prunescu2024representationscrecursive} 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 {\it On-Line Encyclopedia of Integer Sequences}. \begin{example} \label{ExFibonacci} [\textit{Fibonacci numbers}, OEIS \seqnum{A000045}] For all $n \in \Z^+$, we have $$s(n) = \left( 3^{n^2 + n} \bmod (3^{2n} - 3^n - 1) \right) \bmod 3^n .$$ \end{example} \begin{example} \label{PropFormulaLucas} [\textit{Lucas numbers}, OEIS \seqnum{A000032}] The div-mod representation works for $c = 3$ (see Prunescu and Sauras-Altuzarra \cite{prunescusauras2024representationcrecursive}). The mod-mod representation works for $r = 5$: For all $n \in \Z^+$, we have $$s(n) = \left( ( 2 \cdot 5^{n^2 + 2n} - 5^{n^2 + n}) \bmod (5^{2n} - 5^n - 1) \right) \bmod 5^n .$$ \end{example} \begin{example} \label{PropFormulaPellNumbers} [\textit{Pell numbers}, OEIS \seqnum{A000129}] For all $n \in \Z^+$, we have $$s(n) = \left( 3^{n^2 + n} \bmod (3^{2n} - 2 \cdot 3^n - 1) \right) \bmod 3^n .$$ \end{example} \begin{example} \label{PropFormulaPellLucasNumbers} [\textit{Pell-Lucas numbers}, OEIS \seqnum{A002203}] For all $n \in \Z^+$, we have $$s(n) = \left( ( 2 \cdot 9^{n^2 + 2n} - 2 \cdot 9^{n^2 + n}) \bmod (9^{2n} - 2 \cdot 9^n - 1) \right) \bmod 9^n .$$ \end{example} \subsection{Degree 2, natural numbers, positive constant term} \begin{example}\label{PropFormulaNaturals}[\textit{Natural numbers}, OEIS \seqnum{A001477}] For all $n \in \Z^+$, we have $$\left( \left( (- 4^{n^2 + n} ) \bmod (4^{2n} - 2 \cdot 4^n + 1) \right) \bmod 4^n \right) - 1 = n .$$ \end{example} \begin{example}\label{PropFormulaAllTwos} [\textit{All-twos}, OEIS \seqnum{A007395}] For all $n \in \Z^+$, we have $$\left( \left( (-2 \cdot 4^{n^2 + 2n} + 2 \cdot 4^{n^2 + n} ) \bmod ( 4^{2n} - 2 \cdot 4^n + 1 ) \right) \bmod 4^n \right) -1 = 2 .$$ \end{example} \begin{example}\label{PropFormulaMersenne} [\textit{Mersenne numbers}, OEIS \seqnum{A000225}] For all $n \in \Z^+$, we have $$\frac{1}{2} \cdot \left ( \left( (- 6 ^ {n ^ 2 + n} ) \bmod (6 ^ {2n} - 3 \cdot 6 ^ n + 2 ) \right) \bmod 6^n \right ) -1 = 2^n - 1 .$$ \end{example} \begin{example} \label{PropFormula2tonplusone} [$2^n + 1$, OEIS \seqnum{A000051}] The div-mod representation works for $c = 6$ (see Prunescu and Sauras-Altuzarra \cite{prunescusauras2024representationcrecursive}). The mod-mod representation works for $r = 9$: For all $n \in \Z^+$, we have $$\frac{1}{2} \cdot \left ( ( - 2 \cdot 9^{n^2 + 2n} + 3 \cdot 9^{n^2 + n} ) \bmod ( 9^{2n} -3 \cdot 9^n + 2 ) \bmod 9^n \right ) -1 = 2^n + 1 .$$ \end{example} \begin{example} \label{PropA001081} [OEIS \seqnum{A001081}, OEIS \seqnum{A001080}] Consider Pell's equation \begin{align} \label{EqPells} X^2 - k Y^2 = 1 . \end{align} The sequence of solutions $(x(n), y(n))$ with $(x(0), y(0)) = (1,0)$ are known to be C-recursive sequences (see \cite{prunescusauras2024representationcrecursive}). It is proved there that the sequences $(x(n))$ and $(y(n))$ are C-recursive and can be represented as $$x(n) = \left \lfloor \frac{b^{n^2 + 2n} - x(1) b^{n^2 + n}}{b^{2n} - 2 x(1) b^n + 1} \right \rfloor \bmod b^n,$$ $$y(n) = \left \lfloor \frac{y(1) b^{n^2 + n}}{b^{2n} - 2 x(1) b^n + 1} \right \rfloor \bmod b^n.$$ For $k = 7$, the fundamental solution is $(x(1), y(1)) = (8,3)$. If $n \in \Z^+$, then \begin{align*} x(n) &= \left( \left( (- 143 ^ {n ^ 2 + 2n} +8 \cdot 143 ^ {n ^ 2 + n} ) \bmod(143 ^ {2n} -16 \cdot 143 ^ n + 1 ) \right) \bmod 143 ^ n \right) - 1 , \\ y(n) &= \left( \left( ( -3 \cdot 64 ^ {n ^ 2 + n} ) \bmod (64 ^ {2n} -16 \cdot 64 ^ n + 1 ) \right) \bmod 64 ^ n\right) - 1 . \end{align*} \end{example} \subsection{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 \ref{oscillant}. \begin{example} \label{PropGeneralizedGaussianFibonacci} [\textit{Generalized Gaussian Fibonacci integers}, OEIS \seqnum{A088137}] If $n \in \Z^+$, then \small{ \begin{align*} t(n) =\, &\frac{1}{9}\left( \left (3 \cdot 91^{n^2 + 3n} - 5 \cdot 91^{n^2 + 2n} + 6 \cdot 91^{n^2 + n}) \bmod ({91^{3n} - 5\cdot 91^{2n} + 9 \cdot 91^n - 9}) \right ) \bmod 91^n \right ) \\ &- 3^{n+1}. \end{align*} } \normalsize The div-mod representation works for $c = 32$ (see Prunescu and Sauras-Altuzarra \cite{prunescusauras2024representationcrecursive}). The mod-mod representation works for $r = 91$, which is a spectacular difference. \end{example} \begin{example} \label{PropA002249} [OEIS \seqnum{A002249}] If $n \in \Z^+$, then \small{ \begin{align*} s(n) =\, &\frac{1}{4}\left ( \left( (4 \cdot 21^{n^2 + 3n} - 7 \cdot 21^{n^2 + 2n} + 6 \cdot 21^{n^2 + n}) \bmod (21^{3n} - 3\cdot 21^{2n} + 4 \cdot 21^n - 4) \right ) \bmod 21^n \right ) \\ &- 2^{n+1}. \end{align*} } \normalsize \end{example} The div-mod representation works for $c = 8$ (see Prunescu and Sauras-Altuzarra \cite{prunescusauras2024representationcrecursive}). The mod-mod representation works for $r = 21$, so we remark again a big difference. \subsection{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. \begin{example} \label{PropTribonacci} [\textit{Tribonacci numbers}, OEIS \seqnum{A000073}] If $n \in \Z^+$, then $$ s(n) = \left (2^{n^2 + n} \bmod (2^{3n} - 2^{2n} - 2^n - 1) \right ) \bmod 2^n . $$ \end{example} \begin{example} \label{PropPadovan} [\textit{Padovan numbers}, OEIS \seqnum{A000931}] If $n \in \Z^+$, then $$ s(n) = \left ( (2^{n^2 +3 n} - 2^{n^2 + n} ) \bmod (2^{3n} - 2^n - 1) \right ) \bmod 2^n . $$ \end{example} \begin{example} \label{PropNarayana} [\textit{Narayana's cows sequence}, OEIS \seqnum{A000930}] If $ n \in \Z^+$, then $$ s(n) = \left ( 2^{n^2 +3 n} \bmod (2^{3n} - 2^{2n} - 1) \right ) \bmod 2^n .$$ \end{example} \section{Acknowledgments} We thank the anonymous referee for their careful reading and helpful suggestions. \begin{thebibliography}{9} \bibitem{everestandal} G. Everest, A. van der Poorten, I. Shparlinski, and T. Ward, {\it Recurrence Sequences}, Mathematical Surveys and Monographs, Vol.~104, American Mathematical Society, 2003. \bibitem{kauerspaule} M. Kauers and P. Paule, {\it The Concrete Tetrahedron}, Texts and Monographs in Symbolic Computation, Springer, 2011. \bibitem{PetkovsekZakrajsek} M. Petkov\v{s}ek and H. Zakraj\v{s}ek, Solving linear recurrence equations with polynomial coefficients, in J. Bl\"umlein and C. Schneider, eds., {\it Computer Algebra in Quantum Field Theory. Integration, Summation and Special Functions}, Springer, 2013, pp.\ 259--284. \bibitem{prunescu2024representationscrecursive} M. Prunescu, On other two representations of the C-recursive integer sequences by terms in modular arithmetic, {\it J. Symbolic Comput.} {\bf 130} (2025). \bibitem{prunescusauras2024representationcrecursive} M. Prunescu and L. Sauras-Altuzarra, On the representation of C-recursive integer sequences by arithmetic terms, {\it J. Difference Equ. Appl.} {\bf 31} (2025), 1263--1285. \bibitem{stanley} R. P. Stanley, {\it Enumerative Combinatorics}, 2nd edition, Cambridge University Press, 2011. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2020 {\it Mathematics Subject Classification}: Primary 11B37; Secondary 39A06. \noindent \emph{Keywords: } C-recursive sequence, modular arithmetic, term representation. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000032}, \seqnum{A000045}, \seqnum{A000051}, \seqnum{A000073}, \seqnum{A000129}, \seqnum{A000225}, \seqnum{A000930}, \seqnum{A000931}, \seqnum{A001080}, \seqnum{A001081}, \seqnum{A001477}, \seqnum{A002203}, \seqnum{A002249}, \seqnum{A007395}, and \seqnum{A088137}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received March 11 2025; revised versions received March 12 2025; September 16 2025. Published in {\it Journal of Integer Sequences}, September 16 2025. \bigskip \hrule \bigskip \noindent Return to \href{https://cs.uwaterloo.ca/journals/JIS/}{Journal of Integer Sequences home page}. \end{document}