/ 
Math-NumSeq-73
River stage zero No dependents
/ Math::NumSeq::Abundant

NAME

Math::NumSeq::Abundant -- abundant numbers, greater than sum of divisors

SYNOPSIS

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

DESCRIPTION

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.

Deficient

Option 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).

Primitive Abundant

Option 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.

Option 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.

Perfect Numbers

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.

FUNCTIONS

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 $seq.

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.

FORMULAS

Predicate

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

Predicate -- Primitive

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

SEE ALSO

Math::NumSeq

HOME PAGE

http://user42.tuxfamily.org/math-numseq/index.html

LICENSE

Copyright 2010, 2011, 2012, 2013, 2014, 2016 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/>.