Journal of Integer Sequences, Vol. 22 (2019), Article 19.5.2

On the Period mod m of Polynomially-Recursive Sequences: a Case Study

Cyril Banderier
Laboratoire d'Informatique de Paris Nord
Université de Paris Nord
93430 Villetaneuse

Florian Luca
School of Mathematics
University of the Witwatersrand
Wits 2050, Johannesburg
South Africa
Research Group of Algebraic Structures and Applications
King Abdulaziz University
21589 Jeddah
Saudi Arabia
Centro de Ciencias Matemáticas
Universidad Nacional Autónoma de México (UNAM)
58089 Morelia


Polynomially-recursive sequences have a periodic behavior mod m, when the leading coefficient of the corresponding recurrence is invertible mod m. In this paper, we analyze the period mod m of a class of second-order polynomially-recursive sequences. Starting with a problem originally coming from an enumeration of avoiding pattern permutations, we give a generalization which appears to be linked with nice elementary number theory notions (the Carmichael function, algebraic integers, quadratic residues, Wieferich primes).

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A123692 A265165 A306699.)

Received March 11 2019; revised versions received March 23 2019; July 25 2019; August 6 2019. Published in Journal of Integer Sequences, August 19 2019.

Return to Journal of Integer Sequences home page