A062692 -id:A062692 - cp's OEIS frontend

A091226 Number of irreducible GF(2)[X]-polynomials in range [0,n].

0, 0, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 9, 9, 9, 9, 10, 10, 10, 10, 10, 10, 11, 11, 11, 11, 11, 11, 11, 11, 12, 12, 12, 12, 13, 13, 14, 14, 14, 14, 14, 14, 15, 15, 15, 15, 15, 15, 16, 16, 16, 16, 16, 16, 16, 16, 16

Offset: 0

Antti Karttunen, Jan 03 2004

nonn

Analogous to A000720.

Partial sums of A091225. A062692(n) = a(2^n).

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.

Original entry on oeis.org

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

A234751 Self-inverse permutation of integers induced by the restriction of blue-code to irreducible polynomials over GF(2): a(n) = A091227(A193231(A014580(n))).

Original entry on oeis.org

2, 1, 3, 5, 4, 6, 8, 7, 12, 14, 13, 9, 11, 10, 17, 18, 15, 16, 20, 19, 21, 23, 22, 41, 39, 40, 38, 37, 34, 33, 35, 36, 30, 29, 31, 32, 28, 27, 25, 26, 24, 43, 42, 47, 46, 45, 44, 49, 48, 51, 50, 52, 54, 53, 55, 71, 69, 70, 68, 65, 64, 67, 66, 61, 60, 63, 62, 59, 57, 58, 56

Offset: 1

Antti Karttunen, Feb 12 2014

This permutation is also induced when A234747 is restricted to primes: a(n) = A000720(A234747(A000040(n))) because of the way A234747 has been defined.

Note that each subsequence a(1)..a(A062692(j)) is closed (i.e., no cycles are leaking out) because blue code (A193231) preserves the degree of polynomials over GF(2) it operates upon.

Antti Karttunen, Table of n, a(n) for n = 1..2538
Index entries for sequences that are permutations of the natural numbers

Cf. A014580, A062692, A193231, A234747, A234750.

(define (A234751 n) (A091227 (A234750 n)))

a(n) = A091227(A234750(n)) = A091227(A193231(A014580(n))).

A194850 Number of prefix normal words of length n.

Original entry on oeis.org

2, 3, 5, 8, 14, 23, 41, 70, 125, 218, 395, 697, 1273, 2279, 4185, 7568, 13997, 25500, 47414, 87024, 162456, 299947, 562345, 1043212, 1962589, 3657530, 6900717, 12910042, 24427486, 45850670, 86970163, 163756708, 311283363, 587739559, 1119581278, 2119042830

Offset: 1

Gabriele Fici, Sep 04 2011

nonn

A binary word of length n is prefix normal if for all 1 <= k <= n, no factor of length k has more a's than the prefix of length k. That is, abbabab is not prefix normal because aba has more a's than abb. - Zsuzsanna Liptak, Oct 12 2011

a(n) <= A062692(n): every prefix normal word is a pre-necklace, but the converse is not true, see the Fici/Lipták reference. - Joerg Arndt, Jul 20 2013

			For n=3: aaa, aab, abb, aba, bbb are all prefix normal words. - _Zsuzsanna Liptak_, Oct 12 2011

Zsuzsanna Liptak, Table of n, a(n) for n = 1..50
Paul Balister and Stefanie Gerke, The asymptotic number of prefix normal words, arXiv:1903.07957 [math.CO], 2019.
P. Burcsi, G. Fici, Zs. Lipták, F. Ruskey, and J. Sawada, On Combinatorial Generation of Prefix Normal Words, arXiv:1401.6346 [cs.DS], 2014.
P. Burcsi, G. Fici, Z. Lipták, F. Ruskey, and J. Sawada, Normal, Abby Normal, Prefix Normal, arXiv preprint arXiv:1404.2824 [cs.FL], 2014.
P. Burcsi, G. Fici, Z. Lipták, F. Ruskey, and J. Sawada, On prefix normal words and prefix normal forms, Preprint, 2016.
Péter Burcsi, Gabriele Fici, Zsuzsanna Lipták, Rajeev Raman, and Joe Sawada, Generating a Gray code for prefix normal words in amortized polylogarithmic time per word, arXiv:2003.03222 [cs.DS], 2020.
Péter Burcsi, Gabriele Fici, Zsuzsanna Lipták, Frank Ruskey, and Joe Sawada, On Prefix Normal Words and Prefix Normal Forms, arXiv:1611.09017 [cs.DM], 2016.
Ferdinando Cicalese, Zsuzsanna Lipták, and Massimiliano Rossi, Bubble-Flip—A new generation algorithm for prefix normal words, arXiv:1712.05876 [cs.DS], 2017-2018; Theoretical Computer Science, Volume 743, 26 September 2018, Pages 38-52.
Ferdinando Cicalese, Zsuzsanna Lipták, and Massimiliano Rossi, On Infinite Prefix Normal Words, arXiv:1811.06273 [math.CO], 2018.
G. Fici and Zs. Lipták, On Prefix Normal Words
G. Fici and Zs. Lipták, On Prefix Normal Words, Developments in Language Theory 2011, Lecture Notes in Computer Science 6795, 228-238.
Pamela Fleischmann, On Special k-Spectra, k-Locality, and Collapsing Prefix Normal Words, Ph.D. Dissertation, Kiel University (Germany, 2021).
Pamela Fleischmann, Mitja Kulczynski, and Dirk Nowotka, On Collapsing Prefix Normal Words, arXiv:1905.11847 [cs.FL], 2019.
Pamela Fleischmann, Mitja Kulczynski, Dirk Nowotka, and Danny Bøgsted Poulsen, On Collapsing Prefix Normal Words, Language and Automata Theory and Applications (LATA 2020) LNCS Vol. 12038, Springer, Cham, 412-424.
Zsuzsanna Lipták, Open problems on prefix normal words, also in Dagstuhl Reports (2018) Vol. 8, Issue 7, 59-61.

Cf. A062692 (binary pre-necklaces).

See A238109 for a list of the prefix-normal words.

from itertools import product
def is_prefix_normal(w):
  for k in range(1, len(w)+1):
    weight0 = w[:k].count("1")
    for j in range(1, len(w)-k+1):
      weightj = w[j:j+k].count("1")
      if weightj > weight0: return False
  return True
def a(n):
  return sum(is_prefix_normal(w) for w in product("01", repeat=n))
print([a(n) for n in range(1, 20)]) # Michael S. Branicky, Dec 19 2020

More terms added by Zsuzsanna Liptak, Oct 12 2011

Further terms added by Zsuzsanna Liptak, Jan 29 2014

A091231 How many more primes than irreducible GF(2)[X] polynomials there are in range [0,2^n].

Original entry on oeis.org

0, 0, 0, 1, 1, 3, 4, 8, 13, 26, 45, 83, 152, 281, 523, 974, 1822, 3451, 6490, 12348, 23389, 44598, 85076, 162735, 311721, 598669, 1150613, 2215562, 4271844, 8247356, 15941844, 30849114, 59758104, 115878009, 224900328

Offset: 0

Antti Karttunen, Jan 03 2004

nonn

			There are 11 primes (2,3,5,7,11,13,17,19,23,29,31) in range [0,32], while there are only 8 irreducible GF(2)[X]-polynomials in the same range: (2,3,7,11,13,19,25,31), thus a(5)=3.

Partial sums of A091232.

a(0)=a(1)=0, a(n) = A007053(n)-A062692(n-1).

A344018 Table read by rows: T(n,k) (n >= 1, 1 <= k <= 2^n) is the number of cycles of length k which can be produced by a general n-stage feedback shift register.

Original entry on oeis.org

2, 1, 2, 1, 2, 1, 2, 1, 2, 3, 2, 3, 4, 2, 2, 1, 2, 3, 6, 7, 8, 12, 14, 17, 14, 13, 12, 20, 32, 16, 2, 1, 2, 3, 6, 9, 12, 20, 32, 57, 78, 113, 154, 208, 300, 406, 538, 703, 842, 1085, 1310, 1465, 1544, 1570, 1968, 2132, 2000, 2480, 2176, 2816, 4096, 2048

Offset: 1

N. J. A. Sloane, Jun 21 2021

T(n,k) is the number of cycles of length k in the directed binary de Bruijn graph of order n.

			The first four rows of the triangle are
2, 1,
2, 1, 2, 1,
2, 1, 2, 3, 2, 3, 4, 2,
2, 1, 2, 3, 6, 7, 8, 12, 14, 17, 14, 13, 12, 20, 32, 16,
...

Pontus von Brömssen, Rows n = 1..6, flattened
Peter R. Bryant and J. Christensen, The enumeration of shift register sequences, Journal of Combinatorial Theory, Series A, Vol. 35, No. 2 (1983), 154-172.
Oscar Cabrera, Introducing loop compression for encoding de Bruijn sequences, engrXiv (2025) Art. No. 4431. See p. 13.

Cf. A000010, A001037, A016031, A346018.

Row sums: A306522.

import networkx as nx
def deBruijn(n): return nx.MultiDiGraph(((0, 0), (0, 0))) if n==0 else nx.line_graph(deBruijn(n-1))
def A344018_row(n):
  a=[0]*2**n
  for c in nx.simple_cycles(deBruijn(n)):
    a[len(c)-1]+=1
  return a # Pontus von Brömssen, Jun 28 2021

From Pontus von Brömssen, Jun 28 2021: (Start)
T(n,k) = A001037(k) for n >= k-1.
T(k-2,k) = A001037(k) - A000010(k).
T(k-3,k) = A001037(k) - 2*A346018(k,2) + 2 for k >= 5.
T(n,2^n-1) = 2*T(n,2^n) = 2*A016031(n).
(See page 157 in the paper by Bryant and Christensen.)
(End)
From Pontus von Brömssen, Jul 01 2021: (Start)
Conjectures by Bryant and Christensen (1983):
Conjecture 1: T(k-4,k) = A001037(k) - 4*A346018(k,3) - 2*gcd(k,2) + 10 for k >= 8.
Conjecture 2: T(k-5,k) = A001037(k) - 8*A346018(k,4) - gcd(k,3) + 19 for k >= 11.
Conjecture 3: T(k-6,k) = A001037(k) - 16*A346018(k,5) - 4*gcd(k,2) - 2*gcd(k,3) + 48 for k >= 15. (End)
Sum_{k=1..m} T(n, k) = A062692(m) for 1 <= m <= n + 1. - C.S. Elder, Nov 07 2023

More terms from Pontus von Brömssen, Jun 28 2021

A001036 Partial sums of A001037, omitting A001037(1).

Original entry on oeis.org

1, 2, 4, 7, 13, 22, 40, 70, 126, 225, 411, 746, 1376, 2537, 4719, 8799, 16509, 31041, 58635, 111012, 210870, 401427, 766149, 1465019, 2807195, 5387990, 10358998, 19945393, 38458183, 74248450, 143522116, 277737796, 538038782, 1043325197

Offset: 1

N. J. A. Sloane

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

M. A. Harrison, On the classification of Boolean functions by the general linear and affine groups, J. Soc. Indust. Appl. Math. 12 (1964), 285-299.

Cf. A001037, A062692.

f[n_] := DivisorSum[n, MoebiusMu[#] * 2^(n/#) &] / n; Accumulate[Array[f, 30]] - 1 (* Amiram Eldar, Aug 24 2023 *)

a(n) = A062692(n)-1. - Gabriele Fici, Feb 02 2011

G.f.: -x/(1 - x) + (1/(1 - x)) * Sum_{k>=1} mu(k)*log(1/(1 - 2*x^k))/k. - Ilya Gutkovskiy, Nov 11 2019

More terms from David W. Wilson, Oct 11 2000

cp's OEIS Frontend

A091226 Number of irreducible GF(2)[X]-polynomials in range [0,n].

Views

Author

Keywords

Comments

Links

Crossrefs

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

A005377 Number of low discrepancy sequences in base 4.

Views

Author

Keywords

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

Extensions

A234751 Self-inverse permutation of integers induced by the restriction of blue-code to irreducible polynomials over GF(2): a(n) = A091227(A193231(A014580(n))).

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Scheme

Formula

A194850 Number of prefix normal words of length n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Extensions

A091231 How many more primes than irreducible GF(2)[X] polynomials there are in range [0,2^n].

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A344018 Table read by rows: T(n,k) (n >= 1, 1 <= k <= 2^n) is the number of cycles of length k which can be produced by a general n-stage feedback shift register.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

Extensions

A001036 Partial sums of A001037, omitting A001037(1).

Views

Author

Keywords

References

Links

Crossrefs

Programs