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
France

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

Abstract:

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