A143328 -id:A143328 - cp's OEIS frontend

A062692 Number of irreducible polynomials over F_2 of degree at most n.

2, 3, 5, 8, 14, 23, 41, 71, 127, 226, 412, 747, 1377, 2538, 4720, 8800, 16510, 31042, 58636, 111013, 210871, 401428, 766150, 1465020, 2807196, 5387991, 10358999, 19945394, 38458184, 74248451, 143522117, 277737797, 538038783, 1043325198

Offset: 1

Gary L Mullen (mullen(AT)math.psu.edu), Jul 04 2001

Number of binary pre-necklaces of length n. - Joerg Arndt, Jul 20 2013

G. C. Greubel, Table of n, a(n) for n = 1..3320
P. Burcsi, G. Fici, Z. Lipták, F. Ruskey, and J. Sawada, On prefix normal words and prefix normal forms, Preprint, 2016.
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.
Kenneth H. Hicks, Gary L. Mullen, and Ikuro Sato, Distribution of irreducible polynomials over F_2, in Finite Fields with Applications to Coding Theory, Cryptography and Related Areas (Oaxaca, 2001), 177-186, Springer, Berlin, 2002.
M. Waldschmidt, Lectures on Multiple Zeta Values, IMSC 2011.

Partial sums of A001037.
Cf. A014580, A091226, A091231.
Equals A001036 + 1.
Column k=2 of A143328. - Alois P. Heinz, Jul 20 2013

with(numtheory):for n from 1 to 113 do sum3 := 0:for m from 1 to n do sum2 := 0:a := divisors(m):for h from 1 to nops(a) do sum2 := sum2+mobius(a[h])*2^(m/a[h]):end do:sum3 := sum3+sum2/m:end do:s[n] := sum3:end do:q := seq(s[j],j=1..113);

a[n_] := Sum[1/m DivisorSum[m, MoebiusMu[#]*2^(m/#)&], {m, 1, n}]; Array[a, 34] (* Jean-François Alcover, Dec 07 2015 *)
f[n_] := DivisorSum[n, MoebiusMu[#] * 2^(n/#) &] / n; Accumulate[Array[f, 30]] (* Amiram Eldar, Aug 24 2023 *)

a(n)=sum(m=1,n, 1/m* sumdiv(m, d, moebius(d)*2^(m/d) ) ); /* Joerg Arndt, Jul 04 2011 */

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

More terms from Sascha Kurz, Mar 25 2002

A215474 Triangle read by rows: number of k-ary n-tuples (a_1,..,a_n) such that the string a_1...a_n is preprime.

Original entry on oeis.org

1, 1, 3, 1, 5, 14, 1, 8, 32, 90, 1, 14, 80, 294, 829, 1, 23, 196, 964, 3409, 9695, 1, 41, 508, 3304, 14569, 49685, 141280, 1, 71, 1318, 11464, 63319, 259475, 861580, 2447592, 1, 127, 3502, 40584, 280319, 1379195, 5345276, 17360616, 49212093, 1, 226, 9382

Offset: 1

Peter Luschny, Aug 12 2012

A string is prime if it is nonempty and lexicographically less than all of its proper suffixes. A string is preprime if it is a nonempty prefix of a prime, on some alphabet. See the Knuth reference, section 7.2.1.1.

			T(4, 3) counts the 32 ternary preprimes of length 4 which are:
0000,0001,0002,0010,0011,0012,0020,0021,0022,0101,0102,
0110,0111,0112,0120,0121,0122,0202,0210,0211,0212,0220,
0221,0222,1111,1112,1121,1122,1212,1221,1222,2222.
Triangle starts (compare the table A143328 as a square array):
[1]
[1,  3]
[1,  5,  14]
[1,  8,  32,   90]
[1, 14,  80,  294,   829]
[1, 23, 196,  964,  3409,  9695]
[1, 41, 508, 3304, 14569, 49685, 141280]

D. E. Knuth. Generating All Tuples and Permutations. The Art of Computer Programming, Vol. 4, Fascicle 2, Addison-Wesley, 2005.

Alois P. Heinz, Rows n = 1..141, flattened

Cf. A056665, A054630, A143328, A215475.

# From Alois P. Heinz A143328.
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;
A215474 := (n, k) -> g2(n)(k);
seq(print(seq(A215474(n,d),d=1..n)),n=1..8);

t[n_, k_] := Sum[(1/j)*MoebiusMu[j/d]*k^d, {j, 1, n}, {d, Divisors[j]}]; Table[t[n, k], {n, 1, 10}, {k, 1, n}] // Flatten (* Jean-François Alcover, Jul 26 2013 *)

# This algorithm generates and counts all k-ary n-tuples
# (a_1,..,a_n) such that the string a_1...a_n is preprime.
# It is algorithm F in Knuth 7.2.1.1.
def A215474_count(n, k):
    a = [0]*(n+1); a[0]=-1
    j = 1; count = 0
    while True:
        count += 1;
        j = n
        while a[j] >= k-1 : j -= 1
        if j == 0 : break
        a[j] += 1
        for i in (j+1..n): a[i] = a[i-j]
    return count
def A215474(n,k):
     return add((1/j)*add(moebius(j/d)*k^d for d in divisors(j))  for j in (1..n))
for n in (1..9): print([A215474(n,k) for k in (1..n)])

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

T(n,n) = A143328(n,n).

A114945 Number of monic irreducible polynomials over GF(3) of degree <= n.

Original entry on oeis.org

3, 6, 14, 32, 80, 196, 508, 1318, 3502, 9382, 25486, 69706, 192346, 533830, 1490406, 4180416, 11776896, 33299124, 94470780, 268807044, 766918996, 2193322744, 6286504432, 18054379372, 51945923740, 149709932740, 432139468492, 1249167599632, 3615732336352

Offset: 1

Gary L Mullen (mullen(AT)math.psu.edu) and Ken Hicks, Jan 06 2006

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..650

Partial sums of A027376. 3rd column of A143328. - Alois P. Heinz, Sep 23 2008

with(numtheory):
b:= n-> add(mobius(d) *3^(n/d)/n, d=divisors(n)):
a:= n-> add(b(k), k=1..n):
seq(a(n), n=1..30);  # Alois P. Heinz, Sep 23 2008

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

a(n)=sum(m=1,n, 1/m* sumdiv(m, d, moebius(d)*3^(m/d) ) );/* Joerg Arndt, Jul 04 2011 */

a(n) ~ 3^(n+1) / (2*n). - Vaclav Kotesovec, Sep 05 2014

More terms from Alois P. Heinz, Sep 23 2008

A215475 Number of n-ary n-tuples (a_1,...,a_n) such that the string a_1...a_n is preprime.

Original entry on oeis.org

1, 3, 14, 90, 829, 9695, 141280, 2447592, 49212093, 1125217654, 28823053258, 817378772782, 25417591386199, 859893804621774, 31439503146486552, 1235301513403984512, 51906185332282554369, 2322562816163062723410, 110253678955655801174716, 5534198888175777261628156

Offset: 1

Peter Luschny, Aug 12 2012

nonn

See A215474 for the definitions.

			a(3) = 14 = card{000, 001, 002, 010, 011, 012, 020, 021, 022, 111, 112, 121, 122, 222}.

Alois P. Heinz, Table of n, a(n) for n = 1..387

Cf. A215474, A143328.

a[n_] := Sum[1/j Sum[MoebiusMu[j/d] n^d, {d, Divisors[j]}], {j, n}];
Array[a, 20] (* Jean-François Alcover, Jun 27 2019 *)

a(n) = sum(j=1, n, sumdiv(j, d, moebius(j/d)*n^d)/j); \\ Michel Marcus, Jun 27 2019

def A215475(n):
     return add((1/j)*add(moebius(j/d)*n^d for d in divisors(j)) for j in (1..n))
[A215475(n) for n in (1..20)]

a(n) = Sum_{j=1..n} (1/j)*Sum_{d|j} mu(j/d)*n^d.

a(n) = A215474(n,n) = A143328(n,n).

A114946 Number of monic irreducible polynomials over GF(4) of degree <= n.

Original entry on oeis.org

4, 10, 30, 90, 294, 964, 3304, 11464, 40584, 145338, 526638, 1924378, 7086598, 26259388, 97842104, 366273464, 1376854004, 5194587924, 19661846184, 74637375132, 284068160592, 1083712790142, 4143223406562, 15871346734402, 60907343008066, 234122710710436

Offset: 1

Gary L Mullen (mullen(AT)math.psu.edu) and Ken Hicks, Jan 06 2006

nonn

Partial sums of A027377. 4th column of A143328. - Alois P. Heinz, Sep 23 2008

with(numtheory):
b:= n-> add(mobius(d) *4^(n/d)/n, d=divisors(n)):
a:= n-> add(b(k), k=1..n):
seq(a(n), n=1..30); # Alois P. Heinz, Sep 23 2008

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

a(n)=sum(m=1, n, 1/m* sumdiv(m, d, moebius(d)*4^(m/d) ) ); /* Joerg Arndt, Jul 04 2011 */

More terms from Alois P. Heinz, Sep 23 2008

A114947 Number of monic irreducible polynomials over GF(5) of degree <= n.

Original entry on oeis.org

5, 15, 55, 205, 829, 3409, 14569, 63319, 280319, 1256567, 5695487, 26039187, 119939427, 555899247, 2590404239, 12127122989, 57005914349, 268933430849, 1272801132329, 6041172226049, 28747703565329, 137119782755669, 655421041672109, 3138947897124609

Offset: 1

Gary L Mullen (mullen(AT)math.psu.edu) and Ken Hicks, Jan 06 2006

nonn

Alois P. Heinz, Table of n, a(n) for n = 1..1000

Partial sums of A001692. 5th column of A143328. - Alois P. Heinz, Sep 23 2008

with(numtheory):
b:= n-> add(mobius(d) *5^(n/d)/n, d=divisors(n)):
a:= n-> add(b(k), k=1..n):
seq(a(n), n=1..30); # Alois P. Heinz, Sep 23 2008

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

a(n)=sum(m=1, n, 1/m* sumdiv(m, d, moebius(d)*5^(m/d) ) ); /* Joerg Arndt, Jul 04 2011 */

a(n) ~ 5^(n+1) / (4*n). - Vaclav Kotesovec, Sep 05 2014

More terms from Alois P. Heinz, Sep 23 2008

cp's OEIS Frontend

A062692 Number of irreducible polynomials over F_2 of degree at most n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A215474 Triangle read by rows: number of k-ary n-tuples (a_1,..,a_n) such that the string a_1...a_n is preprime.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Sage

Formula

A114945 Number of monic irreducible polynomials over GF(3) of degree <= n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A215475 Number of n-ary n-tuples (a_1,...,a_n) such that the string a_1...a_n is preprime.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Sage

Formula

A114946 Number of monic irreducible polynomials over GF(4) of degree <= n.

Views

Author

Keywords

Crossrefs

Programs

Maple

Mathematica

PARI

Extensions

A114947 Number of monic irreducible polynomials over GF(5) of degree <= n.

Views

Author

Keywords

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions