adv

Efficient Methods in Counting Generalized Necklaces. (arXiv:1808.03155v1 [math.CO])

It is shown in [7] by Venkaiah in 2015 that a category of the number of generalized can be computed using the expression \begin{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*(q-1)*Ord(\lambda)*n$ exponentiations and $(q-1)*Ord(\lambda)*n$ multiplications, at most $(q-1)*Ord(\lambda)*n$ exponentiations and at most $2*(q-1)*Ord(\lambda)*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.查看全文

Solidot 文章翻译

你的名字

留空匿名提交
你的Email或网站

用户可以联系你
标题

简单描述
内容