Math::NumSeq::Abundant -- abundant numbers, greater than sum of divisors
use Math::NumSeq::Abundant; my $seq = Math::NumSeq::Abundant->new; my ($i, $value) = $seq->next;
The abundant numbers, being integers greater than the sum of their divisors,
12, 18, 20, 24, 30, 36, ... starting i=1
For example 12 is abundant because its divisors 1,2,3,4,6 add up to 16 which is > 12.
This is often expressed as 2*n>sigma(n) where sigma(n) is the sum of divisors of n including n itself.
abundant_type => "deficient" is those integers n with n < sum divisors,
abundant_type => "deficient" 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13,
This is the opposite of abundant, except the few perfect numbers n == sum divisors are excluded (see "Perfect Numbers" below).
abundant_type => "primitive" gives abundant numbers which are not a multiple of some smaller abundant,
abundant_type => "primitive" 12, 18, 20, 30, 42, 56, 66, 70, 78, ...
If an integer n is abundant then so are all multiples 2*n, 3*n, 4*n, etc. The "primitive" abundants are those which are not such a multiple.
abundant_type => "non-primitive" gives abundant numbers which are not primitive, ie. which have a divisor which is also abundant.
abundant_type => "non-primitive" 24, 36, 40, 48, 54, 60, 72, 80, 84, ...
The abundant are all either primitive or non-primitive.
Numbers with n == sum divisors are the perfect numbers 6, 28, 496, 8128, 33550336, etc. There's nothing here for them currently. They're quite sparse, with Euler proving the even ones are always n=2^(k-1)*(2^k-1) for prime 2^k-1 (those being the Mersenne primes). The existence of any odd perfect numbers is a famous unsolved problem. If there are any odd perfect numbers then they're very big.
See "FUNCTIONS" in Math::NumSeq for behaviour common to all sequence classes.
$seq = Math::NumSeq::Abundant->new ()
$seq = Math::NumSeq::Abundant->new (abundant_type => $str)
Create and return a new sequence object.
abundant_type (a string) can be
"abundant" n > sum divisors (the default) "deficient" n < sum divisors "primitive" abundant and not a multiple of an abundant "non-primitive" abundant and also a multiple of an abundant
$bool = $seq->pred($value)
Return true if
$value is abundant, deficient or primitive abundant per
This check requires factorizing
$value and in the current code a hard limit of 2**32 is placed on values to be checked, in the interests of not going into a near-infinite loop.
For prime factorization n=p^a * q^b * ... the divisors are all of
divisor = p^A * q^B * ... for A=0 to a, B=0 to b, etc
This includes n itself with A=a,B=b,etc. The sum is formed by grouping each with factor p^i, etc, resulting in a product,
sigma = (1 + p + p^2 + ... + p^a) * (1 + q + q^2 + ... + q^a) * ... sigma = (p^(a+1)-1)/(p-1) * (q^(b+1)-1)/(q-1) * ...
So from the prime factorization of n the sigma is formed and compared against n,
sigma > 2*n abundant sigma < 2*n deficient
For primitive abundant we want to know also that no divisor of n is abundant.
For divisors of n it suffices to consider n reduced by a single prime, so n/p. If taking out some non-prime such as n/(p*q) gives an abundant then so is n/p because it's a multiple of n/(p*q). To testing an n/p for abundance,
sigma(n/p) > 2*n/p means have an abundant divisor
sigma(n/p) can be calculated from sigma(n) by dividing out the p^a term described above and replacing it with the term for p^(a-1).
oldterm = (p^(a+1) - 1)/(p-1) newterm = (p^a - 1)/(p-1) sigma(n) * newterm / oldterm > n/p sigma(n) * p*newterm / oldterm > n
p*newterm/oldterm simplifies to
sigma(n) * (1 - 1/oldterm) > n means an abundant divisor
The left side is a maximum when the factor (1 - 1/oldterm) reduces sigma(n) by the least, and that's when oldterm is the biggest. So to test for primitive abundance note the largest term in the sigma(n) calculation above.
if sigma(n) > 2*n then n is abundant if sigma(n) * (1-1/maxterm) > 2*n then have an abundant divisor and so n is not primitive abundant
Copyright 2010, 2011, 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/>.