# # A030190 bits, A030303 positions of 1s
   # [ 'Math::NumSeq::ChampernowneBinary', 0,
   #   [ 1, 2, 4, 5, 6, 9, 11, 12, 13, 15, 16, 17, 18, 22,
   #     25, 26, 28, 30, 32, 33, 34, 35, 38, 39, 41, 42, 43,
   #     44, 46, 47, 48, 49, 50, 55, 59, 60, 63, 65, 68, 69,
   #     70, 72, 75, 77, 79, 80, 82, 83, 85, 87, 88, 89, 90,
   #     91, 95, 96, 99, 100, 101, 103, 105 ] ],



# Copyright 2010, 2011, 2013 Kevin Ryde

# This file is part of Math-NumSeq.
#
# 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/>.

package Math::NumSeq::ChampernowneBinary;
use 5.004;
use strict;

use vars '$VERSION', '@ISA';
$VERSION = 86;
use Math::NumSeq;
@ISA = ('Math::NumSeq');


# uncomment this to run the ### lines
#use Smart::Comments;

# use constant name => Math::NumSeq::__('Champernowne Sequence');
use constant description => Math::NumSeq::__('Champernowne sequence 1 positions, 1,2,4,5,6,9,11,etc, being the 1-bit positions when the integers 1,2,3,4,5 etc are written out concatenated in binary 1 10 11 100 101 etc.');
use constant i_start => 1;
use constant values_min => 1;
use constant characteristic_increasing => 1;

# 0 1 10  11 100 101  110 111
#   1 2  4,5 6   9,11 12,13 15,16,17,
#    
# cf A030302 - base 2, starting i=1 value=1
#    A030190 - base 2, start i=0 value=0
#    A030303 - base 2 positions of 1s, start 1
#    A030308 - binary reverse starting from 1
#    A030309 - positions of 0 in reverse
#    A030310 - positions of 1 in reverse
#    A030305 - base 2 lengths of runs of 0s
#    A030306 - base 2 lengths of runs of 1s
#
#    A003137 - base 3, start i=1 value=1
#    A054635 - base 3, start i=0 value=0
#    A054637 - base 3 partial sums, start i=0 value=0
#
#    A030998 - base 7, start i=0 value=0
#    A031007 - base 7 reverse, start i=1 value=1
#
#    A031035 - base 8, start i=1 value=1
#    A054634 - base 8, start i=0 value=0
#    A031045 - base 8 reverse, start i=1 value=1
#
#    A031076 - base 9, start i=1 value=1
#    A031087 - base 9 reverse, start i=1 value=1
#
#    A033307 - decimal, start i=1 value=1
#    A007376 - same, decimal, Barbier infinite word, start i=1 value=1
#    A054632 - decimal partial sums
#    A031298 - decimal reverse to LSB digit first, start i=1 value=1
#
#    A136414 - decimal 2 digits at a time, start i=1 value=1
#    A193431 - decimal 3 digits at a time
#    A193492 - decimal 4 digits at a time
#    A193493 - decimal 5 digits at a time
#    A001704 - concatenate n,n+1
#    A127421 - numbers concat of n,n+1, eg. 1819
#
#    A033308 - concatenate primes
#
# sub oeis_anum {
#   my ($class_or_self) = @_;
#   if (! ref $class_or_self ||
#       $class_or_self->{'radix'} == 2) {
#     return 'A030303';
#   }
#   return undef;
# }
#
use constant oeis_anum => 'A030303'; # position of i'th 1


sub rewind {
  my ($self) = @_;
  $self->{'i'} = $self->i_start;
  $self->{'n'} = 0;
  $self->{'val'} = 0;
  $self->{'bitmask'} = 0;
}
sub next {
  my ($self) = @_;
  ### ChampernowneBinary next(): $self

  my $bitmask = $self->{'bitmask'};
  for (;;) {
    if ($bitmask == 0) {
      $self->{'val'}++;
      $bitmask = 1;
      while ($bitmask <= $self->{'val'}) {
        $bitmask <<= 1;
      }
      $bitmask >>= 1;
      ### next val: sprintf('%#X',$self->{'val'})
      ### bitmask: sprintf('%#X',$bitmask)
    }
    $self->{'n'}++;
    if ($bitmask & $self->{'val'}) {
      $self->{'bitmask'} = $bitmask >> 1;
      ### result: $self->{'n'}
      return ($self->{'i'}++, $self->{'n'});
    }
    $bitmask >>= 1;
  }
}

# ENHANCE-ME: msb 1 bit position determines next lower (k+1)*2^k.
#
# 0   0 1
# 2   10 11
# 6   100 101 110 111
#
sub pred {
  my ($self, $n) = @_;
  ### ChampernowneBinary pred(): $n
  if ($n < 2) { return $n; }

  my $base = 2;
  my $bits_each = 2;
  my $nums = 2;
  for (;;) {
    my $next_base = $base + $nums*$bits_each;
    last if ($next_base > $n);
    $base = $next_base;
    $bits_each++;
    $nums <<= 1;
  }
  $n -= $base;
  ### offset: $n
  my $pos = (-1-$n) % $bits_each;
  $n = int($n / $bits_each) + $nums;
  ### $base
  ### $bits_each
  ### $nums
  ### $pos
  ### val: sprintf('%#X',$n)
  return (($n >> $pos) & 1);
}

1;
__END__