Math::NumSeq::Kolakoski -- sequence of 1s and 2s its own run lengths
use Math::NumSeq::Kolakoski; my $seq = Math::NumSeq::Kolakoski->new; my ($i, $value) = $seq->next;
A sequence 1,2,2,1,1,2,1,etc, each run length being given successively by the sequence itself.
Starting from 1,2, at i=2 the values is 2, so there should be a run of two 2s. Then at i=3 value 2 means two 1s. Then at i=4 value 1 means a run of one 2. The value alternates between 1 and 2 and the sequence values themselves determine the run length to give that value, either 1 or 2.
See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence classes.
There's no need to keep the entire sequence, nor even the portion between where i is up to and the values past that which those up to i induce. Instead the value at i is determined by the earlier value, which is determined a yet earlier value, etc. At each level only a value and pending count need to be kept. The levels required end up being about log base 1.6 of the position i.
Copyright 2011, 2012, 2013, 2014, 2016, 2019 Kevin Ryde
Math-NumSeq is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
Math-NumSeq is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with Math-NumSeq. If not, see <http://www.gnu.org/licenses/>.