## Non-Abundant Sums

### January 28, 2020

Our solution comes in three parts: first find abundant numbers, second find sums, and third compute the solution. Here we compute the list of abundant numbers less than or equal to 28123, using `factors`

and `sigma`

functions we have written previously, as well as `uniq-c`

from the Standard Prelude:

(define (factors n) (let ((wheel (vector 1 2 2 4 2 4 2 4 6 2 6))) (let loop ((n n) (f 2) (w 0) (fs (list))) (if (< n (* f f)) (reverse (cons n fs)) (if (zero? (modulo n f)) (loop (/ n f) f w (cons f fs)) (loop n (+ f (vector-ref wheel w)) (if (= w 10) 3 (+ w 1)) fs))))))

(define (sigma x n) ; sum of x'th powers of divisors of n (if (= n 1) 1 (let ((fs (uniq-c = (factors n)))) (if (zero? x) (apply * (map add1 (map cdr fs))) (apply * (map (lambda (p a) (/ (- (expt p (* (+ a 1) x)) 1) (- (expt p x) 1))) (map car fs) (map cdr fs)))))))

(define abuns (filter (lambda (n) (< (+ n n) (sigma 1 n))) (range 1 28124)))

Function `2abun`

returns two abundant numbers that sum to *n*, if they exist, or `#f`

if there is no solution:

(define (2abun n) (let loop ((abuns abuns)) (if (null? abuns) #f (if (< 28123 (+ (car abuns) (car abuns))) #f (if (member (- n (car abuns)) abuns) (list (car abuns) (- n (car abuns))) (loop (cdr abuns)))))))

We compute the requested sum with the statement `(filter (complement 2 abun) (range 1 28124))`

in 95 seconds; it’s slow because `member`

repeatedly searches the 6965 elements of the `abuns`

list in linear time. To speed up the program, we convert the `abuns`

list to a hash set:

(define abunset (let ((abunset (make-hashtable (lambda (n) n) = 7000))) (do ((abuns abuns (cdr abuns))) ((null? abuns) abunset) (hashtable-set! abunset (car abuns) (car abuns)))))

(define (2abun n) (let loop ((abuns abuns)) (if (null? abuns) #f (if (< 28123 (+ (car abuns) (car abuns))) #f (if (hashtable-contains? abunset (- n (car abuns))) (list (car abuns) (- n (car abuns))) (loop (cdr abuns)))))))

Now we compute the result in about a seventh of a second. There are 1456 positive integers that cannot be written as the sum of two abundant numbers, of which the largest is 20161.

Ideone seems to be having problems; I’ll post the exercise there when it returns.

Link to read does not work, and there is no run link.

Here’s a Python solution that makes use of the multiplicativity of divisor sum:

That prints the total number of non-abundant sum numbers (like the Praxis solution at https://programmingpraxis.com/2020/01/28/non-abundant-sums/2/, except mine includes 0).

Here is my take on this in Julia: https://pastebin.com/9XL9fWs5

Total run time (including the time-consuming printing of the numbers): 44.5 sec.

Memory usage: 59.04 MB

Naturally, this code could be improved, something I may venture another time.

Cheers for the intriguing problem! Definitely saved me a lot of time going through the PE archive and skimming through all the overly mathematical problems there!

Reusing some code from https://programmingpraxis.com/2016/12/20/highly-abundant-numbers/, here’s a C++ version of that Python solution. Once again, just the count of non-sum numbers is printed: