Math::NumSeq::Catalan -- factorials i! = 1*2*...*i
use Math::NumSeq::Catalan; my $seq = Math::NumSeq::Catalan->new; my ($i, $value) = $seq->next;
The Catalan numbers binomial(2n,n)/(n+1) = (2n)!/(n!*(n+1)!)
# starting i=0 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, ...
From the factorial expression it can be seen the values grow roughly as a power-of-4,
C(5) = 42 = 14 * 2*(2*5-1)/6
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
values_type => "odd" can give just the odd part of each number, ie. with factors of 2 divided out,
1, 1, 1, 5, 7, 21, 33, 429, 715, 2431, 4199, ...
The number of 2s in C(i) is
num2s = (count 1-bits of i+1) - 1
When i increments this num2s increases by at most 1, which can eat the "2*" factor shown in the C(i) formula above. But because num2s doesn't increase by more than that the OddC(i) values are monotonically increasing.
See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence classes.
$seq = Math::NumSeq::Catalan->new ()
$seq = Math::NumSeq::Catalan->new (values_type => $str)
Create and return a new sequence object.
Move the current sequence position to
$i. The next call to
$iand corresponding value.
$value = $seq->ith($i)
$i = $seq->value_to_i_estimate($value)
Return an estimate of the i corresponding to
The current code is based on C(n) ~= 4^n / (sqrt(pi*n)*(n+1)), but just estimating i=log4(value) since the 4^n term dominates for medium to large
$value(for both plain and "odd").
Copyright 2012, 2013 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/>.