Let Me Make This Abundantly Clear

Wherein as we say too many things about too much…

THE WEEKLY CHALLENGE – PERL & RAKU #171 Task 1


We are buried beneath the weight of information, which is being confused with knowledge; quantity is being confused with abundance and wealth with happiness.

— Tom Waits


Abundant Number

Submitted by: Mohammad S Anwar

Write a script to generate first 20 Abundant Odd Numbers.

According to wikipedia,

A number n for which the sum of divisors σ(n) > 2n, or, equivalently, the sum of proper divisors (or aliquot sum) s(n) > n.

For example, 945 is the first Abundant Odd Number.

Sum of divisors:
1 + 3 + 5 + 7 + 9 + 15 + 21 + 27 + 35 + 45 + 63 + 105 + 135 + 189 + 315 = 975

Discussion

In number theory, a concept we find over-and-over is the search for relationships between sets of divisors and the numbers they multiply to, and exploring the function space of performing alternate operations on these divisor sets, the most common of which is summing them.

But before we begin, terms: What is a divisor, then? A divisor is a number that evenly divides the target value such that there is no remainder. There are always at least two divisors for a number: the multiplicative identity, 1, and the number itself. In the case of the number 1 these two are the same number but can be conceptually considered to be different if you want to view the rules as applying across all numbers. After all, the multiplicative identity times any number results in the original number by definition, and the inverse is also true that any number divided by itself equals 1. And

1 x 1 = 1

so of course it works out.

Although the number itself is sometimes included in a list of divisors under this reasoning, it generally is not, under a different philisophical distinction: in dividing a thing, the collection of parts found to make up the whole is known as the alliquot set. Viewed this way the thing itself undivided has no separate components so cannot be a portion of itself, as there is nothing left over.

The idea of nothing as being a real thing is arguably a relatively new idea in mathematics — as it so self-evidently is nothing, how can it possibly be a thing? The ancient Greek mathematicians had a serious philosophical problem on their hands with the notion. Some other cultures had a better grasp of the material, or perhaps just a better foothold — what they created was a starting point for counting, rather than an entity in itself. As once counting the focus was immediately moved away from the zero-point, what exactly it was was less of a problem and they could move on with life without grappling with the abstraction.

But I’m getting away from the point.

The most common understanding of divisors, with respect to number theory, is the set of all whole values that when multiplied by another whole value greater than 1 yield the number in question. So the trivial divisor of the value 1 is included, but the complement, the number itself, is not. These are then known as the proper divisors, and also sometimes referred to as the aliquot part, as being the same thing.

Usually.

For completeness I should add the definition is far from settled or consistent. Negative numbers are whole numbers, right? These are sometimes included as divisors, and then again 1 and -1 are sometimes explicitly excluded, with or without the number itself and its negative inverse, which may be left in even as we exclude 1. In short, if you can find a combination, be assured some one will be looking at it and be getting loose with the terminology. Be sure to read your definitions closely.

However as far as the various relationships to summing divisors go, if we do decide to include the number itself we just need to change the definitions slightly to allow for this. If we adjust the target values, with some fiddling we can generate congruent number sets within the categories investigators have chiseled out.

And what are those categories? Glad you asked. There’s a lot of them, as this is a popular pastime

If the sum of the proper divisors not including the number itself sum exactly to the number, then that is known as a perfect number. If they sum to less, then the number is deficient. If they sum to more, the number is abundant.

The amount that a divisor sum exceeds its source value is known as its abundance, and a number whose abundance is greater than that of any smaller number is highly abundant. The range of abundance generally grows as the numbers, and hence their factors, grow larger, so if a number’s abundance as a fraction relative to its value is larger than any smaller number than it is known as a superabundant number.

There is a lot of obvious crossover between abundant numbers and numbers that happen to have a lot of divisors; numbers that stand apart as having more divisors than any smaller number are known as highly composite numbers. In fact all highly cpmposite numbers greater than 6 are also abundant numbers. If you think about it, if you can evenly divide a number by 2, 3, and 4 then the complement divisors will be n/2, n/3, and n/4.

If we sum just these components

n/2 + n/3 + n/4 = 6n/12 + 4n/12 + 3n/12 = 13n/12

and we are already abundant as we are larger than n. No take-backsies.

Like describing heavy-metal and EDM music, the sub-genres from here seem to just keep going down into a rabbit-hole of ever-narrowly defined constraints. We have for instance colossally abundant numbers and superior highly composite numbers. We even have weird numbers that somehow don’t fit our preconceived notions.

METHOD

PERL 5 SOLUTION

In previous efforts we have all explored methods for obtaining divisors through trial-division, testing values from 2 up to the square root of the candidate. So this time we aren’t going to do this, and try the right way instead. Which is to say pull in a library of highly-tuned C-code to do it for us. If I was just out exploring around with divisor-sums, this is what I’d recommend anyone do.

That library, in Perl, is Math::Prime::Util, which is a bit of a mouthful, so it also goes by the alias ntheory. This module contains over 200 functions, iterators, custom loop structures and constants all focused on number theory, and is thoroughly amazing. So instead of reinventing the wheel we’re already reinvented and redesigned several times already we’ll devote our efforts to using this library.

Today we use divisors(), which returns a list of divisors that includes the number itself and 1. See what I was saying before? But no mind, we simply pop the last item off, as we know it’s the number itself. We also start at 2 to side-skirt concerns about what to do with 1, which we don’t care about anyway. I’m not going to count the divisor sum as 1 + 1 = 2 and you can’t make me.

The module also provides a loop iterator, fordivisors() which will make a divisor list and build a for loop over the values in one statement, and divisor_sum()which would be I would hope self-evidently useful to this challenge. But you have to leave something to code, no? No you don’t? Well you are technically correct. I just chose not to do it that way, to allow me to explain it next time. Gotta keep some cards in your back pocket.

To satisfy my curiosity I have decided, on finding an abundant number, to also compute its abundance and preserve the divisor list , printing everything out in a nice report when we’re done.

use warnings;
use strict;
use utf8;
use feature ":5.26";
use feature qw(signatures);
no warnings 'experimental::signatures';

use ntheory qw( divisors );
use List::Util qw( sum );

use constant { LIMIT => 20 };

my @abundant;
my $candidate = 2;

while (@abundant < LIMIT) {
    my @d = divisors( $candidate );
    pop @d;
    my $s = sum @d;
    push @abundant, [$candidate, $s - $candidate, join ', ', @d] 
        if $s > $candidate;
    $candidate++;
}

## make report
say "value | abundance | divisors";
say "------+-----------+---------";
say sprintf "%5d | %-9d | %s", $_->@* for @abundant;

The report:

value | abundance | divisors
------+-----------+---------
   12 | 4         | 1, 2, 3, 4, 6
   18 | 3         | 1, 2, 3, 6, 9
   20 | 2         | 1, 2, 4, 5, 10
   24 | 12        | 1, 2, 3, 4, 6, 8, 12
   30 | 12        | 1, 2, 3, 5, 6, 10, 15
   36 | 19        | 1, 2, 3, 4, 6, 9, 12, 18
   40 | 10        | 1, 2, 4, 5, 8, 10, 20
   42 | 12        | 1, 2, 3, 6, 7, 14, 21
   48 | 28        | 1, 2, 3, 4, 6, 8, 12, 16, 24
   54 | 12        | 1, 2, 3, 6, 9, 18, 27
   56 | 8         | 1, 2, 4, 7, 8, 14, 28
   60 | 48        | 1, 2, 3, 4, 5, 6, 10, 12, 15, 20, 30
   66 | 12        | 1, 2, 3, 6, 11, 22, 33
   70 | 4         | 1, 2, 5, 7, 10, 14, 35
   72 | 51        | 1, 2, 3, 4, 6, 8, 9, 12, 18, 24, 36
   78 | 12        | 1, 2, 3, 6, 13, 26, 39
   80 | 26        | 1, 2, 4, 5, 8, 10, 16, 20, 40
   84 | 56        | 1, 2, 3, 4, 6, 7, 12, 14, 21, 28, 42
   88 | 4         | 1, 2, 4, 8, 11, 22, 44
   90 | 54        | 1, 2, 3, 5, 6, 9, 10, 15, 18, 30, 45
Raku Solution



The Perl Weekly Challenge, that idyllic glade wherein we stumble upon the holes for these sweet descents, is now known as

The Weekly Challenge – Perl and Raku

It is the creation of the lovely Mohammad Sajid Anwar and a veritable swarm of contributors from all over the world, who gather, as might be expected, weekly online to solve puzzles. Everyone is encouraged to visit, learn and contribute at

https://theweeklychallenge.org