﻿ Project Euler Problem 23
You are on the Home/Other Tutorials/Project Euler/Problem 23 page

Web This Site

# Project Euler - Problem 23

## Problem description

A perfect number is a number for which the sum of its proper divisors is exactly equal to the number. For example, the sum of the proper divisors of 28 would be 1 + 2 + 4 + 7 + 14 = 28, which means that 28 is a perfect number.

A number whose proper divisors are less than the number is called deficient and a number whose proper divisors exceed the number is called abundant.

As 12 is the smallest abundant number, 1 + 2 + 3 + 4 + 6 = 16, the smallest number that can be written as the sum of two abundant numbers is 24. By mathematical analysis, it can be shown that all integers greater than 28123 can be written as the sum of two abundant numbers. However, this upper limit cannot be reduced any further by analysis even though it is known that the greatest number that cannot be expressed as the sum of two abundant numbers is less than this limit.

Find the sum of all the positive integers which cannot be written as the sum of two abundant numbers.

## Solution

This problem cried out for one to adapt the Sieve of Eratosthenes technique in which one creates a list of all numbers and then zeros out those elements that meet a particular requirement.  In the original sieve, the criterion was non-primality.  In this problem, we will apply two sieves, the first to identify abundant numbers, the second to identify numbers that are not the sum of two abundant numbers.  In the first sieve, we don't zero out elements.  Instead, we add non-zero elements that meet our criterion.  In the second sieve, we zero out elements that are the sum of 2 abundant numbers (thereby leaving as non-zero all those numbers that are *not* the sum of two abundant numbers.

The first part of the code generates the list of abundant numbers.  The second part of the code removes all numbers that are the sum of abundant numbers.  Note that each nested loop searches only through those numbers that yield results less than or equal to 28123*.  The code runs in about 2 seconds on my Core 2 Duo laptop.

For the getFactors function see the Euler Support page.

```Sub Euler023()
Const cLim As Integer = 28123
Dim AbundantNbrs(cLim) As Boolean, AbundantSums(cLim) As Integer
Dim I As Integer, J As Integer
Dim StartTime As Single
StartTime = Timer
For I = 0 To UBound(AbundantNbrs)
AbundantSums(I) = I
Next I
'The first abundant number is 12 and, according to Wikipedia, _
all multiples of an abundant number are abundant numbers themselves
For I = 12 To UBound(AbundantNbrs)
If AbundantNbrs(I) Then
ElseIf Sum(getFactors(I)) - I > I Then
AbundantNbrs(I) = True
For J = 2 To cLim \ I
AbundantNbrs(I * J) = True
Next J
End If
Next I
'Debug.Print Timer - StartTime
For I = 1 To UBound(AbundantNbrs) \ 2
If AbundantNbrs(I) Then
For J = I To cLim - I
If AbundantNbrs(J) Then
AbundantSums(I + J) = 0
End If
Next J
End If
Next I
Debug.Print Timer - StartTime & "," & Sum(AbundantSums)
End Sub
```

* Wikipedia indicates that the largest number that is not the sum of two abundant numbers is 20,000 and change.