A042942 -id:A042942 - cp's OEIS frontend

A054349 Successive generations of the variant of the Kolakoski sequence described in A042942.

2, 22, 2211, 221121, 221121221, 22112122122112, 2211212212211211221211, 221121221221121122121121221121121, 2211212212211211221211212211211212212211212212112

Offset: 0

N. J. A. Sloane, May 07 2000

For n >= 0, let f_1(n) be the number of 1's in a(n) (sequence begins: 0, 0, 2, 3, 4, 6, 11, 17, 24, ...) and f_2(n) be the number of 2's (sequence begins: 1, 2, 2, 3, 5, 8, 11, 16, 25, ...). Then there is a simple relation between f_1 and f_2, namely: f_1(n) = 1 - f_2(n) + f_2(n-1) + f_2(n-2) + ... + f_2(0). i.e. f_1(7) = 17 and 1 - f_2(7) + f_2(6) + ... + f_2(0) = 1 - 16 + 11 + 8 + 5 + 3 + 2 + 2 + 1 = 17. - Benoit Cloitre, Oct 11 2005

Bertran Steinsky, A Recursive Formula for the Kolakoski Sequence A000002, J. Integer Sequences, Vol. 9 (2006), Article 06.3.7.

Cf. A000002, A054348, A054350, A054351, A111123, A111124.

Word lengths give A042942.

More terms from David Wasserman, Mar 04 2002

A054348 Triangular array whose rows are successive generations of the variant of the Kolakoski sequence described in A042942.

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane, May 07 2000

			Triangle begins:
2;
2, 2;
2, 2, 1, 1;
2, 2, 1, 1, 2, 1;
2, 2, 1, 1, 2, 1, 2, 2, 1;
2, 2, 1, 1, 2, 1, 2, 2, 1, 2, 2, 1, 1, 2;
...

Cf. A000002, A054349, A054350, A054351.

Row lengths give A042942.

More terms from David Wasserman, Mar 04 2002

A000002 Kolakoski sequence: a(n) is length of n-th run; a(1) = 1; sequence consists just of 1's and 2's.

Original entry on oeis.org

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

Offset: 1

N. J. A. Sloane

Historical note: the sequence might be better called the Oldenburger-Kolakoski sequence, since it was discussed by Rufus Oldenburger in 1939; see links. - Clark Kimberling, Dec 06 2012.  However, to avoid confusion, this sequence will be known in the OEIS as the Kolakoski sequence. It is undesirable to have some entries refer to the Oldenburger-Kolakoski sequence and others to the Kolakoski sequence. - N. J. A. Sloane, Nov 22 2017
It is an unsolved problem to show that the density of 1's is equal to 1/2.
A weaker problem is to construct a combinatorial bijection between the set of positions of 1's and the set of positions of 2's. - Gus Wiseman, Mar 01 2016
The sequence is cubefree and all square subwords have lengths which are one of 2, 4, 6, 18 and 54 (see A294447) [Carpi, 1994].
This is a fractal sequence: replace each run with its length and recover the original sequence. - Kerry Mitchell, Dec 08 2005
Kupin and Rowland write: We use a method of Goulden and Jackson to bound freq_1(K), the limiting frequency of 1 in the Kolakoski word K. We prove that |freq_1(K) - 1/2| <= 17/762, assuming the limit exists and establish the semirigorous bound |freq_1(K) - 1/2| <= 1/46. - Jonathan Vos Post, Sep 16 2008
freq_1(K) is conjectured to be 1/2 + O(log(K)) (see PlanetMath link). - Jon Perry, Oct 29 2014
Conjecture: Taking the sequence in word lengths of 10, for example, batch 1-10, 11-20, etc., then there can only be 4, 5 or 6 1's in each batch. - Jon Perry, Sep 26 2012
From Jean-Christophe Hervé, Oct 04 2014: (Start)
The sequence does not contain words of the form ababa, because this would imply the impossible 111 (1 b, 1 a, 1 b) somewhere before. This demonstrates the conjecture made by Jon Perry: more than 6 1's or 6 2's in a word of 10 would necessitate something like aabaabaaba, which would imply the impossible 12121 before (word aabaababaa is also impossible because of ababa). The remark on the sextuplets below even shows that the number of 1's in any 9-tuplet is always 4 or 5.
There are only 6 triples that appear in the sequence (112, 121, 122, 211, 212 and 221); and by the preceding argument, only 18 sextuplets: the 6 double triples (112112, etc.); 112122, 112212, 121122, 121221, 211212, and 211221; and those obtained by reversing the order of the triples (122112, etc.). Regarding the density of 1's in the sequence, these 12 sextuplets all have a density 1/2 of 1's, and the 6 double triples all lead to a word with this exact density after transformation by the Kolakoski rules, for example: 112112 -> 12112122 (4 1's/8); this is because the second triple reverses the numbers of 1's and 2's generated by the first triple. Therefore, the sequence can be split into the double triples on one side, a part whose transformation (which is in the sequence) has a density of 1's of 1/2; and a part with the other sextuplets, which has directly the same density of 1's. (End)
If we map 1 to +1 and 2 to -1, then the mapped sequence would have a [conjectured] mean of 0, since the Kolakoski sequence is [conjectured] to have an equal density (1/2) of 1s and 2s. For the partial sums of this mapped sequence, see A088568. - Daniel Forgues, Jul 08 2015
Looking at the plot for A088568, it seems that although the asymptotic densities of 1s and 2s appear to be 1/2, there might be a bias in favor of the 2s. I.e., D(1) = 1/2 - O(log(n)/n), D(2) = 1/2 + O(log(n)/n). - Daniel Forgues, Jul 11 2015
From Michel Dekking, Jan 31 2018: (Start)
(a(n)) is the unique fixed point of the 2-block substitution beta
    11 -> 12
    12 -> 122
    21 -> 112
    22 -> 1122.
A 2-block substitution beta maps a word w(1)...w(2n) to the word
    beta(w(1)w(2))...beta(w(2n-1)w(2n)).
If the word has odd length, then the last letter is ignored.
It was noted by me in 1979 in the Bordeaux seminar on number theory that (a(n+1)) is fixed point of the 2-block substitution 11 -> 21, 12 -> 211, 21 -> 221,  22 -> 2211. (End)
Named after the American artist and recreational mathematician William George Kolakoski (1944-1997). - Amiram Eldar, Jun 17 2021

			Start with a(1) = 1. By definition of the sequence, this says that the first run has length 1, so it must be a single 1, and a(2) = 2. Thus, the second run (which starts with this 2) must have length 2, so the third term must be also be a(3) = 2, and the fourth term can't be a 2, so must be a(4) = 1. Since a(3) = 2, the third run must have length 2, so we deduce a(5) = 1, a(6) = 2, and so on. The correction I made was to change a(4) to a(5) and a(5) to a(6). - _Labos Elemer_, corrected by _Graeme McRae_

Jean-Paul Allouche and Jeffrey Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 337.
Éric Angelini, "Jeux de suites", in Dossier Pour La Science, pp. 32-35, Volume 59 (Jeux math'), April/June 2008, Paris.
F. M. Dekking, What Is the Long Range Order in the Kolakoski Sequence?, in The mathematics of long-range aperiodic order (Waterloo, ON, 1995), 115-125, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., 489, Kluwer Acad. Publ., Dordrecht, 1997. Math. Rev. 98g:11022.
Michael S. Keane, Ergodic theory and subshifts of finite type, Chap. 2 of T. Bedford et al., eds., Ergodic Theory, Symbolic Dynamics and Hyperbolic Spaces, Oxford, 1991, esp. p. 50.
J. C. Lagarias, Number Theory and Dynamical Systems, pp. 35-72 of S. A. Burr, ed., The Unreasonable Effectiveness of Number Theory, Proc. Sympos. Appl. Math., 46 (1992). Amer. Math. Soc.
Michel Rigo, Formal Languages, Automata and Numeration Systems, 2 vols., Wiley, 2014. Mentions this sequence - see "List of Sequences" in Vol. 2.
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).
Ilan Vardi, Computational Recreations in Mathematica. Addison-Wesley, Redwood City, CA, 1991, p. 233.

N. J. A. Sloane, Table of n, a(n) for n = 1..10502
Jean-Paul Allouche, Michael Baake, Julien Cassaigne and David Damanik, Palindrome complexity, arXiv:math/0106121 [math.CO], 2001; Theoretical Computer Science, Vol. 292 (2003), pp. 9-31.
Michael Baake and Bernd Sing, Kolakoski-(3,1) is a (deformed) model set, arXiv:math/0206098 [math.MG], 2002-2003.
Alex Bellos and Brady Haran, The Kolakoski Sequence, Numberphile video (2017).
Olivier Bordellès and Benoit Cloitre, Bounds for the Kolakoski Sequence, J. Integer Sequences, Vol. 14 (2011), Article 11.2.1.
Richard P. Brent, Fast algorithms for the Kolakoski sequence, Slides from a talk, 2016.
Éric Brier, Rémi Géraud-Stewart, David Naccache, Alessandro Pacco, and Emanuele Troiani, The Look-and-Say The Biggest Sequence Eventually Cycles, arXiv:2006.07246 [math.DS], 2020.
Arturo Carpi, On repeated factors in C^infinity-words, Information Processing Letters, Vol. 52 (1994), pp. 289-294.
Benoit Cloitre, The Kolakoski transform of words.
Benoit Cloitre, Plot of walk on the first 60000 terms (step of unit length moving right with angle Pi/2 if 2 and left with angle -Pi/2 if 1 starting at (0,0)).
F. M. Dekking, Regularity and irregularity of sequences generated by automata, Seminar on Number Theory, 1979-1980 (Talence, 1979-1980), Exp. No. 9, 10 pp., Univ. Bordeaux I, Talence, 1980.
F. M. Dekking, On the structure of self-generating sequences, Seminar on Number Theory, 1980-1981 (Talence, 1980-1981), Exp. No. 31, 6 pp., Univ. Bordeaux I, Talence, 1981. Math. Rev. 83e:10075. JSTOR
F. M. Dekking, What Is the Long Range Order in the Kolakoski Sequence?, Report 95-100, Technische Universiteit Delft, 1995.
F. M. Dekking, The Thue-Morse Sequence in Base 3/2, J. Int. Seq., Vol. 26 (2023), Article 23.2.3.
Jörg Endrullis, Dimitri Hendriks and Jan Willem Klop, Degrees of Streams, Integers, Vol. 11B (2011), A6.
David Eppstein, The Kolakoski tree and The Kolakoski sequence via bit tricks instead of recursion.
Jean-Marc Fédou and Gabriele Fici, Some remarks on differentiable sequences and recursivity, Journal of Integer Sequences, Vol. 13 (2010), Article 10.3.2.
Abdallah Hammam, Some new Formulas for the Kolakoski Sequence A000002, Turkish Journal of Analysis and Number Theory, Vol. 4, No. 3 (2016), pp. 54-59.
Mari Huova and Juhani Karhumäki, On Unavoidability of k-abelian Squares in Pure Morphic Words, Journal of Integer Sequences, Vol. 16 (2013), #13.2.9.
Clark Kimberling, Integer Sequences and Arrays, Illustration of the Kolakoski sequence.
William Kolakoski, Problem 5304, Amer. Math. Monthly, Vol. 72, No. 8 (1965), p. 674; Self Generating Runs, Solution to Problem 5304 by Necdet Üçoluk, Vol. 73, No. 6 (1966), pp. 681-682.
Leonid V. Kovalev, Kolakoski sequence II.
Elizabeth J. Kupin and Eric S. Rowland, Bounds on the frequency of 1 in the Kolakoski word, arXiv:0809.2776 [math.CO], Sep 16, 2008.
Rabie A. Mahmoud, Hardware Implementation of Binary Kolakoski Sequence, Research Gate, 2015.
Kerry Mitchell, Spirolateral-Type Images from Integer Sequences, 2013.
Johan Nilsson, A Space Efficient Algorithm for the Calculation of the Digit Distribution in the Kolakoski Sequence, J. Int. Seq., Vol. 15 (2012), Article 12.6.7; arXiv preprint, arXiv:1110.4228 [math.CO], Oct 19, 2011.
J. Nilsson, Letter Frequencies in the Kolakoski Sequence, Acta Physica Polonica A, Vol. 126 (2014), pp. 549-552.
Rufus Oldenburger, Exponent trajectories in symbolic dynamics, Trans. Amer. Math. Soc., Vol. 46 (1939), pp. 453-466.
Matthew Parker, The first 50K terms (7-Zip compressed file).
Gheorghe Păun and Arto Salomaa, Self-reading sequences, Amer. Math. Monthly, Vol. 103, No. 2 (1996), pp. 166-168.
Michael Rao, Trucs et bidules sur la séquence de Kolakoski, 2012, in French.
A. Scolnicov, Kolakoski sequence, PlanetMath.org.
Bobby Shen, A uniformness conjecture of the Kolakoski sequence, graph connectivity, and correlations, arXiv:1703.00180 [math.CO], 2017.
Bernd Sing, More Kolakoski Sequences, INTEGERS, Vol. 11B (2011), A14.
N. J. A. Sloane, Handwritten notes on Self-Generating Sequences, 1970. (note that A1148 has now become A005282)
N. J. A. Sloane, Coordination Sequences, Planing Numbers, and Other Recent Sequences (II), Experimental Mathematics Seminar, Rutgers University, Jan 31 2019, Part I, Part 2, Slides. (Mentions this sequence)
Bertran Steinsky, A Recursive Formula for the Kolakoski Sequence A000002, J. Integer Sequences, Vol. 9 (2006), Article 06.3.7.
Eric Weisstein's World of Mathematics, Kolakoski Sequence
Wikipedia, Kolakoski sequence.
Gus Wiseman, Kolakoski fractal animation for n=40000.
Ed Wynn, Program to generate A000002 in Shakespeare Programming Language.
Index entries for "core" sequences

Cf. A001083, A006928, A042942, A069864, A010060, A078929, A171899, A054353 (partial sums), A074286, A216345, A294447.
Cf. A054354, bisections: A100428, A100429.
Cf. A013947, A156077, A234322 (positions, running total and percentage of 1's).
Cf. A118270.
Cf. A049705, A088569 (are either subsequences of A000002? - Jon Perry, Oct 30 2014)
Kolakoski-type sequences using other seeds than (1,2):
A078880 (2,1), A064353 (1,3), A071820 (2,3), A074804 (3,2), A071907 (1,4), A071928 (2,4), A071942 (3,4), A074803 (4,2), A079729 (1,2,3), A079730 (1,2,3,4).
Other self-describing: A001462 (Golomb sequence, see also references therein), A005041, A100144.
Cf. A088568 (partial sums of [3 - 2 * a(n)]).

a = 1:2: drop 2 (concat . zipWith replicate a . cycle $ [1,2]) -- John Tromp, Apr 09 2011

M := 100; s := [ 1,2,2 ]; for n from 3 to M do for i from 1 to s[ n ] do s := [ op(s),1+((n-1)mod 2) ]; od: od: s; A000002 := n->s[n];
# alternative implementation based on the Cloitre formula:
A000002 := proc(n)
    local ksu,k ;
    option remember;
    if n = 1 then
        1;
    elif n <=3 then
        2;
    else
        for k from 1 do
            ksu := add(procname(i),i=1..k) ;
            if n = ksu then
                return (3+(-1)^k)/2 ;
            elif n = ksu+ 1 then
                return (3-(-1)^k)/2 ;
            end if;
        end do:
    end if;
end proc: # R. J. Mathar, Nov 15 2014

a[steps_] := Module[{a = {1, 2, 2}}, Do[a = Append[a, 1 + Mod[(n - 1), 2]], {n, 3, steps}, {i, a[[n]]}]; a]
a[ n_] := If[ n < 3, Max[ 0, n], Module[ {an = {1, 2, 2}, m = 3}, While[ Length[ an] < n, an = Join[ an, Table[ Mod[m, 2, 1], { an[[ m]]} ]]; m++]; an[[n]]]] (* Michael Somos, Jul 11 2011 *)
n=8; Prepend[ Nest[ Flatten[ Partition[#, 2] /. {{2, 2} -> {2, 2, 1, 1}, {2, 1} -> {2, 2, 1}, {1, 2} -> {2, 1, 1}, {1, 1} -> {2, 1}}] &, {2, 2}, n], 1] (* Birkas Gyorgy, Jul 10 2012 *)
KolakoskiSeq[n_Integer] := Block[{a = {1, 2, 2}}, Fold[Join[#1, ConstantArray[Mod[#2, 2, 1], #1[[#2]]]] &, a, Range[3, n]]]; KolakoskiSeq[999] (* Mikk Heidemaa, Nov 01 2024 *) (* Corrected by Giorgos Kalogeropoulos, May 09 2025 *)

my(a=[1,2,2]); for(n=3,80, for(i=1,a[n],a=concat(a,2-n%2))); a

{a(n) = local(an=[1, 2, 2], m=3); if( n<1, 0, while( #an < n, an = concat( an, vector(an[m], i, 2-m%2)); m++); an[n])};

# For explanation see link.
def Kolakoski():
    x = y = -1
    while True:
        yield [2,1][x&1]
        f = y &~ (y+1)
        x ^= f
        y = (y+1) | (f & (x>>1))
K = Kolakoski()
print([next(K) for  in range(100)]) # _David Eppstein, Oct 15 2016

These two formulas define completely the sequence: a(1)=1, a(2)=2, a(a(1) + a(2) + ... + a(k)) = (3 + (-1)^k)/2 and a(a(1) + a(2) + ... + a(k) + 1) = (3 - (-1)^k)/2. - Benoit Cloitre, Oct 06 2003
a(n+2)*a(n+1)*a(n)/2 = a(n+2) + a(n+1) + a(n) - 3 (this formula doesn't define the sequence, it is just a consequence of the definition). - Benoit Cloitre, Nov 17 2003
a(n+1) = 3 - a(n) + (a(n) - a(n-1))*(a(b(n)) - 1), where b(n) is the sequence A156253. - Jean-Marc Fedou and Gabriele Fici, Mar 18 2010
a(n) = (3 + (-1)^A156253(n))/2. - Benoit Cloitre, Sep 17 2013
Conjectures from Boštjan Gec, Oct 07 2024: (Start)
a(n)*(a(n-1) + a(n-2) - 3) + a(n-1)*a(n-2) + 7 = 3*a(n-1) + 3*a(n-2).
a(n)*(a(n-1) + a(n-2) - 3) = a(n-3)*(a(n-1) + a(n-2) - 3). (End)
Comment from Kevin Ryde, Oct 07 2024: The above formulas are true: The parts identify when terms are same or different and they hold for any sequence of 1's and 2's with run lengths 1 or 2.

Minor edits to example and PARI code made by M. F. Hasler, May 07 2014

A066983 a(n+2) = a(n+1) + a(n) + (-1)^n, with a(1) = a(2) = 1.

Original entry on oeis.org

1, 1, 1, 3, 3, 7, 9, 17, 25, 43, 67, 111, 177, 289, 465, 755, 1219, 1975, 3193, 5169, 8361, 13531, 21891, 35423, 57313, 92737, 150049, 242787, 392835, 635623, 1028457, 1664081, 2692537, 4356619, 7049155, 11405775, 18454929, 29860705, 48315633, 78176339

Offset: 1

Benoit Cloitre, Jan 27 2002

Length of strings given by a successive substitution of a "modified" Kolakoski-(3, 1) sequence. Starting with 1, using the rule "string begins with 1 if previous string ends with 3, string begins with 3 if previous string ends with 1" then applying the classical Kolakoski-(3,1) rule. This gives: 1 -> 3 -> 111 -> 313 -> 1113111 -> 313111313 -> 11131113131113111 and the length of string are 1, 1, 3, 3, 7, 9, 17, ... At step n, length = a(n+1). This substitution leads to two sequences: 1, 1, 1, 3, 1, 1, 1, 3, 1, 3, 1, 1, 1, ... and 3, 1, 3, 1, 1, 1, 3, 1, 3, 1, 1, 1, 3, ... - Benoit Cloitre, Jun 01 2004
Lengths of comparators in subsequent layers of correction network F_n. - Grzegorz Stachowiak (gst(AT)ii.uni.wroc.pl), Nov 28 2004
Convolution of F(n+1) and A105812(n). Action of inverse of sequence array for F(n-1)*(-1)^n on F(n+1). - Paul Barry, Oct 29 2006

Omur Deveci, The Pell-Padovan sequences and the Jacobsthal-Padovan sequences in finite groups, Utilitas Mathematica, 98 (2015), 257-270.

Harry J. Smith, Table of n, a(n) for n = 1..250
K. Atanassov, D. Dimitrov and A. G. Shannon, A remark on psi-function and Pell-Padovan's sequence, Notes Number Theory Discrete Math., 15 (2009), no. 2, 1-44.
Michael Baake and Bernd Sing, Kolakoski-(3,1) is a (deformed) model set, arXiv:math/0206098 [math.MG], 2002-2003.
Taras Goy, S. V. Sharyn, A note on Pell-Padovan numbers and their connection with Fibonacci numbers, Carpathian Math. Publ. (2020) Vol. 12, No. 2, 280-288.
Zehra İşbilir and Nurten Gürses, Pell-Padovan generalized quaternions, Notes on Num. Theory and Disc. Math. (2021) Vol. 27, No. 1, 171—187.
G. Stachowiak, Fibonacci Correction Networks, SWAT 2000, LNCS 1851, 535-548.
G. Stachowiak, Lower Bounds on Correction Networks, ISAAC 2003, LNCS 2906, 221-229.
Dursun Tasci, Gaussian Padovan and Gaussian Pell-Padovan sequences, Commun. Fac. Sci. Univ. Ank. Ser. A1 Math. Stat., 67 (2018), no. 2, 82-88. Sequence R_n.
Index entries for linear recurrences with constant coefficients, signature (0,2,1).

Cf. A000045, A001083, A042942, A064353, A066629.

a:=[1,1];; for n in [3..40] do a[n]:=a[n-1]+a[n-2]+(-1)^n; od; a; # Muniru A Asiru, Aug 09 2018

[n le 2 select 1 else Self(n-1)+Self(n-2)+(-1)^n: n in [1..50]]; // Vincenzo Librandi, Aug 13 2018

seq(coeff(series(x*(1+x-x^2)/((1+x)*(1-x-x^2)), x,n+1),x,n),n=1..40); # Muniru A Asiru, Aug 09 2018

Table[ Floor[ GoldenRatio^(k-1) ] - Floor[ GoldenRatio^(k-1) / Sqrt[5] ], {k, 1, 100} ]  (* Federico Provvedi, Mar 26 2013 *)
LinearRecurrence[{0, 2, 1}, {1, 1, 1}, 40] (* Vincenzo Librandi, Aug 13 2018 *)

{ for (n=1, 250, if (n>2, a=a1 + a2 + (-1)^n; a2=a1; a1=a, a=a1=1; a=a2=1); write("b066983.txt", n, " ", a) ) } \\ Harry J. Smith, Apr 15 2010

vector(40, n, 2*fibonacci(n-2) + (-1)^n) \\ G. C. Greubel, Dec 26 2019

from sympy import fibonacci
def A066983(n): return (fibonacci(n-2)<<1)+(-1 if n&1 else 1) # Chai Wah Wu, May 05 2025

[2*fibonacci(n-2) + (-1)^n for n in (1..40)] # G. C. Greubel, Dec 26 2019

For n > 4, a(n-2) = floor(2 * phi^n/sqrt(5)) + (1 + (-1)^n)/2.
a(n) = 2 * Fibonacci(n-2) + (-1)^n. - Vladeta Jovovic, Mar 19 2003
G.f.: x*(1+x-x^2)/((1+x)*(1-x-x^2)). - Paul Barry, Oct 29 2006
a(n) = A066629(n-2) - A066629(n-3), n > 2. - R. J. Mathar, Jan 14 2009
a(n) = floor(phi^(n-1)) - floor(phi^(n-1)/sqrt(5)). - Federico Provvedi, Mar 26 2013
a(1) = a(2) = a(3) = 1; for n > 3, a(n) = 2*a(n-2) + a(n-3). - Taras Goy, Aug 03 2018
a(n) = (-1)^n + (-1 - 3/sqrt(5))*((1/2)*(1 - sqrt(5)))^n + (-1 + 3/sqrt(5))*((1/2)*(1 + sqrt(5)))^n. - Stefano Spezia, Jul 22 2019

Deleted certain dangerous or potentially dangerous links. - N. J. A. Sloane, Jan 30 2021

A054351 Successive generations of the Kolakoski sequence A000002.

Original entry on oeis.org

1, 12, 1221, 1221121, 12211212212, 122112122122112112, 1221121221221121122121121221, 1221121221221121122121121221121121221221121, 12211212212211211221211212211211212212211212212112112212211212212

Offset: 0

N. J. A. Sloane, May 07 2000

Cf. A054348, A054349, A054350, A054352, A042942, A000002.

Word lengths give A054352.

from itertools import accumulate, groupby, repeat
def K(n, _):
  c, s = "12", ""
  for i, k in enumerate(str(n)): s += c[i%2]*int(k)
  return int(s + c[(i+1)%2])
def aupton(nn): return list(accumulate(repeat(1, nn+1), K))
print(aupton(8)) # Michael S. Branicky, Jan 12 2021

More terms from Antonio G. Astudillo (afg_astudillo(AT)lycos.com), Apr 05 2003

A054352 Lengths of successive generations of the Kolakoski sequence A000002.

Original entry on oeis.org

1, 2, 4, 7, 11, 18, 28, 43, 65, 99, 150, 226, 340, 511, 768, 1153, 1728, 2590, 3885, 5826, 8742, 13116, 19674, 29514, 44280, 66431, 99667, 149531, 224306, 336450, 504648, 756961, 1135450, 1703197, 2554846, 3832292, 5748474, 8622646, 12933971, 19400955, 29101203

Offset: 0

N. J. A. Sloane, May 07 2000

Starting with a(0) = 1, the first term of A000002, the n-th generation is the run of figures directly generated from the preceding generation completed with a single last figure which begins the next run. Thus a(0) = 1 -> 1-2 -> 1-22-1 -> 1-2211-2-1 etc. - Jean-Christophe Hervé, Oct 26 2014

It seems that the limit (c =) lim_{n -> oo} a(n)/(3/2)^n exists, with c = 2.63176..., so a(n) ~ (3/2)*a(n-1) ~ c * (3/2)^n, for large n. - A.H.M. Smeets, Apr 12 2024

Michael S. Branicky, Table of n, a(n) for n = 0..61

Cf. A054348, A054349, A054350, A054351, A054353, A042942, A000002.

Partial sums of A329758.

A2 = {1, 2, 2}; Do[If[Mod[n, 10^5] == 0, Print["n = ", n]]; m = 1 + Mod[n - 1, 2]; an = A2[[n]]; A2 = Join[A2, Table[m, {an}]], {n, 3, 10^6}]; A054353 = Accumulate[A2]; Clear[a]; a[0] = 1; a[n_] := a[n] = A054353[[a[n - 1]]] + 1; Table[a[n], {n, 0, 33}] (* Jean-François Alcover, Oct 30 2014, after Jean-Christophe Hervé *)

def aupton(nn):
  alst, A054353, idx = [1], 0, 1
  K = Kolakoski()  # using Kolakoski() in A000002
  for n in range(2, nn+1):
    target = alst[-1]
    while idx <= target:
      A054353 += next(K)
      idx += 1
    alst.append(A054353 + 1)  # a(n) = A054353(a(n-1))+1
  return alst
print(aupton(36))  # Michael S. Branicky, Jan 12 2021

a(0) = 1, and for n > 0, a(n) = A054353(a(n-1))+1. - Jean-Christophe Hervé, Oct 26 2014

a(7)-a(32) from John W. Layman, Aug 20 2002
a(33) from Jean-François Alcover, Oct 30 2014
a(34) and beyond from Michael S. Branicky, Jan 12 2021

A045723 Number of configurations, excluding reflections and black-white interchanges, of n black and n white beads on a string.

Original entry on oeis.org

1, 1, 3, 7, 23, 71, 252, 890, 3299, 12283, 46508, 176870, 677294, 2602198, 10034104, 38787572, 150289699, 583434323, 2268861516, 8836447022, 34461940538, 134564992898, 526025965864, 2058359779052, 8061905791118, 31602659998046

Offset: 0

Wouter Meeussen

nonn

This sequence (with offset 0) equals the probable number of inequivalent classes of permutations acting on an n-party state under the trace norm in the context of permutation criteria for separability. - Lieven Clarisse, Apr 28 2006
Number of connected components of an undirected graph where the nodes are the n-subsets of {1,...,2n} and an edge (A,B) appears if B = {1,...,2n} \ A or B = {2n + 1 - i: i in A}. See Mathematics Magazine link. - Rob Pratt, Aug 10 2015
Number of distinct staircase walks connecting opposite corners of a square grid of side n > 1. - Christian Barrientos, Nov 25 2018

Vincenzo Librandi, Table of n, a(n) for n = 0..1000
Eddie Cheng and Jerrold W. Grossman, Problem 1959, Mathematics Magazine 87 (Dec. 2014), p. 396.
L. Clarisse and P. Wocjan, On independent permutation separability criteria, Quant. Inf. Comp. 6 277-288, 2006, arXiv:quant-ph/0504160, 2005.

Cf. A042942.

Cf. A027306, A042971.

Table[ 1/4 (2^n + Binomial[ 2 n, n ] + 2 Binomial[ -1 + n, 1/2 (-2 + n) ]*Mod[ 1 + n, 2 ]), {n, 0, 24} ]

a(n) = (1/4)*(2^n + binomial(2*n, n) + if ((n+1)%2, 2*binomial(n-1, (1/2)*(n-2)))); \\ Michel Marcus, Nov 25 2018

a(n) = (1/4)*(2^n + C(2*n, n) + 2*C(n-1, (1/2)*(n-2))*((n+1) mod 2)).

a(n) = A042971(n) + A027306(n). - Michel Marcus, Nov 26 2018

A001083 Length of one version of Kolakoski sequence {A000002(i)} at n-th growth stage.

Original entry on oeis.org

1, 2, 2, 3, 5, 7, 10, 15, 23, 34, 50, 75, 113, 170, 255, 382, 574, 863, 1293, 1937, 2903, 4353, 6526, 9789, 14688, 22029, 33051, 49577, 74379, 111580, 167388, 251090, 376631, 564932, 847376, 1271059, 1906628, 2859984

Offset: 1

N. J. A. Sloane, Simon Plouffe

nonn

			/* generate sequence of sequences by recursion using next1() ( origin 1 ) */
v=[2]; for(n=1,8,p1(v); print1(" -> "); v=next1(v))
2 -> 11 -> 12 -> 122 -> 12211 -> 1221121 -> 1221121221 -> 122112122122112 ->
v=[2]; for(n=1,8,print1(length(v)); print1(","); v=next1(v)) gives: 1,2,2,3,5,7,10,15,

Konstantinos Lambropoulos and Constantinos Simserides, Spectral, localization and charge transport properties of periodic, aperiodic and random binary sequences, arXiv:1808.04764 [cond-mat.soft], 2018.
Eric Weisstein's World of Mathematics, Kolakoski Sequence

Cf. A000002, A042942, A054353.

/* generate sequence starting at 1 given run length sequence */
next1(v)=local(w); w=[]; for(n=1,length(v), for(i=1,v[n],w=concat(w,2-n%2))); w
/* print a number or sequence recursively with no commas */
p1(v)=if(type(v)!="t_VEC",print1(v), for(n=1,length(v),p1(v[n])))

Conjecture: a(n) is asymptotic to c*(3/2)^n where c=0.5819.... - Benoit Cloitre, Jun 01 2004
For n >= 1, a(n+3) = S^n(2) where S(n) = A054353(n) and S^k(2) = S(S^(k-1)(2)). - Benoit Cloitre, Feb 24 2009 [adjusted to match sequence offset by Jon Maiga, Jul 27 2022]
Equivalently, a(n) = A054353(a(n-1)) for n>3. - Jon Maiga, Jul 10 2022

Corrected by and better description from Michael Somos, May 05 2000

A111123 Number of 2's in n-th "Kolakoski" string defined in A054349.

Original entry on oeis.org

1, 2, 2, 3, 5, 8, 11, 16, 25, 38, 57, 85, 127, 192, 289, 430, 644, 966, 1450, 2173, 3263, 4899, 7341, 11022, 16526, 24802, 37201, 55808, 83702, 125541, 188301, 282444, 423683, 635569, 953356, 1429969, 2144990, 3217454, 4826176, 7239129, 10858479, 16287972, 24431890

Offset: 0

Benoit Cloitre, Oct 16 2005

nonn

Also the number of terms in n-th string (starting from n=3) when representing A000002 as a tree. Each branch of this tree is a string. Starting from n=3, each 1 in n-th string generates either 1 or 2 in (n+1)-th string and each 2 in n-th string generates either 11 or 22 in (n+1)-th string based on the previously generated term of either 2 or 1. Hence, the number of terms in (n+1)-th string is the sum of all terms in n-th string. - Rakesh Khanna A, May 24 2020

Rakesh Khanna A, Table of n, a(n) for n = 0..59

Cf. A001083, A042942, A054349, A111124 (number of 1's).

l = { (*terms in A042942*) }; For[i = 2, i <= Length[l], i++, Print[l[[i]] - l[[i - 1]]]]

a(0) + a(1) + ... + a(n) = A042942(n+2) - 1.

a(n) = A001083(n+4) - A001083(n+3). - Benoit Cloitre, Nov 07 2010

More terms from and offset changed to 0 by Jinyuan Wang, Apr 03 2020

A111124 Number of 1's in n-th "Kolakoski" string defined in A054349.

Original entry on oeis.org

0, 0, 2, 3, 4, 6, 11, 17, 24, 36, 55, 84, 127, 189, 284, 432, 648, 970, 1452, 2179, 3262, 4889, 7346, 11006, 16524, 24774, 37177, 55771, 83685, 125548, 188329, 282487, 423692, 635489, 953271, 1430014, 2144962, 3217488, 4826220, 7239443, 10859222, 16288208, 24432262

Offset: 0

Benoit Cloitre, Oct 16 2005

nonn

Cf. A001083, A042942, A054349, A111123 (number of 2's).

More terms from and offset changed to 0 by Jinyuan Wang, Apr 03 2020

cp's OEIS Frontend

A054349 Successive generations of the variant of the Kolakoski sequence described in A042942.

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

A054348 Triangular array whose rows are successive generations of the variant of the Kolakoski sequence described in A042942.

Views

Author

Keywords

Examples

Crossrefs

Extensions

A000002 Kolakoski sequence: a(n) is length of n-th run; a(1) = 1; sequence consists just of 1's and 2's.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

PARI

Python

Formula

Extensions

A066983 a(n+2) = a(n+1) + a(n) + (-1)^n, with a(1) = a(2) = 1.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

PARI

Python

Sage

Formula

Extensions

A054351 Successive generations of the Kolakoski sequence A000002.

Views

Author

Keywords

Crossrefs

Programs

Python

Extensions

A054352 Lengths of successive generations of the Kolakoski sequence A000002.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

Python

Formula

Extensions

A045723 Number of configurations, excluding reflections and black-white interchanges, of n black and n white beads on a string.

Views

Author

Keywords

Comments

Links

Crossrefs