A027376 -id:A027376 - cp's OEIS frontend

A058818 a(0) = 1, a(1) = 3; for n >= 2 a(n) is the number of degree-n monic reducible polynomials over GF(3), i.e., a(n) = 3^n - A027376(n).

1, 3, 6, 19, 63, 195, 613, 1875, 5751, 17499, 53169, 161043, 487221, 1471683, 4441485, 13392331, 40356711, 121543683, 365898261, 1101089811, 3312448137, 9962241251, 29954655861, 90049997139, 270661661541, 813397065075, 2444101819329, 7343167949235

Offset: 0

Claude Lenormand (claude.lenormand(AT)free.fr), Jan 04 2001

nonn

Dimensions of homogeneous subspaces of shuffle algebra over 3-letter alphabet (see A058766 for 2-letter case).

M. Lothaire, Combinatorics on words, Cambridge mathematical library, 1983, p. 126 (definition of shuffle algebra).

Cf. A027376, A058766.

a[n_] := 3^n - DivisorSum[n, MoebiusMu[n/#] * 3^# &] / n; a[0] = 1; a[1] = 3; Array[a, 28, 0] (* Amiram Eldar, Aug 13 2023 *)

a(n) = if (n<=1, 3^n, 3^n - sumdiv(n, d, moebius(d)*3^(n/d))/n); \\ Michel Marcus, Oct 30 2017

Better description from Sharon Sela (sharonsela(AT)hotmail.com), Feb 19 2002

a(16)-a(27) from Alois P. Heinz, Nov 25 2016

A074650 Table T(n,k) read by downward antidiagonals: number of Lyndon words (aperiodic necklaces) with n beads of k colors, n >= 1, k >= 1.

Original entry on oeis.org

1, 2, 0, 3, 1, 0, 4, 3, 2, 0, 5, 6, 8, 3, 0, 6, 10, 20, 18, 6, 0, 7, 15, 40, 60, 48, 9, 0, 8, 21, 70, 150, 204, 116, 18, 0, 9, 28, 112, 315, 624, 670, 312, 30, 0, 10, 36, 168, 588, 1554, 2580, 2340, 810, 56, 0, 11, 45, 240, 1008, 3360, 7735, 11160, 8160, 2184, 99, 0

Offset: 1

Christian G. Bower, Aug 28 2002

D. E. Knuth uses the term 'prime strings' for Lyndon words because of the fundamental theorem stating the unique factorization of strings into nonincreasing prime strings (see Knuth 7.2.1.1). With this terminology T(n,k) is the number of k-ary n-tuples (a_1,...,a_n) such that the string a_1...a_n is prime. - Peter Luschny, Aug 14 2012
Also, for k a power of a prime, the number of monic irreducible polynomials of degree n over GF(k). - Andrew Howroyd, Dec 23 2017
An equivalent description: Array read by antidiagonals: T(n,k) = number of conjugacy classes of primitive words of length k >= 1 over an alphabet of size n >= 1.
There are a few incorrect values in Table 1 in the Perrin-Reutenauer paper (Christophe Reutenauer, personal communication), see A294438. - Lars Blomberg, Dec 05 2017
The fact that T(3,4) = 20 coincides with the number of the amino acids encoded by DNA made Francis Crick, John Griffith and Leslie Orgel conjecture in 1957 that the genetic code is a comma-free code, which later turned out to be false. [Hayes] - Andrey Zabolotskiy, Mar 24 2018

			T(4, 3) counts the 18 ternary prime strings of length 4 which are: 0001, 0002, 0011, 0012, 0021, 0022, 0102, 0111, 0112, 0121, 0122, 0211, 0212, 0221, 0222, 1112, 1122, 1222.
Square array starts:
  1,  2,   3,    4,     5,     6,      7, ...
  0,  1,   3,    6,    10,    15,     21, ...
  0,  2,   8,   20,    40,    70,    112, ...
  0,  3,  18,   60,   150,   315,    588, ...
  0,  6,  48,  204,   624,  1554,   3360, ...
  0,  9, 116,  670,  2580,  7735,  19544, ...
  0, 18, 312, 2340, 11160, 39990, 117648, ...
  ...
The transposed array starts:
   1  0  0     0     0      0       0        0         0          0,
   2  1  2     3     6      9      18       30        56         99,
   3  3  8    18    48    116     312      810      2184       5880,
   4  6  20   60   204    670    2340     8160     29120     104754,
   5 10  40  150   624   2580   11160    48750    217000     976248,
   6 15  70  315  1554   7735   39990   209790   1119720    6045837,
   7 21 112  588  3360  19544  117648   720300   4483696   28245840,
   8 28 168 1008  6552  43596  299592  2096640  14913024  107370900,
   9 36 240 1620 11808  88440  683280  5380020  43046640  348672528,
  10 45 330 2475 19998 166485 1428570 12498750 111111000  999989991,
  11 55 440 3630 32208 295020 2783880 26793030 261994040 2593726344,
  12 66 572 5148 49764 497354 5118828 53745120 573308736 6191711526,
  ...
The initial antidiagonals are:
   1
   2  0
   3  1   0
   4  3   2    0
   5  6   8    3    0
   6 10  20   18    6     0
   7 15  40   60   48     9     0
   8 21  70  150  204   116    18     0
   9 28 112  315  624   670   312    30     0
  10 36 168  588 1554  2580  2340   810    56    0
  11 45 240 1008 3360  7735 11160  8160  2184   99   0
  12 55 330 1620 6552 19544 39990 48750 29120 5880 186 0

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Cambridge, 1998, p. 97 (2.3.74)
Miklos Bona, editor, Handbook of Enumerative Combinatorics, CRC Press, 2015, p. 495.
D. E. Knuth, Generating All Tuples and Permutations. The Art of Computer Programming, Vol. 4, Fascicle 2, pp. 26-27, Addison-Wesley, 2005.

Alois P. Heinz, Antidiagonals n = 1..141, flattened
B. Hayes, The invention of the genetic code, American Scientist, Vol. 86, No. 1 (January-February 1998), pp. 8-14.
Veronika Irvine, Lace Tessellations: A mathematical model for bobbin lace and an exhaustive combinatorial search for patterns, PhD Dissertation, University of Victoria, 2016.
Irem Kucukoglu and Yilmaz Simsek, On k-ary Lyndon words and their generating functions, AIP Conference Proceedings 1863, 300004 (2017).
R. C. Lyndon, On Burnside's problem, Transactions of the American Mathematical Society 77, (1954) 202-215.
Dominique Perrin and Christophe Reutenauer, Hall sets, Lazard sets and comma-free codes, arXiv preprint arXiv:1609.05438 [math.CO] (2016).
Dominique Perrin and Christophe Reutenauer, Hall sets, Lazard sets and comma-free codes, Discrete Math., 341 (2018), 232-243.
Dominique Perrin and Christophe Reutenauer, Hall sets, Lazard sets and comma-free codes, Discrete Math., 341 (2018), 232-243. [Annotated scanned copy of page 236 only.]
Wikipedia, Lyndon word
Index entries for sequences related to Lyndon words

Columns k: A001037 (k=2), A027376 (k=3), A027377 (k=4), A001692 (k=5), A032164 (k=6), A001693 (k=7), A027380 (k=8), A027381 (k=9), A032165 (k=10), A032166 (k=11), A032167 (k=12), A060216 (k=13), A060217 (k=14), A060218 (k=15), A060219 (k=16), A060220 (k=17), A060221 (k=18), A060222 (k=19).
Rows n: A000027 (n=1), A000217(k-1) (n=2), A007290(k+1) (n=3), A006011 (n=4), A208536(k+1) (n=5), A292350 (n=6), A208537(k+1) (n=7).
Cf. A000010, A008683, A075147 (main diagonal), A102659, A215474 (preprime strings), A383011.

t:= func< n,k | (&+[MoebiusMu(Floor(n/d))*k^d: d in Divisors(n)])/n >; // array
A074650:= func< n,k | t(k, n-k+1) >; // downward diagonals
[A074650(n,k): k in [1..n], n in [1..15]]; // G. C. Greubel, Aug 01 2024

with(numtheory):
T:= proc(n, k) add(mobius(n/d)*k^d, d=divisors(n))/n end:
seq(seq(T(i, 1+d-i), i=1..d), d=1..11);  # Alois P. Heinz, Mar 28 2008

max = 12; t[n_, k_] := Total[ MoebiusMu[n/#]*k^# & /@ Divisors[n]]/n; Flatten[ Table[ t[n-k+1, k], {n, 1, max}, {k, n, 1, -1}]] (* Jean-François Alcover, Oct 18 2011, after Maple *)

T(n,k)=sumdiv(n,d,moebius(n/d)*k^d)/n \\ Charles R Greathouse IV, Oct 18 2011

# This algorithm generates and counts all k-ary n-tuples (a_1,..,a_n) such
# that the string a_1...a_n is prime. It is algorithm F in Knuth 7.2.1.1.
def A074650(n, k):
    a = [0]*(n+1); a[0]=-1
    j = 1; count = 0
    while(j != 0) :
        if j == n : count += 1; # print("".join(map(str,a[1:])))
        else: j = n
        while a[j] >= k-1 : j -= 1
        a[j] += 1
        for i in (j+1..n): a[i] = a[i-j]
    return count   # Peter Luschny, Aug 14 2012

T(n,k) = (1/n) * Sum_{d|n} mu(n/d)*k^d.
T(n,k) = (k^n - Sum_{dAlois P. Heinz, Mar 28 2008
From Richard L. Ollerton, May 10 2021: (Start)
T(n,k) = (1/n)*Sum_{i=1..n} mu(gcd(n,i))*k^(n/gcd(n,i))/phi(n/gcd(n,i)).
T(n,k) = (1/n)*Sum_{i=1..n} mu(n/gcd(n,i))*k^gcd(n,i)/phi(n/gcd(n,i)). (End)
From Seiichi Manyama, Apr 12 2025: (Start)
G.f. of column k: -Sum_{j>=1} mu(j) * log(1 - k*x^j) / j.
Product_{n>=1} 1/(1 - x^n)^T(n,k) = 1/(1 - k*x). (End)

A027377 Number of irreducible polynomials of degree n over GF(4); dimensions of free Lie algebras.

Original entry on oeis.org

1, 4, 6, 20, 60, 204, 670, 2340, 8160, 29120, 104754, 381300, 1397740, 5162220, 19172790, 71582716, 268431360, 1010580540, 3817733920, 14467258260, 54975528948, 209430785460, 799644629550, 3059510616420

Offset: 0

N. J. A. Sloane

Apart from initial terms, exponents in expansion of A065419 as a product zeta(n)^(-a(n)).

Number of aperiodic necklaces with n beads of 4 colors. - Herbert Kociemba, Nov 25 2016

E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, NY, 1968, p. 84.
M. Lothaire, Combinatorics on Words. Addison-Wesley, Reading, MA, 1983, p. 79.

Seiichi Manyama, Table of n, a(n) for n = 0..1666 (terms 0..200 from T. D. Noe)
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
G. Niklasch, Some number theoretical constants: 1000-digit values [Cached copy]
A. Pakapongpun and T. Ward, Functorial Orbit counting, JIS 12 (2009) 09.2.4, example 3.
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
G. Viennot, Algèbres de Lie Libres et Monoïdes Libres, Lecture Notes in Mathematics 691, Springer Verlag 1978.
Index entries for sequences related to Lyndon words

Cf. A001037, A027376, A054719, A054660, A054661.

Column k=4 of A074650.

A027377 := proc(n) local d,s; if n = 0 then RETURN(1); else s := 0; for d in divisors(n) do s := s+mobius(d)*4^(n/d); od; RETURN(s/n); fi; end;

a[n_] := Sum[MoebiusMu[d]*4^(n/d), {d, Divisors[n]}] / n; a[0] = 1; Table[a[n], {n, 0, 23}](* Jean-François Alcover, Nov 29 2011 *)
mx=40;f[x_,k_]:=1-Sum[MoebiusMu[i] Log[1-k*x^i]/i,{i,1,mx}];CoefficientList[Series[f[x,4],{x,0,mx}],x] (* Herbert Kociemba, Nov 25 2016 *)

a(n)=if(n,sumdiv(n,d,moebius(d)<<(2*n/d))/n,1) \\ Charles R Greathouse IV, Nov 29 2011

a(n) = Sum_{d|n} mu(d)*4^(n/d)/n.
G.f.: k=4, 1 - Sum_{i>=1} mu(i)*log(1 - k*x^i)/i. - Herbert Kociemba, Nov 25 2016
a(n) = A054661(n) + 3 * A054660(n). - Andrey Zabolotskiy, Dec 17 2020
a(n) = 2 * (A054664(n) + A054660(n)). - Andrey Zabolotskiy, Dec 19 2020
a(n) = A054719(n)/n, n>0. - R. J. Mathar, Dec 16 2024

A059885 a(n) = |{m : multiplicative order of 3 mod m = n}|.

Original entry on oeis.org

2, 2, 2, 6, 4, 10, 2, 14, 4, 16, 6, 58, 2, 10, 16, 88, 6, 108, 6, 150, 10, 54, 6, 290, 18, 10, 56, 138, 14, 716, 14, 144, 22, 118, 40, 1088, 6, 54, 90, 670, 14, 730, 6, 570, 356, 22, 30, 13864, 124, 342, 54, 138, 14, 3912, 116, 1362, 118, 238, 6, 22058, 6, 110

Offset: 1

Vladeta Jovovic, Feb 06 2001

nonn

The multiplicative order of a mod m, GCD(a,m)=1, is the smallest natural number d for which a^d = 1 (mod m). a(n) = number of orders of degree-n monic irreducible polynomials over GF(3).

Also, number of primitive factors of 3^n - 1 (cf. A218356). - Max Alekseyev, May 03 2022

			a(2) = |{4,8}| = 2, a(4) = |{5,10,16,20,40,80}| = 6, a(6) = |{7,14,28,52,56,91,104,182,364,728}| = 10.

Max Alekseyev, Table of n, a(n) for n = 1..690 (first 100 terms from Alois P. Heinz)

Primitive factors of b^n - 1: A059499 (b=2), this sequence (b=3), A059886 (b=4), A059887 (b=5), A059888 (b=6), A059889 (b=7), A059890 (b=8), A059891 (b=9), A059892 (b=10).
Cf. A000005, A008683, A027376, A057958, A058944, A074477, A143663, A212906, A218356.
Column k=3 of A212957.

with(numtheory); A059885 := proc(n) local d,s; s := 0; for d in divisors(n) do s := s+mobius(n/d)*tau(3^d-1); od; RETURN(s); end;

a[n_] := Sum[ MoebiusMu[n/d] * DivisorSigma[0, 3^d - 1], {d, Divisors[n]}]; Table[a[n], {n, 1, 62} ] (* Jean-François Alcover, Dec 12 2012 *)

a(n) = sumdiv(n, d, moebius(n/d) * numdiv(3^d-1)); \\ Amiram Eldar, Jan 25 2025

a(n) = Sum_{ d divides n } mu(n/d)*tau(3^d-1), (mu(n) = Moebius function A008683, tau(n) = number of divisors of n A000005).

A210109 Number of 3-divided binary sequences (or words) of length n.

Original entry on oeis.org

0, 0, 0, 2, 7, 23, 54, 132, 290, 634, 1342, 2834, 5868, 12140, 24899, 50929, 103735, 210901, 427623, 865910, 1750505, 3535098, 7131321, 14374647, 28952661, 58280123, 117248217, 235770302, 473897980, 952183214, 1912535827, 3840345963, 7709282937, 15472242645, 31045402788, 62280978042

Offset: 1

N. J. A. Sloane, Mar 17 2012

nonn

A binary sequence (or word) W of length n is 3-divided if it can be written as a concatenation W = XYZ such that XYZ is strictly earlier in lexicographic order than any of the five permutations  XZY, ZYX, YXZ, YZX, ZXY.
More generally, fix an alphabet A = {0,1,2,...,a-1}.
Define lexicographic order on words over A in the obvious way: for single letters, i < j is the natural order; for words U, V, we set U < V iff u_i < v_i at the first place where they differ; also U < UV if V is nonempty, etc.
Then a word U over A is "k-divided over A" if it can be written as U = X_1 X_2 ... X_k in such a way that X is strictly less in lexicographic order than X_pi_1 X_pi_2 ... X_pi_k for all nontrivial permutations pi of [1..k].
All 2^n binary words are 1-divided. For 2-divided words see A209970.
"k-divisible" would sound better to me than "k-divided", but I have followed Lothaire and Pirillo-Varricchio in using the latter term. Neither reference gives this sequence.

			The two 3-divisible binary words of length 4 and the seven of length 5 are as follows. The periods indicate the division w = x.y.z. For example, 0.01.1 is 3-divided since 0011 < all of 0101, 1010, 0101, 1001, 0110.
0.01.1
0.10.1
0.001.1
0.010.1
0.01.10
0.01.11
0.100.1
0.10.11
0.110.1

M. Lothaire, Combinatorics on words. A collective work by Dominique Perrin, Jean Berstel, Christian Choffrut, Robert Cori, Dominique Foata, Jean Eric Pin, Guiseppe Pirillo, Christophe Reutenauer, Marcel-P. Schützenberger, Jacques Sakarovitch and Imre Simon. With a foreword by Roger Lyndon. Edited and with a preface by Perrin. Encyclopedia of Mathematics and its Applications, 17. Addison-Wesley Publishing Co., Reading, Mass., 1983. xix+238 pp. ISBN: 0-201-13516-7, MR0675953 (84g:05002). See p. 144.

Michael S. Branicky, Python program using bitwise operations
Giuseppe Pirillo and Stefano Varricchio, Some combinatorial properties of infinite words and applications to semigroup theory. Proceedings of the 5th Conference on Formal Power Series and Algebraic Combinatorics (Florence, 1993). Discrete Math. 153 (1996), no. 1-3, pages 239-251, MR1394958 (98f:05018).

Number of k-divided words of length n over alphabet of size A:
A=2, k=2,3,4,5: A209970 (and A209919, A000031, A001037), A210109 (and A210145), A210321, A210322;
A=3, k=2,3,4,5: A210323 (and A001867, A027376), A210324, A210325, A210326;
A=4, k=2,3,4: A210424 (and A001868, A027377), A210425, A210426.

# see link for faster, bit-based version
from itertools import product
def is3div(b):
    for i in range(1, len(b)-1):
        for j in range(i+1, len(b)):
            X, Y, Z = b[:i], b[i:j], b[j:]
            if all(b < bp for bp in [Z+Y+X, Z+X+Y, Y+Z+X, Y+X+Z, X+Z+Y]):
                return True
    return False
def a(n): return sum(is3div("".join(b)) for b in product("01", repeat=n))
print([a(n) for n in range(1, 16)]) # Michael S. Branicky, Aug 27 2021

Is there a formula or recurrence?

Values confirmed and a(30)-a(31) by David Applegate, Mar 19 2012

a(32)-a(36) from Michael S. Branicky, Aug 27 2021

A065418 Decimal expansion of Hardy-Littlewood constant Product_{p prime >= 5} (1-(3*p-1)/(p-1)^3).

Original entry on oeis.org

6, 3, 5, 1, 6, 6, 3, 5, 4, 6, 0, 4, 2, 7, 1, 2, 0, 7, 2, 0, 6, 6, 9, 6, 5, 9, 1, 2, 7, 2, 5, 2, 2, 4, 1, 7, 3, 4, 2, 0, 6, 5, 6, 8, 7, 3, 3, 2, 3, 7, 2, 4, 5, 0, 8, 9, 9, 7, 3, 4, 4, 6, 0, 4, 8, 6, 7, 8, 4, 6, 1, 3, 1, 1, 6, 1, 3, 9, 1, 8, 8, 2, 0, 8, 0, 2, 9, 1, 3, 8, 6, 7, 6, 4, 0, 4, 6, 1, 7

Offset: 0

N. J. A. Sloane, Nov 15 2001

For comparison: Product_{n>=5} (1-(3n-1)/(n-1)^3) = 3/8 . - R. J. Mathar, Feb 25 2009

			0.635166354604271207206696591272522417342...

Steven R. Finch, Mathematical Constants, Encyclopedia of Mathematics and its Applications, vol. 94, Cambridge University Press, 2003, Section 2.1, p. 86.

R. J. Mathar, Hardy-Littlewood constants embedded into infinite products over all positive integers, arXiv:0903.2514 [math.NT], 2009-2011, constant C_1^(3).
B. H. Mayoh, The 2nd Goldbach conjecture revisited, BIT 8 (1968) 128-133 Table 5.
G. Niklasch, Some number theoretical constants: 1000-digit values. [Cached copy]

Cf. A066654, A065419, A027376.

$MaxExtraPrecision = 500; digits = 99; terms = 500; P[n_] := PrimeZetaP[n] - 1/2^n - 1/3^n; LR = Join[{0, 0}, LinearRecurrence[{4, -3}, {-6, -24}, terms+10]]; r[n_Integer] := LR[[n]]; Exp[NSum[r[n]*P[n-1]/(n-1), {n, 3, terms}, NSumTerms -> terms, WorkingPrecision -> digits+10]] // RealDigits[#, 10, digits]& // First (* Jean-François Alcover, Apr 17 2016 *)

prodeulerrat(1-(3*p-1)/(p-1)^3, 1, 5) \\ Amiram Eldar, Mar 10 2021

The constant equals Product_{n>=2} (zeta(n)*(1-2^-n)*(1-3^-n))^-A027376(n). - Michael Somos, Apr 05 2003

A054718 Number of ternary sequences with primitive period n.

Original entry on oeis.org

1, 3, 6, 24, 72, 240, 696, 2184, 6480, 19656, 58800, 177144, 530640, 1594320, 4780776, 14348640, 43040160, 129140160, 387400104, 1162261464, 3486725280, 10460350992, 31380882456, 94143178824, 282428998560, 847288609200, 2541864234000, 7625597465304

Offset: 0

N. J. A. Sloane, Apr 20 2000

nonn

Equivalently, output sequences with primitive period n from a simple cycling shift register.

Seiichi Manyama, Table of n, a(n) for n = 0..2095 (terms 0..650 from Alois P. Heinz)
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.

Column k=3 of A143324.

Cf. A027375, A054719, A054720, A054721.

with(numtheory):
a:= n-> `if`(n=0, 1, add(mobius(d)*3^(n/d), d=divisors(n))):
seq(a(n), n=0..30);  # Alois P. Heinz, Oct 21 2012

a[0] = 1; a[n_] := Sum[MoebiusMu[d]*3^(n/d), {d, Divisors[n]}]; Table[a[n], {n, 0, 30}] (* Jean-François Alcover, Mar 11 2014, after Alois P. Heinz *)

a(n) = if(n==0,1,sumdiv(n,d, moebius(d) * 3^(n/d) )); \\ Joerg Arndt, Apr 14 2013

a(n) = Sum_{d|n} mu(d)*3^(n/d).
a(0) = 1, a(n) = n * A027376(n).
a(n) = 3 * A034741(n).
G.f.: 1 + 3 * Sum_{k>=1} mu(k) * x^k / (1 - 3*x^k). - Ilya Gutkovskiy, Apr 14 2021

A102660 List of Lyndon words on {1,2,3} sorted first by length and then lexicographically.

Original entry on oeis.org

1, 2, 3, 12, 13, 23, 112, 113, 122, 123, 132, 133, 223, 233, 1112, 1113, 1122, 1123, 1132, 1133, 1213, 1222, 1223, 1232, 1233, 1322, 1323, 1332, 1333, 2223, 2233, 2333, 11112, 11113, 11122, 11123, 11132, 11133, 11212, 11213, 11222, 11223, 11232

Offset: 1

N. J. A. Sloane, Feb 03 2005

A Lyndon word is primitive (not a power of another word) and is earlier in lexicographic order than any of its cyclic shifts.

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
F. Bassino, J. Clement and C. Nicaud, The standard factorization of Lyndon words: an average point of view, Discrete Math. 290 (2005), 1-25.
Reinhard Zumkeller, Haskell programs for some sequences concerning Lyndon words
Wikipedia, Lyndon word
Index entries for sequences related to Lyndon words

Cf. A074650, A001037, A102659, A210584, A210585.

Cf. A027376.

Haskell
```
cf. link.
```

is_A102660(n)=is_A239016(n)&&is_A239017(n)
for(n=1, 5, p=vector(n, i, 10^(n-i))~; forvec(d=vector(n, i, [1, 3]), is_A102660(m=d*p)&&print1(m", "))) \\ M. F. Hasler, Mar 09 2014

Equals A239016 intersect A239017. - M. F. Hasler, Mar 09 2014

More terms from John W. Layman, Jan 24 2006

Definition improved by Reinhard Zumkeller, Mar 23 2012

A124720 Number of ternary Lyndon words of length n with exactly two 1's.

Original entry on oeis.org

2, 5, 16, 38, 96, 220, 512, 1144, 2560, 5616, 12288, 26592, 57344, 122816, 262144, 556928, 1179648, 2490112, 5242880, 11009536, 23068672, 48233472, 100663296, 209713152, 436207616, 905965568, 1879048192, 3892305920, 8053063680, 16642981888, 34359738368

Offset: 3

Mike Zabrocki, Nov 05 2006

If the offsets are modified, A124720 to A124723 are the 2nd to 5th Witt transform of A000079 [Moree]. - R. J. Mathar, Nov 08 2008

a(n+2) is the number of distinct unordered pairs of binary words having a total length of n letters: a(2+2) = 5 because we have the unordered pairs: (e,00),(e,01), (e,10), (e,11), (0,1) where e represents the empty word. Each pair has a total of 2 letters and the two elements of each pair are distinct words. - Geoffrey Critzer, Feb 28 2013

			a(4) = 5 because 1122, 1123, 1132, 1213, 1133 are all Lyndon words on 3 letters with 2 ones.

Colin Barker, Table of n, a(n) for n = 3..1000
Pieter Moree, The formal series Witt transform, Discr. Math. no. 295 vol. 1-3 (2005) 143-160. [From _R. J. Mathar_, Nov 08 2008]
Index entries for linear recurrences with constant coefficients, signature (4,-2,-8,8).

Cf. A051168, A027376, A124721, A124722, A124723.

nn=30;Drop[CoefficientList[Series[(1/(1-2x)^2-1/(1-2x^2))/2,{x,0,nn}],x],1] (* Geoffrey Critzer, Feb 28 2013 *)

Vec(x^3*(2-3*x)/((1-2*x)^2*(1-2*x^2)) + O(x^40)) \\ Colin Barker, Oct 28 2016

G.f.: x^3*(2-3 x)/((1-2 x^2)(1- 2x)^2) = (x^2/(1-2x)^2 - x^2/(1-2*x^2))/2.
From Colin Barker, Oct 28 2016: (Start)
a(n) = 2^(n-3)*(n-1)-2^(n/2-2) for n even.
a(n) = 2^(n-3)*n-2^(n-3) for n odd.
a(n) = 4*a(n-1)-2*a(n-2)-8*a(n-3)+8*a(n-4) for n>6.
(End)

A124814 Triangle of number of 4-ary Lyndon words of length n containing exactly k 1s.

Original entry on oeis.org

1, 3, 1, 3, 3, 0, 8, 9, 3, 0, 18, 27, 12, 3, 0, 48, 81, 54, 18, 3, 0, 116, 243, 198, 89, 21, 3, 0, 312, 729, 729, 405, 135, 27, 3, 0, 810, 2187, 2538, 1701, 702, 189, 30, 3, 0, 2184, 6561, 8748, 6801, 3402, 1134, 251, 36, 3, 0, 5880, 19683, 29484, 26244, 15282, 6123, 1692

Offset: 0

Mike Zabrocki, Nov 08 2006

Row sums given by A027377, first column given by A027376, second column given by A000244, third through sixth columns (k=2,3,4,5) given by A124810, A124811, A124812, A124813, third diagonal given by 3*A032766.

			T(4,2) = 12 because the words 11ab, 11ba, 1a1b for ab=23, 24, 34 and 11aa for a=2,3,4 are all Lyndon and of length 4 with exactly two 1s.
From _Andrew Howroyd_, Mar 26 2017: (Start)
Triangle starts
*   1
*   3    1
*   3    3    0
*   8    9    3    0
*  18   27   12    3   0
*  48   81   54   18   3   0
* 116  243  198   89  21   3  0
* 312  729  729  405 135  27  3 0
* 810 2187 2538 1701 702 189 30 3 0
(End)

Andrew Howroyd, Table of n, a(n) for n = 0..1274

Cf. A051168, A123223, A027377, A124810, A124811, A124812, A124813.

C:=combinat[numbcomb]:mu:=numtheory[mobius]:divs:=numtheory[divisors]: T:=proc(n,k) local d; if k>0 then add(mu(d)*C(n/d-1,(n-k)/d)*3^((n-k)/d),d=divs(n) intersect divs(k))/k; elif n>0 then 1/n*add(mu(d)*3^(n/d),d=divs(n)); else 1; fi; end; [seq([seq(T(n,k),k=0..n)],n=0..10)];

nmax = 10; col[0] = Table[If[n == 0, 1, 1/n* DivisorSum[n, MoebiusMu[#]* 3^(n/#)&]], {n, 0, nmax}]; col[k_] := x^k/k * DivisorSum[k, MoebiusMu[#] / (1 - 3*x^#)^(k/#)&] + O[x]^(nmax+2) // CoefficientList[#, x]&; Table[ col[k][[n+1]], {n, 0, nmax}, {k, 0, n}] // Flatten (* Jean-François Alcover, Sep 19 2017 *)

T(n,0) = 1/n*Sum_{d|n} mu(d)*3^(n/d) = A027376(n).
T(n,n-1) = 3 for k>0.
T(n,k) = 1/k*Sum_{d|k,d|n} mu(d) C(n/d-1,(n-k)/d )*3^((n-k)/d) = 1/(n-k)*Sum_{d|k,d|n} mu(d) C(n/d-1,k/d)*3^((n-k)/d).
O.g.f. of columns: Sum_n T(n,k) x^n = x^k/k*Sum_{d|k} mu(d)*1/(1-3*x^d)^(k/d).
O.g.f. of diagonals: Sum_n T(n,n-k) x^n = x^k/k*Sum_{d|k} mu(d)*(3/(1-x^d))^(k/d).

cp's OEIS Frontend

A058818 a(0) = 1, a(1) = 3; for n >= 2 a(n) is the number of degree-n monic reducible polynomials over GF(3), i.e., a(n) = 3^n - A027376(n).

Views

Author

Keywords

Comments

References

Crossrefs

Programs

Mathematica

PARI

Extensions

A074650 Table T(n,k) read by downward antidiagonals: number of Lyndon words (aperiodic necklaces) with n beads of k colors, n >= 1, k >= 1.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Magma

Maple

Mathematica

PARI

Sage

Formula

A027377 Number of irreducible polynomials of degree n over GF(4); dimensions of free Lie algebras.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A059885 a(n) = |{m : multiplicative order of 3 mod m = n}|.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A210109 Number of 3-divided binary sequences (or words) of length n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Python

Formula

Extensions

A065418 Decimal expansion of Hardy-Littlewood constant Product_{p prime >= 5} (1-(3*p-1)/(p-1)^3).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula