.pdf
.ps
.tex
[Appeared in J. Difference Equations and Applications v. 20 (2014), 973988.]
Written: Nov. 15, 2013
This article is a sequel to the
beautiful article by Eric Rowland (the firstnamed 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
superfast, 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 superfast the remainder, upon dividing Catalan numbers by an
integer m that is a divisor of
2^{6} 3^{3} 5^{2}(7)(11)...(59)=2768774904222066200260800 .
 CatalanLS,
a Maple package that uses Congruence Linear Schemes to compute superfast the remainder, upon dividing Catalan numbers by an
integer m that is a divisor of
2^{3}3^{3}5^{3}7^{2}= 1323000
.
 MotzkinCC,
a Maple package that uses Congruence Automata to compute superfast the remainder, upon dividing Motzkin numbers by an
integer m that is a divisor of
2^{3} 3^{3} (5)(7)(11)...(29)=232908956280.
 MotzkinLS,
a Maple package that uses Congruence Linear Schemes to compute superfast the remainder, upon dividing Motzkin numbers by an
integer m that is a divisor of
2^{3} 3^{3} 5^{3} 7^{2} =1323000 .
 DelannoyLS,
a Maple package that uses Congruence Linear Schemes to compute superfast the remainder, upon dividing
the Central Delannoy numbers by an
integer m that is a divisor of
2^{3} 3^{3} 5^{3} 7^{2} =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 2^{8}
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 p^{2} 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 pschemes 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 Zeta2 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 Zeta2 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 5^{100} to 5^{100} plus a thousand modulo 1000
(i.e. the last three digits), the
the input
gives the output.

If you want to see the 5^{100} 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 10^{30} to 10^{30}+1000 modulo 1000
(i.e. the last three digits), the
the input
gives the output.

If you want to see the googolth 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 10^{30} to 10^{30} plus a thousand modulo 1000
(i.e. the last three digits), the
the input
gives the output.

If you want to see the googolth 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