login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A006345 Linus sequence: a(n) "breaks the pattern" by avoiding the longest doubled suffix.
(Formerly M0074)
6
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, 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, 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 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

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

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

REFERENCES

N. S. Hellerstein, Letter to N. J. A. Sloane (1978).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

T. D. Noe, Robert Israel and Hugo van der Sanden, Table of n, a(n) for n = 1..50000 (1..1000 from T. D. Noe, 1001..20000 from Robert Israel)

P. Balister, S. Kalikow, A. Sarkar, The Linus sequence, Preprint May 2007; Combinatorics, Probability and Computing, Volume 19, Issue 1 January 2010 , pp. 21-46..

N. Hellerstein, Letter to N. J. A. Sloane, 1978

N. Hellerstein, M. Gardner, & S. Kim, Correspondence related to the Linus and Sally sequences, 1977

N. J. A. Sloane, Illustration of initial terms

Eric Weisstein's World of Mathematics, Linus Sequence.

EXAMPLE

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.

MAPLE

LDS:= proc(L)

  local Cands, r, m;

  Cands:= {$1..floor(nops(L)/2)};

  r:= 0;

for m from 1 while nops(Cands) > 0 do

     Cands:= select(c -> L[-m] = L[-c-m], Cands);

     if min(Cands) = m then

        r:= m;

        Cands:= subs(m=NULL, Cands);

     fi

   od;

   r

end proc:

A:= 1:

for n from 2 to 10^3 do

  if LDS([A, 1]) < LDS([A, 2]) then A:= A, 1 else A:= A, 2 fi;

od:

seq(A[i], i=1..10^3); # Robert Israel, Jun 22 2015

MATHEMATICA

a[1]=1; a[2]=2; suffix[lst_] := If[MatchQ[lst, {___, b__, b__}], lst /. {___, b__, b__} :> {b}, {}]; a[n_] := a[n] = Module[{aa, lg1, lg2}, aa = Array[a, n-1]; lg1 = suffix[Append[aa, 1]] // Length; lg2 = suffix[Append[aa, 2]] // Length; If[lg1 <= lg2, 1, 2]]; Table[a[n], {n, 1, 105}] (* Jean-Fran├žois Alcover, Dec 11 2014 *)

PROG

(Perl) -le 'print$_.=3**/(.*)(.)\1$/-$2for($_)x99' (Ton Hospel/Phil Carmody) [An example of Perl golfing: use as few (key)strokes as possible]

(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 */

Comment on calculating this sequence and A006346 with Perl, from Hugo van der Sanden, Jun 23 2015: (Start)

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:

my $string = "";

digit('1', 0);

for (2 .. $limit) {

    my($repeat, $digit) = ($string =~ m{ ^ (.*) ([12]) \1 }x) or die;

    digit($digit eq '1' ? '2' : '1', length($repeat) + 1);

}

sub digit {

    my($digit, $repeat) = @_;

    $string = $digit . $string;

    # n A6345(n) A6346(n)

    printf "%s %s %s\n", length($string), $digit, $repeat;

}

This takes about 45s to calculate 50000 terms of both sequences. (End)

CROSSREFS

Cf. A006346, A094840, A157238 (A006345(n) - 1).

Sequence in context: A202340 A049705 A060236 * A122497 A154402 A210682

Adjacent sequences:  A006342 A006343 A006344 * A006346 A006347 A006348

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

EXTENSIONS

More terms from Naohiro Nomoto, May 21 2001

Additional comments from Mitch Harris, Dec 31 2003

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified January 23 01:55 EST 2018. Contains 298093 sequences.