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

zbMATH Open1460.11025arXiv1903.01986MaRDI QIDQ5236571FDOQ5236571

Authors: Cyril Banderier, Florian Luca 

Publication date: 9 October 2019

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.

Full work available at URL: https://arxiv.org/abs/1903.01986

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

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\)

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)

Cites Work

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

Cited In (3)

• Title not available (Why is that?)
• Title not available (Why is that?)
• MC-finiteness of restricted set partition functions

Uses Software

• OEIS
• AutoSquared
• CatalanCC
• MotzkinCC
• DelannoyLS

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)