MATLAB Examples

The aliquot parts of a number

This demo file teaches about the aliquot parts of a number, and how to use the functions I've provided.

Author: John D'Errico

e-mail: woodchips@rochester.rr.com

Release: 1.0

Release date: 9/21/08

Contents

The aliquot parts of a number are its proper divisors

For example, the number 12 has the list of prime factors

factor(12)
ans =
     2     2     3

but its proper divisors are given by

aliquotparts(12)
ans =
     1     2     3     4     6

See that N will not be listed as a proper divisor of itself, not for any value of N. In fact, the number 1 has no proper divisors.

aliquotparts(1)
ans =
     1

Of course, prime numbers can have only 1 as a proper divisor.

aliquotparts(17)
ans =
     1

The sum of the aliquot parts, or sum of proper divisors

aliquotsum([2 4 5 6 8 12 27 135 40320])
ans =
  Columns 1 through 8
           1           3           1           6           7          16          13         105
  Column 9
      118800

aliquotsum is efficient and vectorized

In this test, the sum of the divisors for EVERY number from 1 to 100000 is computed in short order.

N = (1:100000)';
tic,pdsum = aliquotsum(N);toc
Elapsed time is 3.735000 seconds.

Show the numbers up to 100000 with the largest relative sums of their proper divisors.

[pdsum,tags] = sort(pdsum./N,'descend');
disp('         N,      sigma(N)./N')
disp([N(tags(1:10)),pdsum(1:10)])
         N,      sigma(N)./N
        55440        3.187
        83160       3.1558
        65520       3.1333
        98280       3.1026
        75600       3.0677
        85680       3.0639
        27720       3.0519
        95760       3.0401
        90720       3.0333
        60480       3.0317

You can also count the number of divisors

This is just the sum of the zero'th powers of the divisors. Logically, we expect all the prime numbers to have only one divisor.

N = (1:20)';
[N,aliquotsum(N,0)]
ans =
     1     0
     2     1
     3     1
     4     2
     5     1
     6     3
     7     1
     8     3
     9     2
    10     3
    11     1
    12     5
    13     1
    14     3
    15     3
    16     4
    17     1
    18     5
    19     1
    20     5

What number no larger than 100000 has the most proper divisors?

N = (1:100000)';
d = aliquotsum(N,0);
[maxdivisors,Nmax] = max(d)
maxdivisors =
   127
Nmax =
       83160

As you might expect, that number has multiple small factors

factor(Nmax)
ans =
     2     2     2     3     3     3     5     7    11

Or you can form the sum of the p'th powers

Here we will compute the sum of the squares of the aliquot parts.

N = (1:20)';
[N,aliquotsum(N,2)]
ans =
     1     0
     2     1
     3     1
     4     5
     5     1
     6    14
     7     1
     8    21
     9    10
    10    30
    11     1
    12    66
    13     1
    14    54
    15    35
    16    85
    17     1
    18   131
    19     1
    20   146

Perfect numbers

Perfect numbers have their aliquot sums equal to the number itself.

aliquotsum([6 28 496 8128])
ans =
           6          28         496        8128

Abundant numbers

Just under 25% of all numbers are abundant

N = 100000;
100*sum(aliquotsum(1:N)>(1:N))/N
ans =
       24.795

Hyper-abundant numbers

Few (roughly 2%) of numbers are hyper-abundant. I've defined hyper-abundancy as an aliquot sum of the number N that is at least twice as large as N.

N = (1:100000)';

As a percentage...

100*sum(aliquotsum(N)>(2*N))./100000
ans =
         2.02

Show the numbers up to 100000 with the largest relative sums of their proper divisors.

pdsum = aliquotsum(N);
[pdsum,tags] = sort(pdsum./N,'descend');
disp('         N,      sigma(N)./N')
disp([N(tags(1:10)),pdsum(1:10)])
         N,      sigma(N)./N
        55440        3.187
        83160       3.1558
        65520       3.1333
        98280       3.1026
        75600       3.0677
        85680       3.0639
        27720       3.0519
        95760       3.0401
        90720       3.0333
        60480       3.0317

Collosally-abundant numbers?

How hyper-abundant can they get? Is there a maximum?

N = 1000000;
pdsum = aliquotsum(1:N);
[maxsum,whichN] = max(pdsum)
maxsum =
     3392928
whichN =
      997920

It does not appear that there is any maximum value to this ratio. Certainly it exceeds 3. Mathworld suggests (Collossally abundant) that the ratio can get fairly large. Add 1 to get the ratio they list.

maxsum/whichN
ans =
          3.4

Odd abundant numbers are less common than the abundant numbers in general

The smallest odd abundant number is 945.

N = (1:2:10000)';
pdsum = aliquotsum(N);
ind = find(pdsum>N);
N(ind)'
ans =
  Columns 1 through 8
         945        1575        2205        2835        3465        4095        4725        5355
  Columns 9 through 16
        5775        5985        6435        6615        6825        7245        7425        7875
  Columns 17 through 23
        8085        8415        8505        8925        9135        9555        9765

The odd abundant numbers are also "less" abundant

The third column here is the extent of the overabundancy. Since 1.0 there would indicate a perfect number, these odd abundants are all clearly just barely so. I wonder, is there a limit to the extent of abundancy for the odd numbers? Are any hyper-abundant, as I've defined it above?

N = (1:2:1000000)';
pdsum = aliquotsum(N);
maxOddAbundancy = max(pdsum./N)
maxOddAbundancy =
       1.4665

Why are the odd abundants so rare?

We can get some idea as to the reason why odd abundant numers are so rare, by looking at the factors of a highly abundant even number.

Try 840 for example. Clearly it has multiple powers of 2 in its factorization.

factor(840)
ans =
     2     2     2     3     5     7

840 is also quite abundant.

aliquotsum(840)
ans =
        2040

If we look at the factors of the most highly abundant numbers, you will generally find many spare powers of 2. But how about the odd abunbdants? There are no powers of 2 allowed in an odd number, so pick some of the odd abundant numbers and look at their factors. As expected, we find some extra powers of 3, along with some other moderately small odd primes.

factor(945)
factor(9765)
ans =
     3     3     3     5     7
ans =
     3     3     5     7    31

Pick a rather large odd number that will have very many factors. Unfortunately, this is close to as far as aliquotsum will go, due to the limits of MATLAB's operating precision. I'll admit the ratio is starting to approach 2.

N = 3*3*3*5*5*7*7*11*13*17*19
aliquotsum(N)/N
N =
   1.5277e+09
ans =
       1.7981

Deficient numbers

All primes are deficient, as are all pure powers of prime numbers. As well, all the divisors of any perfect number are known to be deficient.

aliquotsum(primes(50))
ans =
     1     1     1     1     1     1     1     1     1     1     1     1     1     1     1

Maximally deficient numbers

Naturally, the prime numbers represent the most deficient numbers possible, since each prime has only one divisor less than itself, and that is the number 1. If we ignore the prime numbers, which numbers are the next most deficient? Do you see a pattern?

N = setdiff(1:50,primes(50))';
[N,aliquotsum(N)]
ans =
     1     0
     4     3
     6     6
     8     7
     9     4
    10     8
    12    16
    14    10
    15     9
    16    15
    18    21
    20    22
    21    11
    22    14
    24    36
    25     6
    26    16
    27    13
    28    28
    30    42
    32    31
    33    15
    34    20
    35    13
    36    55
    38    22
    39    17
    40    50
    42    54
    44    40
    45    33
    46    26
    48    76
    49     8
    50    43

Amicable numbers

A pair of numbers is amicable if their aliquot sums are equal to the other member of the pair.

aliquotsum([220 284])
ans =
   284   220

Sociable numbers form cliques, or amicable cycles

Perfect numbers are self-amicable, with a cycle length of 1. Amicable pairs have a cycle length of 2. This cycle has length 5 before it returns to the start.

aliquotsum([12496 14288 15472 14536 14264])
ans =
       14288       15472       14536       14264       12496

Amicable cycles

Perfect numbers are self-amicable. The amicablecycles function:

cycles = amicablecycles(N,L)

will find all cycles that start with a number as large as N. The length of the cycle is L.

amicablecycles(20000,1)
ans =
           6
          28
         496
        8128

Amicable pairs have a cycle length of 2.

amicablecycles(20000,2)
ans =
         220         284
        1184        1210
        2620        2924
        5020        5564
        6232        6368
       10744       10856
       12285       14595
       17296       18416

There are no known sociable cliques of length 3 or 4

amicablecycles(20000,3)
amicablecycles(20000,4)
ans =
   Empty matrix: 0-by-3
ans =
   Empty matrix: 0-by-4

The smallest cycle of length 5 starts at 12496

amicablecycles(20000,5)
ans =
       12496       14288       15472       14536       14264

Odd amicables

You can force amicablecycles to look only at certain starting points. For example, to find the odd amicable cycles only

amicablecycles(1:2:200000,2)
ans =
       12285       14595
       67095       71145
       69615       87633
      100485      124155
      122265      139815

Some interesting things to try

What fun things can you find to do with these numbers? Can you find any odd perfect numbers? Perhaps a quasi-perfect number?

Some simple problems for the student, and a few that may not be so simple.

1. Which numbers have many distinct divisors?

2. What is the smallest number to have exactly 31 divisors?

3. Does the product of the first k primes necessarily have the largest number of distinct divisors?

4. Can you construct a number less than 2*3*5*7*11 that has more divisors than this number?

5. For which values of non-prime numbers N is the lower bound sqrt(N)+1 realized for the aliquot sum?

6. Can you prove that sqrt(N)+1 forms a lower bound for the aliquot sum for the non-prime numbers N?

7. Is there a simple relationship for the upper bound of the aliquot sum as a function of N? Consider N*log(N) as a start.

8. There are many abundant numbers. As was shown above, roughly 25% of all numbers are abundant. Can you generate the list of all abundant numbers up to some value? (Start with the aliquotsum function.) What is the smallest abundant number?

9. The odd abundant numbers were shown to be somewhat rare, and always seemed to have multiple powers of 3 in their representations. Are there any abundants that do not have either 2 or 3 as a factor? Can this happen? Note that such an investigation might involve numbers that are too large for the tools I've provided to work with properly.

N = vpi(5)*5*5*5*5*5*7*7*7*11*13
aliquotsum(N)
N =
   766390625
ans =
   546092575

10. Can you represent numbers as the sum of two abundant numbers? Which numbers are not so representable? Is there a smallest number such that all those above it are the sum of two abundant numbers?

11. An interesting generalization of a perfect number is what I'll call the p-perfect number. Thus, if a perfect number is an integer such that the sum of its proper divisors adds up to the number itself, a p-perfect number N might have the sum of the p'th powers of the divisors adding up to N^p. Do any such numbers exist? Can you show this cannot happen? Or are there any numbers with the squares of the divisors that adds up to the original number?

12. How about p-amicability? Can you think of a way to generalize this concept?