## Highly Abundant Numbers

### December 20, 2016

We studied highly composite numbers in a series of several previous exercises, and had a lot of fun. In today’s exercise we look at a related concept: highly abundant numbers (A002093).

Highly abundant numbers are those numbers *n* such that `sigma`

(*m*) < `sigma`

(*n*) for all *m* < *n*, where *m* and *n* are positive integers and `sigma`

(*n*) is the sum of the divisors of *n*. For instance, 12 is a highly abundant number since the sum of its divisors is 1 + 2 + 3 + 4 + 6 + 12 = 28, and no number less than 12 has a greater sum of divisors.

Your task is to compute the sequence of highly abundant numbers. When you are finished, you are welcome to read or run a suggested solution, or to post your own solution or discuss the exercise in the comments below.

Pages: 1 2

We can express the divisor sum, sigma(n), as a product of sums of powers of prime divisors, so sigma(60) = sigma(2*2*3*5) = (1+2+2*2)(1+3)(1+5) = 7*4*6 = 168. In python, with a very simple factorizing function:

However, since we want to find sigma(n) for all n (up to some point) we can use a variation of the Sieve of Eratosthenes to save a lot of factoring. Here, we build up the divisors sums, using the formula above, in array a, using array b to store the sums of powers for each prime p:

The problem can divide into the following part

a) find all divisors and it’s sum

b) keep tracking the current abundant sum until we find the next one

[/sourcecode lang="css"]

(define (find-divisor p)

(define (find-divisor-iter p current divisor-list)

(cond ((eq? current 0) divisor-list)

((eq? (remainder p current) 0) (find-divisor-iter p (- current 1) (cons current divisor-list)))

(else (find-divisor-iter p (- current 1) divisor-list))))

(find-divisor-iter p p ‘()))

(define (print-abundant current current-max)

(let ((d-list (find-divisor current)))

(let ((s (apply + d-list)))

(cond ((> s current-max) (begin (display current) (display “—–“)(display current-max) (newline) (print-abundant (+ 1 current) s)))

(else (print-abundant (+ 1 current) current-max))))))

[/sourcecode]

Repost due to mis-formated post, why i can’t just edit the old post?

The problem can divide into the following part

a) find all divisors and it’s sum

b) keep tracking the current abundant sum until we find the next one