A025142 -id:A025142 - cp's OEIS frontend

A001037 Number of degree-n irreducible polynomials over GF(2); number of n-bead necklaces with beads of 2 colors when turning over is not allowed and with primitive period n; number of binary Lyndon words of length n.

1, 2, 1, 2, 3, 6, 9, 18, 30, 56, 99, 186, 335, 630, 1161, 2182, 4080, 7710, 14532, 27594, 52377, 99858, 190557, 364722, 698870, 1342176, 2580795, 4971008, 9586395, 18512790, 35790267, 69273666, 134215680, 260300986, 505286415, 981706806, 1908866960, 3714566310, 7233615333, 14096302710, 27487764474

Offset: 0

N. J. A. Sloane

Also dimensions of free Lie algebras - see A059966, which is essentially the same sequence.
This sequence also represents the number N of cycles of length L in a digraph under x^2 seen modulo a Mersenne prime M_q=2^q-1. This number does not depend on q and L is any divisor of q-1. See Theorem 5 and Corollary 3 of the Shallit and Vasiga paper: N=sum(eulerphi(d)/order(d,2)) where d is a divisor of 2^(q-1)-1 such that order(d,2)=L. - Tony Reix, Nov 17 2005
Except for a(0) = 1, Bau-Sen Du's [1985/2007] Table 1, p. 6, has this sequence as the 7th (rightmost) column. Other columns of the table include (but are not identified as) A006206-A006208. - Jonathan Vos Post, Jun 18 2007
"Number of binary Lyndon words" means: number of binary strings inequivalent modulo rotation (cyclic permutation) of the digits and not having a period smaller than n. This provides a link to A103314, since these strings correspond to the inequivalent zero-sum subsets of U_m (m-th roots of unity) obtained by taking the union of U_n (n|m) with 0 or more U_d (n | d, d | m) multiplied by some power of exp(i 2Pi/n) to make them mutually disjoint. (But not all zero-sum subsets of U_m are of that form.) - M. F. Hasler, Jan 14 2007
Also the number of dynamical cycles of period n of a threshold Boolean automata network which is a quasi-minimal positive circuit of size a multiple of n and which is updated in parallel. - Mathilde Noual (mathilde.noual(AT)ens-lyon.fr), Feb 25 2009
Also, the number of periodic points with (minimal) period n in the iteration of the tent map f(x):=2min{x,1-x} on the unit interval. - Pietro Majer, Sep 22 2009
Number of distinct cycles of minimal period n in a shift dynamical system associated with a totally disconnected hyperbolic iterated function system (see Barnsley link). - Michel Marcus, Oct 06 2013
From Jean-Christophe Hervé, Oct 26 2014: (Start)
For n > 0, a(n) is also the number of orbits of size n of the transform associated to the Kolakoski sequence A000002 (and this is true for any map with 2^n periodic points of period n). The Kolakoski transform changes a sequence of 1's and 2's by the sequence of the lengths of its runs. The Kolakoski sequence is one of the two fixed points of this transform, the other being the same sequence without the initial term. A025142 and A025143 are the periodic points of the orbit of size 2. A027375(n) = n*a(n) gives the number of periodic points of minimal period n.
For n > 1, this sequence is equal to A059966 and to A060477, and for n = 1, a(1) = A059966(1)+1 = A060477(1)-1; this because the n-th term of all 3 sequences is equal to (1/n)*sum_{d|n} mu(n/d)*(2^d+e), with e = -1/0/1 for resp. A059966/this sequence/A060477, and sum_{d|n} mu(n/d) equals 1 for n = 1 and 0 for all n > 1. (End)
Warning: A000031 and A001037 are easily confused, since they have similar formulas.
From Petros Hadjicostas, Jul 14 2020: (Start)
Following Kam Cheong Au (2020), let d(w,N) be the dimension of the Q-span of weight w and level N of colored multiple zeta values (CMZV). Here Q are the rational numbers.
Deligne's bound says that d(w,N) <= D(w,N), where 1 + Sum_{w >= 1} D(w,N)*t^w = (1 - a*t + b*t^2)^(-1) when N >= 3, where a = phi(N)/2 + omega(N) and b = omega(N) - 1 (with omega(N) = A001221(N) being the number of distinct primes of N).
For N = 3, a = phi(3)/2 + omega(3) = 2/2 + 1 = 2 and b = omega(3) - 1 = 0. It follows that D(w, N=3) = A000079(w) = 2^w.
For some reason, Kam Cheong Au (2020) assumes Deligne's bound is tight, i.e., d(w,N) = D(w,N). He sets Sum_{w >= 1} c(w,N)*t^w = log(1 + Sum_{w >= 1} d(w,N)*t^w) = log(1 + Sum_{w >= 1} D(w,N)*t^w) = -log(1 - a*t + b*t^2) for N >= 3.
For N = 3, we get that c(w, N=3) = A000079(w)/w = 2^w/w.
He defines d*(w,N) = Sum_{k | w} (mu(k)/k)*c(w/k,N) to be the "number of primitive constants of weight w and level N". (Using the terminology of A113788, we may perhaps call d*(w,N) the number of irreducible colored multiple zeta values at weight w and level N.)
Using standard techniques of the theory of g.f.'s, we can prove that Sum_{w >= 1} d*(w,N)*t^w = Sum_{s >= 1} (mu(s)/s) Sum_{k >= 1} c(k,N)*(t^s)^k = -Sum_{s >= 1} (mu(s)/s)*log(1 - a*t^s + b*t^(2*s)).
For N = 3, we saw that a = 2 and b = 0, and hence d*(w, N=3) = a(w) = Sum_{k | w} (mu(k)/k) * 2^(w/k) / (w/k) = (1/w) * Sum_{k | w} mu(k) * 2^(w/k) for w >= 1. See Table 1 on p. 6 in Kam Cheong Au (2020). (End)

			Binary strings (Lyndon words, cf. A102659):
a(0) = 1 = #{ "" },
a(1) = 2 = #{ "0", "1" },
a(2) = 1 = #{ "01" },
a(3) = 2 = #{ "001", "011" },
a(4) = 3 = #{ "0001", "0011", "0111" },
a(5) = 6 = #{ "00001", "00011", "00101", "00111", "01011", "01111" }.

Michael F. Barnsley, Fractals Everywhere, Academic Press, San Diego, 1988, page 171, Lemma 3.
E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, NY, 1968, p. 84.
E. L. Blanton, Jr., S. P. Hurd and J. S. McCranie. On the digraph defined by squaring mod m, when m has primitive roots. Congr. Numer. 82 (1991), 167-177.
P. J. Freyd and A. Scedrov, Categories, Allegories, North-Holland, Amsterdam, 1990. See 1.925.
M. Lothaire, Combinatorics on Words, Addison-Wesley, Reading, MA, 1983, pp. 65, 79.
Robert M. May, "Simple mathematical models with very complicated dynamics." Nature, Vol. 261, June 10, 1976, pp. 459-467; reprinted in The Theory of Chaotic Attractors, pp. 85-93. Springer, New York, NY, 2004. The sequences listed in Table 2 are A000079, A027375, A000031, A001037, A000048, A051841. - N. J. A. Sloane, Mar 17 2019
Guy Melançon, Factorizing infinite words using Maple, MapleTech Journal, vol. 4, no. 1, 1997, pp. 34-42, esp. p. 36.
M. R. Nester, (1999). Mathematical investigations of some plant interaction designs. PhD Thesis. University of Queensland, Brisbane, Australia. [See A056391 for pdf file of Chap. 2]
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence in entries N0046 and N0287).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Seiichi Manyama, Table of n, a(n) for n = 0..3333 (terms 0..200 from T. D. Noe)
Per Alexandersson and Joakim Uhlin, Cyclic sieving, skew Macdonald polynomials and Schur positivity, arXiv:1908.00083 [math.CO], 2019.
Nicolas Andrews, Lucas Gagnon, Félix Gélinas, Eric Schlums, and Mike Zabrocki, When are Hopf algebras determined by integer sequences?, arXiv:2505.06941 [math.CO], 2025. See p. 17.
Joerg Arndt, Matters Computational (The Fxtbook), pp.379-383, pp.843-845.
Kam Cheong Au, Evaluation of one-dimensional polylogarithmic integral, with applications to infinite series, arXiv:2007.03957 [math.NT], 2020. See 3rd line of Table 1 (p. 6).
E. L. Blanton, Jr., S. P. Hurd and J. S. McCranie, On a digraph defined by squaring modulo n, Fibonacci Quart. 30 (1992), 322-333.
P. J. Cameron, Sequences realized by oligomorphic permutation groups, J. Integ. Seqs. Vol. 3 (2000), #00.1.5.
Émilie Charlier, Manon Philibert, and Manon Stipulanti, Nyldon words, arXiv:1804.09735 [math.CO], 2018. Also J. Comb. Thy. A, 167 (2019), 60-90.
R. Church, Tables of irreducible polynomials for the first four prime moduli, Annals Math., 36 (1935), 198-209.
J. Demongeot, M. Noual and S. Sene, On the number of attractors of positive and negative threshold Boolean automata circuits, 2010 IEEE 24th Intl. Conf. Advan. Inf. Network. Appl. Workshops (WAINA), p 782-789.
Joscha Diehl, Rosa Preiß, and Jeremy Reizenstein, Conjugation, loop and closure invariants of the iterated-integrals signature, arXiv:2412.19670 [math.RA], 2024. See p. 6.
Bau-Sen Du, The Minimal Number of Periodic Orbits of Periods Guaranteed in Sharkovskii's Theorem, arXiv:0706.2297 [math.DS], 2007; Bull. Austral. Math. Soc. 31(1985), 89-103. Corrigendum: 32 (1985), 159.
S. V. Duzhin and D. V. Pasechnik, Groups acting on necklaces and sandpile groups, 2014. See page 85. - _N. J. A. Sloane_, Jun 30 2014
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
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.
A. Knopfmacher and M. E. Mays, Graph Compositions I: Basic enumeration, Integers 1 (2001), A4, eq. (1).
T. Laarhoven and B de Weger, The Collatz conjecture and De Bruijn graphs, arXiv preprint arXiv:1209.3495 [math.NT], 2012. - From _N. J. A. Sloane_, Dec 27 2012
J. C. Lagarias, The set of rational cycles for the 3x+1 problem, Acta Arithmetica, LVI (1990), pp. 33-53.
Piotr Laskawiec, Joint Spectral Radius with focus on pairs of 2 X 2 matrices, Ph. D. Dissertation, Penn. State Univ. (2025). See p. 55.
R. J. Mathar, Hardy-Littlewood constants embedded into infinite products over all positive integers, sequence gamma_{2,j}^(T), arXiv:0903.2514 [math.NT], 2009-2011.
Ueli M. Maurer, Asymptotically-tight bounds on the number of cycles in generalized de Bruijn-Good graphs, Discrete applied mathematics 37 (1992): 421-436. See Table 1.
Romeo Meštrović, Different classes of binary necklaces and a combinatorial method for their enumerations, arXiv:1804.00992 [math.CO], 2018.
H. Meyn and W. Götz, Self-reciprocal polynomials over finite fields, Séminaire Lotharingien de Combinatoire, B21d (1989), 8 pp.
J.-F. Michon and P. Ravache, On different families of invariant irreducible polynomials over F_2, Finite fields & Applications 16 (2010) 163-174.
Hans Z. Munthe-Kaas and Jonatan Stava, Lie Admissible Triple Algebras: The Connection Algebra of Symmetric Spaces, arXiv:2306.15582 [math.DG], 2023.
Mathilde Noual, Dynamics of Circuits and Intersecting Circuits, in Language and Automata Theory and Applications, Lecture Notes in Computer Science, 2012, Volume 7183/2012, 433-444, ArXiv 1011.3930 [cs.DM]. - _N. J. A. Sloane_, Jul 07 2012
Cormac O'Sullivan, Topographs for binary quadratic forms and class numbers, arXiv:2408.14405 [math.NT], 2024. See p. 30.
George Petrides and Johannes Mykkeltveit, On the Classification of Periodic Binary Sequences into Nonlinear Complexity Classes, in Sequences and Their Applications SETA 2006, Lecture Notes in Computer Science, Volume 4086/2006, pp 209-222. [From _N. J. A. Sloane_, Jul 09 2009]
Y. Puri and T. Ward, Arithmetic and growth of periodic orbits, J. Integer Seqs., Vol. 4 (2001), #01.2.1.
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc.
F. Ruskey, Primitive and Irreducible Polynomials
F. Ruskey, Necklaces, Lyndon words, De Bruijn sequences, etc. [Cached copy, with permission, pdf format only]
Troy Vasiga and Jeffrey Shallit, On the iteration of certain quadratic maps over GF(p), Discrete Mathematics, Volume 277, Issues 1-3, 2004, pages 219-240.
G. Viennot, Algèbres de Lie Libres et Monoïdes Libres, Lecture Notes in Mathematics 691, Springer Verlag 1978.
M. Waldschmidt, Lectures on Multiple Zeta Values, IMSC 2011.
Eric Weisstein's World of Mathematics, Irreducible Polynomial
Eric Weisstein's World of Mathematics, Lyndon Word
Wikipedia, Lyndon word
Index entries for sequences related to Lyndon words
Index entries for "core" sequences

Column 2 of A074650.
Row sums of A051168, which gives the number of Lyndon words with fixed number of zeros and ones.
Euler transform is A000079.
See A058943 and A102569 for initial terms. See also A058947, A011260, A059966.
Irreducible over GF(2), GF(3), GF(4), GF(5), GF(7): A058943, A058944, A058948, A058945, A058946. Primitive irreducible over GF(2), GF(3), GF(4), GF(5), GF(7): A058947, A058949, A058952, A058950, A058951.
Cf. A000031 (n-bead necklaces but may have period dividing n), A014580, A046211, A046209, A006206-A006208, A038063, A060477, A103314.
Cf. A027750, A008683, A254040.
See also A102659 for the list of binary Lyndon words themselves.
Cf. A000010, A008683.

a001037 0 = 1
a001037 n = (sum $ map (\d -> (a000079 d) * a008683 (n `div` d)) $
                       a027750_row n) `div` n
-- Reinhard Zumkeller, Feb 01 2013

with(numtheory): A001037 := proc(n) local a,d; if n = 0 then RETURN(1); else a := 0: for d in divisors(n) do a := a+mobius(n/d)*2^d; od: RETURN(a/n); fi; end;

f[n_] := Block[{d = Divisors@ n}, Plus @@ (MoebiusMu[n/d]*2^d/n)]; Array[f, 32]

A001037(n)=if(n>1,sumdiv(n,d,moebius(d)*2^(n/d))/n,n+1) \\ Edited by M. F. Hasler, Jan 11 2016

{a(n)=polcoeff(1-sum(k=1,n,moebius(k)/k*log(1-2*x^k+x*O(x^n))),n)} \\ Paul D. Hanna, Oct 13 2010

a(n)=if(n>1,my(s);forstep(i=2^n+1,2^(n+1),2,s+=polisirreducible(Mod(1,2) * Pol(binary(i))));s,n+1) \\ Charles R Greathouse IV, Jan 26 2012

from sympy import divisors, mobius
def a(n): return sum(mobius(d) * 2**(n//d) for d in divisors(n))/n if n>1 else n + 1 # Indranil Ghosh, Apr 26 2017

For n >= 1:
a(n) = (1/n)*Sum_{d | n} mu(n/d)*2^d.
A000031(n) = Sum_{d | n} a(d).
2^n = Sum_{d | n} d*a(d).
a(n) = A027375(n)/n.
a(n) = A000048(n) + A051841(n).
For n > 1, a(n) = A059966(n) = A060477(n).
G.f.: 1 - Sum_{n >= 1} moebius(n)*log(1 - 2*x^n)/n, where moebius(n) = A008683(n). - Paul D. Hanna, Oct 13 2010
From Richard L. Ollerton, May 10 2021: (Start)
For n >= 1:
a(n) = (1/n)*Sum_{k=1..n} mu(gcd(n,k))*2^(n/gcd(n,k))/phi(n/gcd(n,k)).
a(n) = (1/n)*Sum_{k=1..n} mu(n/gcd(n,k))*2^gcd(n,k)/phi(n/gcd(n,k)). (End)
a(n) ~ 2^n / n. - Vaclav Kotesovec, Aug 11 2021

Revised by N. J. A. Sloane, Jun 10 2012

A027375 Number of aperiodic binary strings of length n; also number of binary sequences with primitive period n.

Original entry on oeis.org

0, 2, 2, 6, 12, 30, 54, 126, 240, 504, 990, 2046, 4020, 8190, 16254, 32730, 65280, 131070, 261576, 524286, 1047540, 2097018, 4192254, 8388606, 16772880, 33554400, 67100670, 134217216, 268419060, 536870910, 1073708010, 2147483646, 4294901760

Offset: 0

N. J. A. Sloane

A sequence S is aperiodic if it is not of the form S = T^k with k>1. - N. J. A. Sloane, Oct 26 2012
Equivalently, number of output sequences with primitive period n from a simple cycling shift register. - Frank Ruskey, Jan 17 2000
Also, the number of nonempty subsets A of the set of the integers 1 to n such that gcd(A) is relatively prime to n (for n>1). - R. J. Mathar, Aug 13 2006; range corrected by Geoffrey Critzer, Dec 07 2014
Without the first term, this sequence is the Moebius transform of 2^n (n>0). For n > 0, a(n) is also the number of periodic points of period n of the transform associated to the Kolakoski sequence A000002. This transform changes a sequence of 1's and 2's by the sequence of the lengths of its runs. The Kolakoski sequence is one of the two fixed points of this transform, the other being the same sequence without the initial term. A025142 and A025143 are the 2 periodic points of period 2. A001037(n) = a(n)/n gives the number of orbits of size n. - Jean-Christophe Hervé, Oct 25 2014
From Bernard Schott, Jun 19 2019: (Start)
There are 2^n strings of length n that can be formed from the symbols 0 and 1; in the example below with a(3) = 6, the last two strings that are not aperiodic binary strings are { 000, 111 }, corresponding to 0^3 and 1^3, using the notation of the first comment.
Two properties mentioned by Krusemeyer et al. are:
1) For any n > 2, a(n) is divisible by 6.
2) Lim_{n->oo} a(n+1)/a(n) = 2. (End)

			a(3) = 6 = |{ 001, 010, 011, 100, 101, 110 }|. - corrected by _Geoffrey Critzer_, Dec 07 2014

J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 13. - From N. J. A. Sloane, Oct 26 2012
E. R. Berlekamp, Algebraic Coding Theory, McGraw-Hill, NY, 1968, p. 84.
Blanchet-Sadri, Francine. Algorithmic combinatorics on partial words. Chapman & Hall/CRC, Boca Raton, FL, 2008. ii+385 pp. ISBN: 978-1-4200-6092-8; 1-4200-6092-9 MR2384993 (2009f:68142). See p. 164.
S. W. Golomb, Shift-Register Sequences, Holden-Day, San Francisco, 1967.
Mark I. Krusemeyer, George T. Gilbert, Loren C. Larson, A Mathematical Orchard, Problems and Solutions, MAA, 2012, Problem 128, pp. 225-227.

T. D. Noe, Table of n, a(n) for n = 0..300
J.-P. Allouche, Note on the transcendence of a generating function. In A. Laurincikas and E. Manstavicius, editors, Proceedings of the Palanga Conference for the 75th birthday of Prof. Kubilius, New trends in Probab. and Statist., Vol. 4, pages 461-465, 1997.
B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, arXiv:1212.6102 [math.CO], Dec 25 2012.
B. Chaffin, J. P. Linderman, N. J. A. Sloane and Allan Wilks, On Curling Numbers of Integer Sequences, Journal of Integer Sequences, Vol. 16 (2013), Article 13.4.3.
John D. Cook, Counting primitive bit strings (2014).
P. Flajolet and R. Sedgewick, Analytic Combinatorics, 2009; see page 85.
Guilhem Gamard, Gwenaël Richomme, Jeffrey Shallit and Taylor J. Smith, Periodicity in rectangular arrays, arXiv:1602.06915 [cs.DM], 2016; Information Processing Letters 118 (2017) 58-63. See Table 1.
O. Georgiou, C. P. Dettmann and E. G. Altmann, Faster than expected escape for a class of fully chaotic maps, arXiv preprint arXiv:1207.7000 [nlin.CD], 2012. - From _N. J. A. Sloane_, Dec 23 2012
E. N. Gilbert and J. Riordan, Symmetry types of periodic sequences, Illinois J. Math., 5 (1961), 657-665.
David W. Lyons, Cristina Mullican, Adam Rilatt, and Jack D. Putnam, Werner states from diagrams, arXiv:2302.05572 [quant-ph], 2023.
Robert M. May, Simple mathematical models with very complicated dynamics, Nature, Vol. 261, June 10, 1976, pp. 459-467; reprinted in The Theory of Chaotic Attractors, pp. 85-93. Springer, New York, NY, 2004. The sequences listed in Table 2 are A000079, A027375, A000031, A001037, A000048, A051841. - _N. J. A. Sloane_, Mar 17 2019
M. B. Nathanson, Primitive sets and Euler phi function for subsets of {1,2,...,n}, arXiv:math/0608150 [math.NT], 2006-2007.
P. Pongsriiam, Relatively Prime Sets, Divisor Sums, and Partial Sums, arXiv:1306.4891 [math.NT], 2013 and J. Int. Seq. 16 (2013) #13.9.1.
P. Pongsriiam, A remark on relative prime sets, arXiv:1306.2529 [math.NT], 2013.
P. Pongsriiam, A remark on relative prime sets, Integers 13 (2013), A49.
R. C. Read, Combinatorial problems in the theory of music, Disc. Math. 167/168 (1997) 543-551, sequence A(n).
M. Tang, Relatively Prime Sets and a Phi Function for Subsets of {1, 2, ... , n}, J. Int. Seq. 13 (2010) # 10.7.6.
László Tóth, Menon-type identities concerning subsets of the set {1,2,...,n}, arXiv:2109.06541 [math.NT], 2021.

A038199 and A056267 are essentially the same sequence with different initial terms.
Cf. A020921, A216953.
Column k=2 of A143324.

a027375 n = n * a001037 n  -- Reinhard Zumkeller, Feb 01 2013

with(numtheory): A027375 :=n->add( mobius(d)*2^(n/d), d = divisors(n)); # N. J. A. Sloane, Sep 25 2012

Table[ Apply[ Plus, MoebiusMu[ n / Divisors[n] ]*2^Divisors[n] ], {n, 1, 32} ]
a[0]=0; a[n_] := DivisorSum[n, MoebiusMu[n/#]*2^#&]; Array[a, 40, 0] (* Jean-François Alcover, Dec 01 2015 *)

PARI
```
a(n) = sumdiv(n,d,moebius(n\d)*2^d);
```

from sympy import mobius, divisors
def a(n): return sum(mobius(d)*2**(n//d) for d in divisors(n))
print([a(n) for n in range(101)]) # Indranil Ghosh, Jun 28 2017

a(n) = Sum_{d|n} mu(d)*2^(n/d).
a(n) = 2*A000740(n).
a(n) = n*A001037(n).
Sum_{d|n} a(n) = 2^n.
a(p) = 2^p - 2 for p prime. - R. J. Mathar, Aug 13 2006
a(n) = 2^n - O(2^(n/2)). - Charles R Greathouse IV, Apr 28 2016
a(n) = 2^n - A152061(n). - Bernard Schott, Jun 20 2019
G.f.: 2 * Sum_{k>=1} mu(k)*x^k/(1 - 2*x^k). - Ilya Gutkovskiy, Nov 11 2019

A378282 Irregular triangular T: (row 1) = (1); (row n+1) = inverse runlength sequence of row n, starting with 2 if r = 3k for some k, and 1 otherwise. See Comments.

Original entry on oeis.org

1, 1, 2, 1, 1, 1, 2, 2, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 1, 1, 2, 1, 2, 2, 1, 2, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 1, 2, 2, 1, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1

Offset: 1

Clark Kimberling, Dec 08 2024

For present purposes, all sequences to be considered consist entirely of 1s and 2s. If u and v are such sequences (infinite or finite), we call v an inverse runlength sequence of u if u is the runlength sequence of v. Each u has two inverse runlength sequences, one with first term 1 and the other with first term 2. Consequently, an inverse runlength array, in which each row after the first is an inverse runlength sequence of the preceding row, is determined by its first column. In this array, the first column is periodic with period 1,1,2. As a result, the array has three limiting sequences: A378283, A378284, A378285.
Generally, if the first column is periodic with fundamental period p, then the array has p distinct limiting sequences; otherwise, there is no limiting sequence; however, if a segment, of any length, occurs in a row, then it also occurs in a subsequent row.
This guide is a table of four columns:
col 1: (row 1 of A)
col 2: fundamental period of column 1 of A
col 3: limiting sequence of array (possibly several)
col 4: runlength sequence of sequence in column 3
***
col 1  col 2       col 3        col 4
(1)     (1)        A000002      A000002
(1)     (1,2)      A025142      A025143
(2)     (2,1)      A025143      A025142
(1)     (1,1,2)    A378283      A378285
(1)     (1,2,1)    A378284      A378283
(2)     (2,1,1)    A378285      A378284
(1)     (1,1,2)    A378304      A378306
(2)     (2,1,2)    A378305      A378304
(2)     (2,2,1)    A378306      A378305

			First eleven rows:
  1
  1
  2
  1  1
  1  2
  2  1  1
  1  1  2  1
  1  2  1  1  2
  2  1  1  2  1  2  2
  1  1  2  1  2  2  1  2  2  1  1
  1  2  1  1  2  1  1  2  2  1  2  2  1  1  2  2  1
(row 8) = (1,2,1,1,2) has runlength sequence (1,1,2,1) = (row 7).

Cf. A270641, A378284, A378285, A378286 (row lengths).

invRE[seq_, k_] := Flatten[Map[ConstantArray[#[[2]], #[[1]]] &,
    Partition[Riffle[seq, {k, 2 - Mod[k + 1, 2]}, {2, -1, 2}], 2]]];
row1 = {1}; rows = {row1};
col = PadRight[{}, 18, {1, 1, 2}]
Do[AppendTo[rows, invRE[Last[rows], col[[n]]]], {n, 2, Length[col]}]
rows // ColumnForm  (* array *)
Flatten[rows]  (* sequence *)
(* Peter J. C. Moses, Nov 21 2024 *)

A288723 First sequence of a Kolakoski 3-Ouroboros, i.e., sequence of 1s, 2s and 3s that begins a chain of three distinct sequences where successive run-length encodings produce seq(1) -> seq(2) -> seq(3) -> seq(1).

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 1, 1, 1, 2, 3, 1, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 2, 3, 3, 1, 1, 1, 2, 3, 3, 1, 1, 2, 2, 2, 3, 3, 3, 1, 2, 3, 3, 1, 1, 2, 2, 3, 3, 3, 1, 2, 3, 3, 1, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 1, 2, 2, 2, 3, 1, 2, 2, 3, 3, 1, 1

Offset: 1

Anthony Sand, Jun 14 2017

nonn

The Kolakoski sequence, A000002, is its own run-length encoding: if you write down the lengths of the runs of 1 and 2, the same sequence reappears, i.e., A000002 = runlength(A000002). Next, runlength(A025142) = A025143 and runlength(A025143) = A025142. The run-lengths of the sequence above yield a second sequence whose run-lengths yield a third sequence whose run-lengths yield the original sequence:
seq(1) = 1,1,2,2,3,3,1,1,1,2,3,1,1,2,2,3,3,3,1,1,1,2,2,2,3,1,2,3,3,1,1,1,2,3,3,...
seq(2) = 2,2,2,3,1,1,2,2,3,3,3,1,1,1,2,3,1,2,2,3,3,1,1,2,2,2,3,1,1,2,2,2,3,3,3,...
seq(3) = 3,1,2,2,3,3,1,1,1,2,2,2,3,1,2,3,3,1,1,1,2,3,1,1,2,2,3,3,3,1,1,1,2,2,2,...
It seems possible to create arbitrarily long chains of distinct integer sequences, seq(1), seq(2)..seq(n), in which runlength(seq(i)) = seq(i+1) for (i=1,n-1) and runlength(seq(n)) = seq(1). When n=5, one possible chain is:
seq(1) = 1,1,2,2,3,3,4,4,4,5,5,5,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,5,...
seq(2) = 2,2,2,3,3,3,4,4,4,5,5,5,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,5,5,5,5,5,...
seq(3) = 3,3,3,3,4,4,4,4,5,5,5,5,1,1,1,1,2,2,2,2,3,3,3,3,3,4,5,1,1,2,2,3,3,3,...
seq(4) = 4,4,4,4,4,5,1,1,2,2,3,3,3,4,4,4,5,5,5,5,1,1,1,1,2,2,2,2,3,3,3,3,3,...
seq(5) = 5,1,2,2,3,3,4,4,4,5,5,5,1,1,1,1,2,2,2,2,3,3,3,3,4,4,4,4,4,...
When n=10, one possible chain begins and ends:
seq(1) = 1,1,2,2,3,3,4,4,4,5,5,5,6,6,6,7,7,7,7,8,8,8,8,9,9,9,9,10,10,10,10,10,...
[...]
seq(10) = 10,1,2,2,3,3,4,4,4,5,5,5,6,6,6,6,7,7,7,7,8,8,8,8,9,9,9,9,9,10,10,10,10,10,...
These chains might be called Kolakoski n-Ouroboroi, after the legendary serpent Ouroboros that bites its own tail. This sequence, A288723, is the first of one possible 3-Ouroboros, but any set of three distinct integers can seed a 3-Ouroboros. If the seed is (2,3,5), the 3-Ouroboros is:
seq(1) = 2,2,2,3,3,3,5,5,5,2,2,2,3,3,3,5,5,5,5,5,2,2,2,2,2,3,3,3,3,3,5,5,5,5,5,...
seq(2) = 3,3,3,3,3,5,5,5,5,5,2,2,3,3,5,5,5,2,2,2,3,3,3,3,3,5,5,5,5,5,2,2,2,2,2,...
seq(3) = 5,5,2,2,3,3,5,5,5,2,2,2,3,3,3,5,5,5,5,5,2,2,2,2,2,3,3,3,3,3,5,5,2,2,3,3,...
For n > 3, the integer set can repeat integers if the same integer does not occur consecutively or at the beginning and end of the set. If the seed is (1,2,1,3), the 4-Ouroboros is:
seq(1) = 1,1,2,1,1,1,3,1,2,1,1,3,1,1,1,2,2,2,1,3,1,1,2,1,3,1,1,1,2,2,2,1,1,1,...
seq(2) = 2,1,3,1,1,1,2,1,3,3,1,1,2,1,1,1,3,3,3,1,1,1,2,1,1,3,3,1,2,1,1,1,3,3,3,...
seq(3) = 1,1,1,3,1,1,2,2,1,3,3,3,1,2,2,1,1,3,3,1,2,2,2,1,1,1,3,1,1,2,1,3,1,1,1,...
seq(4) = 3,1,2,2,1,3,1,2,2,2,1,3,3,1,2,1,1,1,3,1,2,1,1,3,3,1,1,2,1,1,1,3,1,2,2,...
The existence of Kolakoski p-Ouroboros sequences for any positive integer p is proved in my paper 'What Is the Long Range Order in the Kolakoski Sequence?' from 1997. - Michel Dekking, Feb 05 2018

			Write down the run-lengths of the sequence, or the lengths of the runs of 1s, 2s and 3s. This yields a second and different sequence of 1s, 2s and 3s, A288724. The run-lengths of this second sequence yield a third and different sequence, A288725. The run-lengths of this third sequence yield the original sequence. For example, bracket the runs of distinct integers, then replace the original digits with the run-lengths to create the second sequence:
(1,1), (2,2), (3,3), (1,1,1), (2), (3), (1,1), (2,2), (3,3,3), (1,1,1), (2,2,2), (3), (1), (2), (3,3), (1,1,1), (2), (3,3), (1,1), (2,2,2), ... -> 2, 2, 2, 3, 1, 1, 2, 2, 3, 3, 3, 1, 1, 1, 2, 3, 1, 2, 2, 3, ...
Apply the same process to the second sequence and the third sequence appears:
(2,2,2), (3), (1,1), (2,2), (3,3,3), (1,1,1), (2), (3), (1), (2,2), (3,3), (1,1), (2,2,2), (3), (1,1), (2,2,2), (3,3,3), (1), (2), (3), ... -> 3, 1, 2, 2, 3, 3, 1, 1, 1, 2, 2, 2, 3, 1, 2, 3, 3, 1, 1, 1, ...
Apply the same process to the third sequence and the original sequence reappears:
(3), (1), (2,2), (3,3), (1,1,1), (2,2,2), (3), (1), (2), (3,3), (1,1,1), (2), (3), (1,1), (2,2), (3,3,3), (1,1,1), (2,2,2), (3), (1), ... -> 1, 1, 2, 2, 3, 3, 1, 1, 1, 2, 3, 1, 1, 2, 2, 3, 3, 3, 1, 1, ...

F. M. Dekking: "What is the long range order in the Kolakoski sequence?" in: The Mathematics of Long-Range Aperiodic Order, ed. R. V. Moody, Kluwer, Dordrecht (1997), pp. 115-125.

Georg Fischer, Table of n, a(n) for n = 1..2000 (recovered b-file, Jan 16 2019)
F. M. Dekking, What Is the Long Range Order in the Kolakoski Sequence?, Report 95-100, Technische Universiteit Delft, 1995.
Wikipedia, Ouroboros, the serpent that bites its own tail.

Cf. A000002, A025142, A025143. The second and third sequences in this 3-Ouroboros are A288724 and A288725.

cp's OEIS Frontend

A025143 Unique sequence a of 1's and 2's such that a(1) = 2 and r(r(a)) = a != r(a), where for any sequence s, r(s) is the sequence of lengths of runs of same symbols in s; r(a) is sequence A025142.

Views

Author

Keywords

References

Crossrefs

A025144 Numbers k such that (#1's in s(1),...,s(k)) = (#1's in r(1),...,r(k)), where s = A025142 and r = A025143.

Views

Author

Keywords

Links

A025145 Numbers k such that (#1's in s(1),...,s(k)) = -1 + (#1's in r(1),...,r(k)), where s = A025142 and r = A025143.

Views

Author

Keywords

Links

A025146 (#1's in s(1),...,s(n)) - (#1's in r(1),...,r(n)), where s = A025142 and r = A025143.

Views

Author

Keywords

Links

A001037 Number of degree-n irreducible polynomials over GF(2); number of n-bead necklaces with beads of 2 colors when turning over is not allowed and with primitive period n; number of binary Lyndon words of length n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

PARI

Python

Formula

Extensions

A027375 Number of aperiodic binary strings of length n; also number of binary sequences with primitive period n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

A378282 Irregular triangular T: (row 1) = (1); (row n+1) = inverse runlength sequence of row n, starting with 2 if r = 3k for some k, and 1 otherwise. See Comments.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A288723 First sequence of a Kolakoski 3-Ouroboros, i.e., sequence of 1s, 2s and 3s that begins a chain of three distinct sequences where successive run-length encodings produce seq(1) -> seq(2) -> seq(3) -> seq(1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

A288724 Second sequence of a Kolakoski 3-Ouroboros, i.e., sequence of 1s, 2s and 3s that is second in a chain of three distinct sequences where successive run-length encodings produce seq(1) -> seq(2) -> seq(3) -> seq(1).

Views

Author

Keywords

Comments