File Coverage

blib/lib/Math/NumSeq/GolombSequence.pm

Criterion	Covered	Total	%
statement	118	119	99.1
branch	17	18	94.4
condition	1	3	33.3
subroutine	21	21	100.0
pod	3	3	100.0
total	160	164	97.5

# Copyright 2011, 2012, 2013, 2014 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 .



# Maybe: using_values => 'primes'
#
# http://mathworld.wolfram.com/SilvermansSequence.html
#
# Y.-F. S. Petermann, J.-L. Remy and I. Vardi, Discrete derivatives of
# sequences, Adv. in Appl. Math. 27 (2001), 562-84.
#   http://www.lix.polytechnique.fr/Labo/Ilan.Vardi/publications.html
#   http://www.lix.polytechnique.fr/Labo/Ilan.Vardi/discrete_derivatives.ps
#
# cf A112377 self seq sub1 drop 0s    1, 2, 1, 1, 3, 1, 2
#    A112378 self seq add1 drop 0s
#    A112379 self seq sub1 drop 0s    1, 2, 1, 3,
#    A112380 self seq sub1 drop 0s    1, 2, 1, 1, 3, 2, 1


package Math::NumSeq::GolombSequence;
use 5.004;
use strict;
use Carp;

use vars '$VERSION', '@ISA';
$VERSION = 71;

use Math::NumSeq;
@ISA = ('Math::NumSeq');

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

# use constant name => Math::NumSeq::__('Golomb Sequence');
use constant description => Math::NumSeq::__('Golomb sequence 1,2,2,3,3,4,4,4,etc, its own run lengths.');
use constant i_start => 1;
use constant values_min => 1;
use constant characteristic_smaller => 1;
use constant characteristic_non_decreasing => 1;
use constant characteristic_integer => 1;

use constant parameter_info_array =>
  [
   { name    => 'using_values',
     display => Math::NumSeq::__('Using Values'),
     type    => 'enum',
     default => 'all',
     choices => ['all','odd','even','3k','squares','primes'],
     choices_display => [Math::NumSeq::__('All'),
                         Math::NumSeq::__('Odd'),
                         Math::NumSeq::__('Even'),
                         # TRANSLATORS: "3k" meaning triples 3,6,9,12,15, probably no need to translate except into another script if Latin letter "k" won't be recognised
                         Math::NumSeq::__('3k'),
                         Math::NumSeq::__('Squares'),
                         Math::NumSeq::__('Primes'),
                        ],
     description => Math::NumSeq::__('Which values to use in the sequence.  Default "all" means all integers.'),
   },
  ];

#------------------------------------------------------------------------------

# cf A001463 golomb seq partial sums
#    A088517 golomb first diffs, is 0/1 characteristic of partial sums
#    A163563 a(n)+1 reps
#    A113722 a(n) reps of 2n+1
#    A113724 a(n) reps of 2n+2 evens
#    A103320 condensed 1,22,33,444,555,6666 etc
#    A104236 n*golomb(n)
#    A143125 n*golomb(n) cumulative
#    A095773 generalizing
#    A116548 divisors occurring fewer than a(n) times
#    A072649 n occurs Fibonacci(n) times
#    A108229 n occurs Lucas(n) times
#    A109167 n appears a(n) times
#
my %oeis_anum = (all   => 'A001462',
                 # OEIS-Catalogue: A001462

                 odd => 'A080605',
                 # OEIS-Catalogue: A080605 using_values=odd

                 even => 'A080606',
                 # OEIS-Catalogue: A080606 using_values=even

                 '3k' => 'A080607',
                 # OEIS-Catalogue: A080607 using_values=3k

                 'squares' => 'A013189',
                 # OEIS-Catalogue: A013189 using_values=squares

                 'primes' => 'A169682',
                 # OEIS-Catalogue: A169682 using_values=primes
                );
sub oeis_anum {
  my ($self) = @_;
  return $oeis_anum{$self->{'using_values'}};
}

#------------------------------------------------------------------------------
#
# count[0] is how many of value[0] still to be returned
# when count[0]==0 must increment value[0] and new count from k=1


sub rewind {
  my ($self) = @_;
  $self->{'i'} = $self->i_start;

  my $using_values = $self->{'using_values'};
  $self->{'upto_func'} = $self->can("_upto_$using_values")
    || croak "Unrecognised using_values \"$using_values\"";

  # ENHANCE-ME: a hash table for these initializations, but would have to
  # clone the arrays
  if ($using_values eq 'all') {
    $self->{'small'} = [ 1, 2, 2 ];
    $self->{'counts'} = [ 2 ];
    $self->{'values'} = [ 3 ];
    $self->{'upto'}   = [ 3 ];
    $self->{'extend_count'} = 2;
    $self->{'extend_value'} = 3;
    $self->{'extend_upto'}  = 3;

  } elsif ($using_values eq 'odd') {
    $self->{'counts'} = [ 1, 3 ];
    $self->{'upto'}   = [ 1, 2 ];
    $self->{'values'} = [ 1, 3 ];
    $self->{'extend_count'} = 2;
    $self->{'extend_value'} = 3;
    $self->{'extend_upto'}  = 2;

  } elsif ($using_values eq 'even') {
    $self->{'counts'} = [ 2 ];
    $self->{'values'} = [ 4 ];
    $self->{'upto'}   = [ 2 ];
    $self->{'small'} = [ 2, 2 ];
    $self->{'extend_count'} = 2;
    $self->{'extend_value'} = 4;
    $self->{'extend_upto'}  = 2;

  } elsif ($using_values eq '3k') {
    $self->{'counts'} = [ 3 ];
    $self->{'values'} = [ 3 ];
    $self->{'upto'}   = [ 1 ];
    $self->{'extend_count'} = 2;
    $self->{'extend_value'} = 3;
    $self->{'extend_upto'}  = 1;

  } elsif ($using_values eq 'squares') {
    $self->{'counts'} = [ 1, 4 ];
    $self->{'values'} = [ 1, 4 ];
    $self->{'upto'}   = [ 1, 2 ];
    $self->{'extend_count'} = 3;
    $self->{'extend_value'} = 4;
    $self->{'extend_upto'}  = 2;

  } elsif ($using_values eq 'primes') {
    $self->{'small'} = [ 2, 2 ];
    $self->{'counts'} = [ 2 ];
    $self->{'values'} = [ 3 ];
    $self->{'upto'}   = [ 2 ];
    $self->{'extend_count'} = 2;
    $self->{'extend_value'} = 3;
    $self->{'extend_upto'}  = 2;
    $self->{'primes'} = [ 2, 3, 5 ];

  } else {
    croak "Unrecognised using_values: ",$using_values;
  }
}

sub _upto_all {
  my ($self, $upto) = @_;
  return $upto;
}
sub _upto_odd {
  my ($self, $upto) = @_;
  return 2*$upto-1;
}
sub _upto_even {
  my ($self, $upto) = @_;
  return 2*$upto;
}
sub _upto_3k {
  my ($self, $upto) = @_;
  return 3*$upto;
}
sub _upto_squares {
  my ($self, $upto) = @_;
  return $upto*$upto;
}
sub _upto_primes {
  my ($self, $upto) = @_;
  $upto--;
  my $primes = $self->{'primes'};
  if ($upto > $#$primes) {
    require Math::NumSeq::Primes;
    @$primes = Math::NumSeq::Primes::_primes_list (2, 2 * $primes->[-1]);
  }
  return $primes->[$upto];
}

sub next {
  my ($self) = @_;
  ### GolombSequence next(): "i=$self->{'i'}"
  ### counts: join(',',@{$self->{'counts'}})
  ### values: join(',',@{$self->{'values'}})

  if (defined (my $value = shift @{$self->{'small'}})) {
    return ($self->{'i'}++, $value);
  }

  my $values = $self->{'values'};
  my $upto = $self->{'upto'};
  my $ret = $values->[0];

  my $counts = $self->{'counts'};
  for (my $pos = 0; --$counts->[$pos] <= 0; $pos++) {
    if ($pos >= $#$counts) {
      ### extend ...
      push @$counts, $self->{'extend_count'};
      push @$upto,   $self->{'extend_upto'};
      push @$values, $self->{'extend_value'};
    }
    $upto->[$pos]++;
    my $upto_func = $self->{'upto_func'};
    $values->[$pos] = $self->$upto_func($upto->[$pos]);
    $counts->[$pos] = $values->[$pos+1];
  }
  return ($self->{'i'}++, $ret);
}

1;
__END__