A114945 -id:A114945 - cp's OEIS frontend

A143328 Table T(n,k) read by antidiagonals. T(n,k) is the number of primitive (=aperiodic) k-ary Lyndon words (n,k >= 1) with length less than or equal to n.

1, 2, 1, 3, 3, 1, 4, 6, 5, 1, 5, 10, 14, 8, 1, 6, 15, 30, 32, 14, 1, 7, 21, 55, 90, 80, 23, 1, 8, 28, 91, 205, 294, 196, 41, 1, 9, 36, 140, 406, 829, 964, 508, 71, 1, 10, 45, 204, 728, 1960, 3409, 3304, 1318, 127, 1, 11, 55, 285, 1212, 4088, 9695, 14569, 11464, 3502, 226, 1

Offset: 1

Alois P. Heinz, Aug 07 2008

			T(3,2) = 5, because 5 words of length <=3 over 2-letter alphabet {a,b} are primitive Lyndon words: a, b, ab, aab, abb.
Table begins:
  1,  2,  3,   4,   5,  ...
  1,  3,  6,  10,  15,  ...
  1,  5, 14,  30,  55,  ...
  1,  8, 32,  90, 205,  ...
  1, 14, 80, 294, 829,  ...

Alois P. Heinz, Antidiagonals n = 1..141, flattened
Index entries for sequences related to Lyndon words

Columns k=1-5 give: A000012, A062692, A114945, A114946, A114947.
Rows n=1-4 give: A000027, A000217, A000330, A132117.
Main diagonal gives A215475.
Cf. A143324, A074650, A008683.

with(numtheory):
f0:= proc(n) option remember; unapply(k^n-add(f0(d)(k),
        d=divisors(n)minus{n}), k)
     end:
f2:= proc(n) option remember; unapply(f0(n)(x)/n, x) end:
g2:= proc(n) option remember; unapply(add(f2(j)(x), j=1..n), x) end:
T:= (n,k)-> g2(n)(k):
seq(seq(T(n, 1+d-n), n=1..d), d=1..12);

f0[n_] := f0[n] = Function[k, k^n-Sum[f0[d][k], {d, Divisors[n]//Most}]]; f2[n_] := f2[n] = Function[x, f0[n][x]/n]; g2[n_] := g2[n] = Function[x, Sum[f2[j][x], {j, 1, n}]]; T[n_, k_] := g2[n][k]; Table[T[n, 1+d-n], {d, 1, 12}, {n, 1, d}]//Flatten (* Jean-François Alcover, Feb 12 2014, translated from Maple *)

T(n,k) = Sum_{1<=j<=n} (1/j) * Sum_{d|j} mu(j/d)*k^d.

T(n,k) = Sum_{1<=j<=n} A074650(j,k).

A005377 Number of low discrepancy sequences in base 4.

Original entry on oeis.org

0, 0, 0, 0, 1, 2, 3, 4, 5, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40, 42, 44, 46, 49, 52, 55, 58, 61, 64, 67, 70, 73, 76, 79, 82, 85, 88, 91, 94, 97, 100, 103, 106, 109, 112, 115, 118, 121, 124, 127, 130, 133, 136, 139

Offset: 1

N. J. A. Sloane, Simon Plouffe

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Harald Niederreiter, Low-discrepancy and low-dispersion sequences, J. Number Theory 30 (1988), no. 1, 51-70.

Cf. A005356 (base 2), A005357 (base 3), A005358 (base 5), A274039 (Plouffe's g.f.)

Cf. A001037 (N(2,n)), A027376 (N(3,n)), A027377 (N(4,n)), A062692 (M(2,n)), A114945 (M(3,n)), A114946 (M(4,n)).

N := proc(b,n)
    option remember;
    local d;
    add(b^d*numtheory[mobius](n/d),d=numtheory[divisors](n)) ;
    %/n ;
end proc:
M := proc(b,n)
    local h;
    if n = 0 then
        0;
    else
        add(N(b,h),h=1..n) ;
    end if;
end proc:
nMax := proc(b,s)
    local n;
    for n from 0 do
        if M(b,n) > s then
            return n-1 ;
        end if;
    end do:
end proc:
A005377 := proc(s)
    local n,b;
    b := 4 ;
    n := nMax(b,s) ;
    n*(s-M(b,n))+add( (h-1)*N(b,h),h=1..n) ;
end proc:
seq(A005377(n),n=1..40) ; # R. J. Mathar, Jun 09 2016

Np[b_, n_] := Np[b, n] = Sum[b^d*MoebiusMu[n/d], {d, Divisors[n]}]/n;
M[b_, n_] := If[n == 0, 0, Sum[Np[b, h], {h, 1, n}]];
nMax[b_, s_] := Module[{n}, For[n = 0, True, n++, If[M[b, n] > s, Return[n - 1]]]];
a[s_] := Module[{n, b}, b = 4; n = nMax[b, s]; n*(s - M[b, n]) + Sum[(h - 1)*Np[b, h], {h, 1, n}]];
Table[a[n], {n, 1, 61}] (* Jean-François Alcover, Sep 12 2023, after R. J. Mathar *)

Let N(b,n) = (1/n) * Sum_{d|n} mobius(n/d) * b^d. Let M(b,n) = Sum_{k=1..n} N(b,k) with M(b,0) = 0. Let r = r(b,n) be the largest value r such that M(b,r) <= n. Then a(n) = r * (n - M(4, r)) + Sum_{h=1..r} (h-1) * N(4, h) [From Niederreiter paper]. - Sean A. Irvine, Jun 07 2016

G.f.: z^4 * (z^2+1) * (z^4-z^2+1) / (z-1)^2; [Conjectured by Simon Plouffe in his 1992 dissertation, but is incorrect.]

Terms, offset, and formula corrected by Sean A. Irvine, Jun 07 2016

cp's OEIS Frontend

A143328 Table T(n,k) read by antidiagonals. T(n,k) is the number of primitive (=aperiodic) k-ary Lyndon words (n,k >= 1) with length less than or equal to n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula