A Case Study in Meta-AUTOMATION: AUTOMATIC Generation of Congruence AUTOMATA For Combinatorial Sequences

By Eric Rowland and Doron Zeilberger


.pdf   .ps   .tex  


[Appeared in J. Difference Equations and Applications v. 20 (2014), 973-988.]


Written: Nov. 15, 2013
This article is a sequel to the beautiful article by Eric Rowland (the first-named author) and Reem Yassawi, presenting yet another approach to the fast determination of congruence properties of `famous' combinatorial sequences. The present approach can be taught to a computer, and our beloved servant, Shalosh B. Ekhad, was able to generate many new theorems, for famous sequences, of course, but also for many obscure ones!

In addition to the great interest of the actual theorems, (isn't it FASCINATING that the Motzkin numbers are NEVER divisible by 8?, and AMAZING that no Catalan number can ever give remainder 22 when it is divided by 256?), this project is yet another CASE STUDY in future mathematics, where the human does not waste his time proving new theorems, but teaches his bag of tricks to his friend the computer, who can prove much deeper theorems.


Maple Packages

Important: This article is accompanied by Maple packages

  • AutoSquared, a Maple package to automatically generate automata that enables one to determine super-fast, the congruence properties, modulo powers of prime (and hence, thanks to the Chinese Remainder Theorem, modulo any integer of famous combinatorial sequences like the Catalan, Motzkin, Delannoy, etc.etc. sequences.

  • CatalanCC, a Maple package that uses Congruence Automata to compute super-fast the remainder, upon dividing Catalan numbers by an integer m that is a divisor of
    26 33 52(7)(11)...(59)=2768774904222066200260800 .

  • CatalanLS, a Maple package that uses Congruence Linear Schemes to compute super-fast the remainder, upon dividing Catalan numbers by an integer m that is a divisor of
    23335372= 1323000 .

  • MotzkinCC, a Maple package that uses Congruence Automata to compute super-fast the remainder, upon dividing Motzkin numbers by an integer m that is a divisor of
    23 33 (5)(7)(11)...(29)=232908956280.

  • MotzkinLS, a Maple package that uses Congruence Linear Schemes to compute super-fast the remainder, upon dividing Motzkin numbers by an integer m that is a divisor of
    23 33 53 72 =1323000 .

  • DelannoyLS, a Maple package that uses Congruence Linear Schemes to compute super-fast the remainder, upon dividing the Central Delannoy numbers by an integer m that is a divisor of
    23 33 53 72 =1323000 .

Sample Input and Output for the Maple package AutoSquared

  • If you want to get a list of automata for the Catalan numbers, modulo 2,3,5, and 7, and their powers ≤ 3, where the max. size is 500, the
    the input gives the output.

  • If you want to get a list of automata for the Catalan numbers, modulo 2,3,5,7, and 11, and their powers ≤ 4, where the max. size is 1000, the
    the input gives the output.

  • If you want to get a list of Congruence Linear Schemes for the Catalan numbers, phrased in terms of the letter A, modulo 2,3,5, and 7, and their powers ≤ 4, where the max. size is 500, the
    the input gives the output.

  • If you want to get a list of Congruence Linear Schemes for the Catalan numbers, phrased in terms of the letter A, modulo powers of 2 up to 28
    the input gives the output.

  • If you want to get a list of automata for the Motzkin numbers, modulo 2,3,5, and 7, and their power and their powers ≤ 3 , where the max. size is 500, the where the max. size of the automata is 1000,
    the input gives the output.

  • If you want to get a list of automata for the Motzkin numbers, modulo 2,3,5, 7, and 11, and their power and their powers ≤ 4 , where the max. size of the automata is 1000,
    the input gives the output.

  • If you want to get a list of the Congruence Linear Schemes for the Motzkin numbers, modulo 2,3,5, and 7, and their power and their powers ≤ 3 , where the max. size of the automata is 1000,
    the input gives the output.

  • If you want to get a list of the Congruence Linear Schemes for the Motzkin numbers, modulo p2 for all primes from 2 to 29, owers ≤ 3 , where the max. size is 2000,
    the input gives the output.

  • If you want to get a list of automata for the Central Delannoy numbers, modulo 2,3,5, and 7, and their power and their powers < 3, where the max. size is 500, the where the max. size of the automata is 1000,
    the input gives the output.

  • If you want to get a list of Congruence Linear Schemes for the Central Delannoy numbers, modulo 2,3,5, and 7, and their power and their powers < 3, where the max. size is 500
    the input gives the output.

  • If you want to get automata for many sequences modulo 2,4,8,16,3,9,27,5,25 given by constant terms
    the input gives the output.

  • If you want to get Congruence Linear Schemes for many sequences modulo 2,4,8,16,3,9,27,5,25 given by constant terms
    the input gives the output.

  • If you want to get a webbook with HUNDREDS of exciting theorems about automatic p-schemes for even more sequences modulo 2,4,8,16,3,9,27,5,25 given by constant terms
    the input gives the output.

  • If you want to get THOUSANDS of exciting theorems about Congruence Linear Schemes, for many combinatorial sequences modulo 2,4,8,16,3,9,27,5,25 given by constant terms
    the input gives the output.

  • If you want to get Congruence Automata for the Zeta-2 Apery numbers for the moduli 2,4,8,3,9, 5,25
    the input gives the output.

  • If you want to get Congruence Linear Schemes for the Zeta-2 Apery numbers for the moduli 2,4,8,3,9, 5,25
    the input gives the output.

  • If you want to get Congruence Automata for the (usual, Zeta(3)) Apery numbers for the moduli 2,4,8,3,9, 5,25
    the input gives the output.

  • If you want to get Congruence Linear Schemes for the (usual, Zeta(3)) Apery numbers for the moduli 2,4,8,16,32
    the input gives the output.

  • If you want to get Congruence Automata for the Catalan numbers for the moduli 2,4,8,16,32,64,128, and 256, and the avoided congruence classes
    the input gives the output.

  • If you want to get Congruence Linear Schemes for the Catalan numbers for the moduli 2,4,8,16,32,64,128, and 256, and the avoided congruence classes
    the input gives the output.

  • If you want to get Congruence Linear Schemes for the Motzkin numbers for the moduli 2,4,8,16,32,64, and 128, and the avoided congruence classes
    the input gives the output.

Sample Input and Output for the Maple package CatalanCC

  • If you want to see the Catalan numbers from googol to googol plus a thousand modulo 221
    the input gives the output.
    (as you can see they are all zero!)

Sample Input and Output for the Maple package CatalanLS

  • If you want to see the Catalan numbers from 5100 to 5100 plus a thousand modulo 1000 (i.e. the last three digits), the
    the input gives the output.

  • If you want to see the 5100 -th number mod 1000 (i.e. the last three digits), the
    the input gives the output.

Sample Input and Output for the Maple package MotzkinCC

  • If you want to see the Motzkin numbers from googol to googol plus a thousand modulo 221
    the input gives the output.

Sample Input and Output for the Maple package MotzkinLS

  • If you want to see the Motzkin numbers from 1030 to 1030+1000 modulo 1000 (i.e. the last three digits), the
    the input gives the output.

  • If you want to see the googol-th Motzkin number mod 1000, (i.e. the last three digits) (it is 187) the
    the input gives the output.

Sample Input and Output for the Maple package DelannoyLS

  • If you want to see the Central Delannoy numbers from 1030 to 1030 plus a thousand modulo 1000 (i.e. the last three digits), the
    the input gives the output.

  • If you want to see the googol-th Central Delannoy number mod 1000 (i.e. the last three (decimal) digits) (it is 281), the
    the input gives the output.

Doron Zeilberger's List of Papers

Doron Zeilberger's Home Page