OFFSET
1,8
COMMENTS
This multiset is generally not the same as the multiset of prime indices of n. For example, the prime indices of 12 are {1,1,2}, while a multiset whose multiplicities are {1,1,2} is {1,1,2,3}.
The Lyndon product of two or more finite sequences is defined to be the lexicographically maximal sequence obtainable by shuffling the sequences together. For example, the Lyndon product of (231) with (213) is (232131), the product of (221) with (213) is (222131), and the product of (122) with (2121) is (2122121). A Lyndon word is a finite sequence that is prime with respect to the Lyndon product.
a(1) = 1 by convention.
LINKS
Andrew Howroyd, Table of n, a(n) for n = 1..1000
Wikipedia, Lyndon word
FORMULA
a(p) = 0 for prime p. - Andrew Howroyd, Dec 08 2018
EXAMPLE
The a(30) = 10 Lyndon permutations of {1,1,1,2,2,3}:
(111223)
(111232)
(111322)
(112123)
(112132)
(112213)
(112312)
(113122)
(113212)
(121213)
MATHEMATICA
nrmptn[n_]:=Join@@MapIndexed[Table[#2[[1]], {#1}]&, If[n==1, {}, Flatten[Cases[FactorInteger[n]//Reverse, {p_, k_}:>Table[PrimePi[p], {k}]]]]];
LyndonQ[q_]:=Array[OrderedQ[{q, RotateRight[q, #]}]&, Length[q]-1, 1, And]&&Array[RotateRight[q, #]&, Length[q], 1, UnsameQ];
Table[Length[Select[Permutations[nrmptn[n]], LyndonQ]], {n, 2, 100}]
PROG
(PARI) sig(n)={my(f=factor(n)); concat(vector(#f~, i, vector(f[i, 2], j, primepi(f[i, 1]))))}
count(sig)={my(n=vecsum(sig)); sumdiv(gcd(sig), d, moebius(d)*(n/d)!/prod(i=1, #sig, (sig[i]/d)!))/n}
a(n)={if(n==1, 1, count(sig(n)))} \\ Andrew Howroyd, Dec 08 2018
CROSSREFS
KEYWORD
nonn
AUTHOR
Gus Wiseman, Sep 04 2018
STATUS
approved