On the period mod m of polynomially-recursive sequences: a case study

MaRDI QIDQ5236571zbMATH OpenFDO

Authors Cyril Banderier, Florian Luca

Publication date 9 October 2019

Full work available at URL https://arxiv.org/abs/1903.01986, https://cs.uwaterloo.ca/journals/JIS/VOL22/Banderier/band3.html

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

D-finite functionquadratic residuesupercongruenceCarmichael functionWieferich primeP-recursive sequencemodular property

Mathematics Subject Classification ID

Exact enumeration problems, generating functions (05A15) Fibonacci and Lucas numbers and polynomials and generalizations (11B39) Sequences (mod (m)) (11B50) Automata sequences (11B85)

Abstract: Polynomially-recursive sequences generally have a periodic behavior mod $m$. In this paper, we analyze the period mod $m$ of a second order polynomially-recursive sequence. The problem originally comes from an enumeration of avoiding pattern permutations and appears to be linked with nice number theory notions (the Carmichael function, Wieferich primes, algebraic integers). We give the mod $a^k$ supercongruences, and generalize these results to a class of recurrences.

Recommendations

• Recursive sequences and polynomial congruences
• scientific article; zbMATH DE number 1222507
• scientific article; zbMATH DE number 17602
• Linear recurrence sequences over a finite field: theory and applications
• Periodicity of some recurrence sequences modulo \(m\)

Cites work

• scientific article; zbMATH DE number 3880787 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 872231 (Why is no real title available?)
• A \(q\)-microscope for supercongruences
• A case study in meta-automation: automatic generation of congruence automata for combinatorial sequences
• A method for determining the mod-\(2^k\) behaviour of recursive sequences, with applications to subgroup counting
• A short approach to Catalan numbers modulo 2r
• Analytic combinatorics
• Carmichael's lambda function
• Congruences for Catalan and Motzkin numbers and related sequences
• Gaussian hypergeometric series and supercongruences
• On integrality and periodicity of the Motzkin numbers
• Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer
• Right-jumps and pattern avoiding permutations
• Supercongruences for polynomial analogs of the Apéry numbers
• Symmetric functions and P-recursiveness

Cited in

(3)

• scientific article; zbMATH DE number 653399 (Why is no real title available?)
• scientific article; zbMATH DE number 1222507 (Why is no real title available?)
• MC-finiteness of restricted set partition functions

Describes a project that uses

Uses Software

• DelannoyLS
• MotzkinCC
• CatalanCC
• AutoSquared
• OEIS

This page was built for publication: On the period mod \(m\) of polynomially-recursive sequences: a case study

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5236571)