A Transform Of Seqs Involv Permutations

David Wasserman dwasserm at earthlink.com
Wed Dec 15 04:30:40 CET 2004

I'd be very surprised if this transform has been studied before.
I started by applying it to the Kolakoski sequence A000002, and I got
This sequence is not in the OEIS, and it can be obtained from A000002 by replacing each 2,2 with 3,1.

 - David

%I A000002 M0190 N0070
%S A000002 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,
%T A000002 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,
%U A000002 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
%N A000002 Kolakoski sequence: a(n) is length of n-th run; a(1) = 1; sequence consists just of 1's and 2's.
%C A000002 It is a famous unsolved problem to show that the density of 1's is equal to 1/2.
%C A000002 The sequence is cube-free, and all square subwords have lengths which are one of 2, 4, 6, 18 and 54.
%D A000002 J.-P. Allouche and J. Shallit, Automatic Sequences, Cambridge Univ. Press, 2003, p. 337.
%D A000002 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.
%D A000002 F. M. Dekking, What Is the Long Range Order in the Kolakoski Sequence?, in The mathematics of long-range ape\
  riodic order (Waterloo, ON, 1995), 115-125, NATO Adv. Sci. Inst. Ser. C Math. Phys. Sci., 489, Kluwer Acad. Publ., Do\
  rdrecht, 1997. Math. Rev. 98g:11022.
%D A000002 M. 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.
%D A000002 W. Kolakoski, Problem 5304, Amer. Math. Monthly, 72 (1965), 674; 73 (1966), 681-682.
%D A000002 J. C. Lagarias, Number Theory and Dynamical Systems, pp. 35-72 of S. A. Burr, ed., The Unreasonable Effectiv\
  eness of Number Theory, Proc. Sympos. Appl. Math., 46 (1992). Amer. Math. Soc.
%D A000002 G. Paun and A. Salomaa, Self-reading sequences, Amer. Math. Monthly 103 (1996), no. 2, 166-168.
%D A000002 I. Vardi, Computational Recreations in Mathematica. Addison-Wesley, Redwood City, CA, 1991, p. 233.
%H A000002 J.-P. Allouche, M. Baake, J. Cassaigns and D. Damanik, <a href="http://www.lri.fr/~allouche/">Palindrome com\
%H A000002 Michael Baake and Bernd Sing, <a href="http://arXiv.org/abs/math.MG/0206098">Kolakoski-(3,1) is a (deformed)\
   model set</a>
%H A000002 C. Kimberling, Integer Sequences and Arrays, <a href="http://www2.evansville.edu/ck6/integer/index.html">Ill\
  ustration of the Kolakoski sequence</a>
%H A000002 A. Scolnicov, PlanetMath.org, <a href="http://planetmath.org/encyclopedia/KolakoskiSequence.html">Kolakoski \
%H A000002 E. W. Weisstein, <a href="http://mathworld.wolfram.com/KolakoskiSequence.html">Link to a section of The Worl\
  d of Mathematics.</a>
%H A000002 <a href="http://www.research.att.com/~njas/sequences/Sindx_Cor.html#core">Index entries for "core" sequences\
%F A000002 Omit the initial 1 (so this remark is really about A078880). Then the sequence can be generated by starting \
  with 22 and applying the block-substitution rules 22 -> 2211, 21 -> 221, 12 -> 211, 11 -> 21 (Lagarias)
%F A000002 These two formulae 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 (abcloitre(AT)wanadoo.fr), Oct 06 2003
%F A000002 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, just a consequence of\
   definition) - Benoit Cloitre (abcloitre(AT)wanadoo.fr), Nov 17 2003
%e A000002 Start with a(1) = 1, a(2) = 2. The rule says that the first run (which is a single 1) has length 1, which it\
   does, and the second run (which starts with the 2) has length 2, so the third term must be a 2 also, and the fourth \
  term can't be a 2, so must be a 1. So we have a(3) = 2, a(4) = 1. Since a(3) =2, the third run has length 2, so we de\
  duce a(4) = 1, a(5) =2. And so on. (From Labos E.)
%p A000002 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];
%t A000002 a[steps_] := Module[{a = {1, 2, 2}}, Do[a = Append[a, 1 + Mod[(n - 1), 2]], {n, 3, lst}, {i, a[[n]]}]; a]
%o A000002 (PARI) a=[ 1,2,2 ]; for(n=3,80, for(i=1,a[ n ],a=concat(a,1+((n-1)%2)))); a
%o A000002 (PARI) a(n)=local(an,m); if(n<1,0,an=[1,2,2]; m=3; while(length(an)<n,an=concat(an,vector(an[m],i,(m-1)%2+1)\
  ); m++); an[n])
%Y A000002 Cf. A064353, A001462, A001083, A006928, A042942, A069864, A010060, A078880.
%Y A000002 Sequence in context: A074293 A013949 A078880 this_sequence A074295 A088427 A020945
%Y A000002 Adjacent sequences: A000001 this_sequence A000003 A000004 A000005
%K A000002 nonn,core,easy,nice
%O A000002 1,2
%A A000002 njas 

More information about the SeqFan mailing list