Kevin Ryde > Math-NumSeq > Math::NumSeq::Abundant

Download:
Math-NumSeq-71.tar.gz

Dependencies

Annotate this POD

Website

CPAN RT

Open  2
View/Report Bugs
Module Version: 71   Source  

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

syntax highlighting: