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

Math-NumSeq-72.tar.gz

Dependencies

Annotate this POD

Website

# CPAN RT

 Open 0
View/Report Bugs
Module Version: 72

# 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```

Math::NumSeq

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