cp's OEIS Frontend

A006345 Linus sequence: a(n) "breaks the pattern" by avoiding the longest doubled suffix.

%I A006345 M0074 #125 Feb 16 2025 08:32:30
%S A006345 1,2,1,1,2,2,1,2,1,1,2,1,2,2,1,1,2,1,1,1,2,2,1,2,1,1,2,2,1,1,1,2,1,1,
%T A006345 2,2,1,2,1,1,2,1,2,2,1,1,2,1,1,1,2,2,1,2,1,1,2,2,1,2,2,2,1,1,2,1,2,2,
%U A006345 1,1,2,2,2,1,2,2,1,1,2,1,2,2,1,2,1,1,2,2,1,2,2,2,1,1,2,1,2,2,1,1,2,2,2,1,2
%N A006345 Linus sequence: a(n) "breaks the pattern" by avoiding the longest doubled suffix.
%C A006345 To find a(n), consider either a 1 or a 2. For each, find the longest repeated suffix, that is, for each of a(n)=1,2, find the longest sequence s with the property that the sequence a(1),...,a(n) ends with ss. Use the digit that results in the shorter such suffix. a(1) = 1. The empty sequence of length 0 is the shortest possible suffix and is trivially doubled. Note that this doesn't result in exactly Linus's choices. - K. Ramsey, kramsey(AT)aol.com
%C A006345 On average, it seems that (# of 1s up to n) - (# of 2s up to n) -> infinity as n -> infinity (as O(log n)?), while the asymptotic density of either 1s or 2s appears to be 1/2. - _Daniel Forgues_, Mar 01 2017
%D A006345 N. S. Hellerstein, Letter to _N. J. A. Sloane_ (1978).
%D A006345 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A006345 T. D. Noe, Robert Israel, and Hugo van der Sanden, <a href="/A006345/b006345.txt">Table of n, a(n) for n = 1..50000</a> (1..1000 from T. D. Noe, 1001..20000 from Robert Israel)
%H A006345 P. Balister, S. Kalikow, and A. Sarkar, <a href="http://www2.ims.nus.edu.sg/preprints/2007-19.pdf">The Linus sequence</a>, Preprint May 2007; Combinatorics, Probability and Computing, Volume 19, Issue 1 January 2010 , pp. 21-46..
%H A006345 N. Hellerstein, <a href="/A006345/a006345.pdf">Letter to N. J. A. Sloane, 1978</a>
%H A006345 N. Hellerstein, M. Gardner, and S. Kim, <a href="/A006345/a006345_1.pdf">Correspondence related to the Linus and Sally sequences, 1977</a>
%H A006345 N. J. A. Sloane, <a href="/A006345/a006345.html">Illustration of initial terms</a>
%H A006345 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/LinusSequence.html">Linus Sequence.</a>
%e A006345 After 1,2,1,1,2,2,1,2, if we put a 1, the suffix {2,1} repeats, but if we put a 2 the longer suffix {1,2,2} repeats, so the next term is 1.
%p A006345 LDS:= proc(L)
%p A006345   local Cands, r,m;
%p A006345   Cands:= {$1..floor(nops(L)/2)};
%p A006345   r:= 0;
%p A006345 for m from 1 while nops(Cands) > 0 do
%p A006345      Cands:= select(c -> L[-m] = L[-c-m], Cands);
%p A006345      if min(Cands) = m then
%p A006345         r:= m;
%p A006345         Cands:= subs(m=NULL,Cands);
%p A006345      fi
%p A006345    od;
%p A006345    r
%p A006345 end proc:
%p A006345 A:= 1:
%p A006345 for n from 2 to 10^3 do
%p A006345   if LDS([A,1]) < LDS([A,2]) then A:= A,1 else A:= A,2 fi;
%p A006345 od:
%p A006345 seq(A[i],i=1..10^3); # _Robert Israel_, Jun 22 2015
%t A006345 LDS[L_] := Module[{Cands, r, m}, Cands = Range[Floor[Length[L]/2]]; r = 0; For[m = 1, Length[Cands] > 0, m++, Cands = Select[Cands, L[[-m]] == L[[-# - m]]&]; If[Min[Cands] == m, r = m; Cands = ReplaceAll[Cands, m -> Nothing]]]; r]; A = {1}; For[n = 2, n <= 10^3, n++, If[LDS[Append[A, 1]] < LDS[Append[A, 2]], A = Append[A, 1], A = Append[A, 2]]];
%t A006345 Table[A[[i]], {i, 1, 105}] (* _Jean-François Alcover_, Jul 17 2024, after _Robert Israel_ *)
%o A006345 (Perl) -le 'print$_.=3**/(.*)(.)\1$/-$2for($_)x99' # (Ton Hospel/Phil Carmody) [An example of Perl golfing: use as few (key)strokes as possible]
%o A006345 (PARI) {a(n)=local(A,t); if(n<2, n>0, A=[1]; for(i=2, n, forstep(j=i\2-1, 0, -1, for(k=1, j, if(A[i-j-k-1]!=A[i-k], next(2))); t=j; break); A=concat(A,[3-A[i-t-1]])); A[n])} /* _Michael Somos_, May 04 2006 */
%o A006345 (Perl)
%o A006345 =Comment on calculating this sequence and A006346 with Perl, from _Hugo van der Sanden_, Jun 23 2015:
%o A006345 The approach I used was to take advantage of Perl's regular expression capabilities, coupled with the realization that Perl can optimize patterns anchored to the start far better than those anchored to the end - reversing the string to allow that gave a speedup of several orders of magnitude:
%o A006345 =cut
%o A006345 my $string = "";
%o A006345 digit('1', 0);
%o A006345 for (2 .. $limit) {
%o A006345     my($repeat, $digit) = ($string =~ m{ ^ (.*) ([12]) \1 }x) or die;
%o A006345     digit($digit eq '1' ? '2' : '1', length($repeat) + 1);
%o A006345 }
%o A006345 sub digit {
%o A006345     my($digit, $repeat) = @_;
%o A006345     $string = $digit . $string;
%o A006345     # n A6345(n) A6346(n)
%o A006345     printf "%s %s %s\n", length($string), $digit, $repeat;
%o A006345 }
%o A006345 # This takes about 45s to calculate 50000 terms of both sequences.
%Y A006345 Cf. A006346, A094840, A157238 (A006345(n) - 1).
%K A006345 nonn,easy,nice
%O A006345 1,2
%A A006345 _N. J. A. Sloane_
%E A006345 More terms from _Naohiro Nomoto_, May 21 2001
%E A006345 Additional comments from _Mitch Harris_, Dec 31 2003