Efficient Methods in Counting Generalized Necklaces

arXiv1808.03155MaRDI QIDQ6305232FDOQ6305232

Authors: V. Ch. Venkaiah 

Publication date: 8 August 2018

Abstract: It is shown in [7] by Venkaiah in 2015 that a category of the number of generalized can be computed using the expression �egin{equation*} e(n, q) = frac{1}{(q-1) ord(lambda) n} sum^{ord(lambda)n}_{substack{t in mathbb{F}_q setminus {0}, i=1 \ t^{frac{n}{gcd(n, i)}} lambda^{frac{i}{gcd(n,i)}} = 1}}(q^{gcd(n,i)} - 1) + 1 end{equation*} where $q$ (number of colors) is the size of the prime field $mathbb{F}_q$, $lambda$ is the constant of the consta-cyclic shift, $n$ is the length of the necklace. However, direct evaluation of this expression requires, apart from the $gcd$ computations, $2\ast (q-1)\ast Ord(lambda)\ast n$ exponentiations and $(q-1)\ast Ord(lambda)\ast n$ multiplications, at most $(q-1)\ast Ord(lambda)\ast n$ exponentiations and at most $2\ast (q-1)\ast Ord(lambda)\ast n$ additions and hence computationally intensive. This note discusses various other ways of evaluating the expression and tries to throw some light on amortizing the amount of computation.

This page was built for publication: Efficient Methods in Counting Generalized Necklaces

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