Effective MC-finiteness

Abstract

An integer sequence $(a_n{)}_{n\in \mathbb{N}}$ is \emph{MC-finite} if for all $m$, the sequence $a_n\mathrm{mod}m$ is eventually periodic. There are MC-finite sequences $(a_n{)}_{n\in \mathbb{N}}$ such that the function $F:(m,n)\mapsto a_n\mathrm{mod}m$ is not computable. In \cite{filmus2023mc} we presented concrete examples of MC-finite sequences taken from the Online Encyclopedia of Integer Sequences (OEIS) without discussing the computability of $F$. In this paper we discuss cases when this $F$ is effectively computable.

12 pages