2025/02/24 by Mihai Prunescu, Joseph M. Shunia, Prunescu, Mihai +1 · 1 citation
Computer Science · #11B37 (primary) #39A06 (secondary) #Coding theory and cryptography #Computability, Logic, AI Algorithms #FOS: Mathematics #Number Theory (math.NT) #semigroups and automata theory
paper · pdf · doi:10.48550/arxiv.2502.16928
openalex publication_date 2025/02/24 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 mod-mod representation, consisting of two successive remainder computations. This result has two weaknesses: (i) the representation works only ultimately, and (ii) 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.