A Primality Test inspired by circular words in, {1, 2, 3},

    avoiding Consecutive subwords in, {[1, 1], [2, 2, 2], [3, 3, 3, 3]},

    and their first few Pseudoprimes



                              By Shalosh B. Ekhad



The following primality test is generated by the sequence enumerating  words\

     of length n in the alphabet, {1, 2, 3},

    avoiding as consecutive words the patterns in,

    {[1, 1], [2, 2, 2], [3, 3, 3, 3]}



       Theorem: Let a(i) be the sequence given by the generating function



         infinity
          -----                     5       4       3       2
           \            n        5 s  + 14 s  + 18 s  + 12 s  - 6
            )     a(n) s  = -------------------------------------------
           /                            5      4      3      2
          -----             (s + 1) (2 s  + 3 s  + 4 s  + 2 s  + s - 1)
          n = 0



             Or equivalenty the sequence satisfying the recurrence



     a(n) = 3 a(n - 2) + 6 a(n - 3) + 7 a(n - 4) + 5 a(n - 5) + 2 a(n - 6)



                            with initial conditions



        a[1] = 0, a[2] = 6, a[3] = 18, a[4] = 46, a[5] = 115, a[6] = 300



        then if p is a prime, then a(p) is always congruent mod p to, 0



Proof: Using the Edlin-Zeilberger variation of the Goulden-Jackson method,  \
    Adv. in Appl. Math 25(2000), 228-232,  https://sites.math.rutgers.edu/~z\
    eilberg/mamarim/mamarimhtml/cgj.html

the above generating function (except for the first few terms) enumerates ci\
    rcular words (with a clasp)

Obviously unless  all the letters are the same, all the p rotations are dist\
    inct, hence this set of non-constant words can be partitioned into equiv\
    alence classes under rotation, each of them

                                 with p members



                             ---------------------





      For the sake of the OEIS the first, 30, terms, starting at n=1 are



0, 6, 18, 46, 115, 300, 777, 2014, 5202, 13471, 34859, 90208, 233441, 604113,

    1563343, 4045678, 10469552, 27093504, 70113572, 181442511, 469543680,

    1215102609, 3144487734, 8137422352, 21058324315, 54495515145, 141025521600,

    364951091677, 944434013103, 2444041476925





            There are, 6, pseduo-primes <=, 1000000, here there are



                     [6, 9, 107058, 149907, 196949, 387961]





There are, 1, pseduo-primes that are squares of primes, among the first, 2000,

    primes. Here there are

                                      [9]





There are, 0,

    pseduo-primes that are products of two distinct primes, among the first,

    500, primes. Here there are

                                       []



                        -------------------------------



                                                          7
         This ends this article that took, 0.1078159927 10 , seconds.



               [[6, 9, 107058, 149907, 196949, 387961], [9], []]