view release on metacpan or  search on metacpan

lib/Math/NumSeq/Catalan.pm  view on Meta::CPAN

  if ($value <= 3) {
    return 1;
  }

  my $i = _blog2_estimate($value);
  unless (defined $i) {
    $i = log($value) * (1/log(2));
  }
  $i /= 2;

  return int($i);
}

1;
__END__

=for stopwords Ryde Math-NumSeq ie num2s

=head1 NAME

Math::NumSeq::Catalan -- Catalan numbers (2n)! / (n!*(n+1)!)

=head1 SYNOPSIS

 use Math::NumSeq::Catalan;
 my $seq = Math::NumSeq::Catalan->new;
 my ($i, $value) = $seq->next;

=head1 DESCRIPTION

The Catalan numbers

    C(n) = binomial(2n,n) / (n+1)
         = (2n)! / (n!*(n+1)!)

    1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ...  (A000108)
    starting i=0

From the factorial expression it can be seen the values grow roughly as a
power-of-4,

    C(i) = C(i-1) * (2i)*(2i-1) / (i*(i+1))
    C(i) = C(i-1) * 2*(2i-1)/(i+1)
         < C(i-1) * 4

=head2 Odd

Option C<values_type =E<gt> "odd"> can give just the odd part of each
number, ie. with factors of 2 divided out,

    values_type => "odd"

    1, 1, 1, 5, 7, 21, 33, 429, 715, 2431, 4199, ...  (A098597)
    starting i=0

The number of 2s in C(i) is

    num2s = (count-1-bits of i+1) - 1

The odd part is always monotonically increasing.  When i increments num2s
increases by at most 1, ie. a single factor of 2.  In the formula above

    C(i) = C(i-1) * 2*(2i-1)/(i+1)

it can be seen that C(i) gains at least 1 factor of 2, so after dividing out
2^num2s it's still greater than C(i-1).

=head1 FUNCTIONS

See L<Math::NumSeq/FUNCTIONS> for behaviour common to all sequence classes.

=over 4

=item C<$seq = Math::NumSeq::Catalan-E<gt>new ()>

=item C<$seq = Math::NumSeq::Catalan-E<gt>new (values_type =E<gt> $str)>

Create and return a new sequence object.

=back

=head2 Iterating

=over

=item C<$seq-E<gt>seek_to_i($i)>

Move the current sequence position to C<$i>.  The next call to C<next()>
will return C<$i> and its corresponding value.

=back

=head2 Random Access

=over

=item C<$value = $seq-E<gt>ith($i)>

Return the C<$i>'th value.

=item C<$i = $seq-E<gt>value_to_i_estimate($value)>

Return an estimate of the i corresponding to C<$value>.

The current code is based on

    C(n) ~= 4^n / (sqrt(pi*n)*(n+1))

but ignoring the denominator there and so simply taking

    C(n) ~= 4^n
    hence i ~= log4(value)

The 4^n term dominates for medium to large C<$value> (for both plain and
"odd").

=back

=head1 SEE ALSO

L<Math::NumSeq>,