Elegant Programming

I’ve been quiet lately. That’s because I have a new addiction, an addiction to number problems and elegant programming solutions to them. Behold Project Euler. A suite of nearly 200 numeric problems suitable for solving via programs. So far I’ve solved 19 of them, and I’ll probably keep banging away at them in every spare moment for some time to come.

Here’s an example, from problem 21:

Let d(n) be defined as the sum of proper divisors of n (numbers less than n which divide evenly into n).

If d(a) = b and d(b) = a, where a b, then a and b are an amicable pair and each of a and b are called amicable numbers.

For example, the proper divisors of 220 are 1, 2, 4, 5, 10, 11, 20, 22, 44, 55 and 110; therefore d(220) = 284. The proper divisors of 284 are 1, 2, 4, 71 and 142; so d(284) = 220.

Evaluate the sum of all the amicable numbers under 10000.

Here’s the VB .NET source code for my solution:

Public Class p021
    Private Shared amicable As List(Of Integer)

    Public Shared Function Run() As Long
        Dim amicable As New List(Of Long)

        For i As Long = 1 To 9999
            Dim a() As Long = GetAmicables(i)
            If a(0) <> a(1) Then
                If Not amicable.Contains(a(0)) Then amicable.Add(a(0))
                If Not amicable.Contains(a(1)) Then amicable.Add(a(1))
            End If
        Next

        Dim sum As Long = 0
        For Each s As Long In amicable
            sum += s
        Next
        Return sum
    End Function

    Private Shared Function GetAmicables(ByVal i As Long) As Long()
        Dim res() As Long = {0, 0}

        Dim a As Long = SumFactors(i)
        Dim b As Long = SumFactors(a)

        If b = i Then
            res(0) = a
            res(1) = b
        End If

        Return res
    End Function

    Private Shared Function SumFactors(ByVal i As Long) As Long
        Dim fi As New List(Of Long)(Factors(i))
        fi.Sort()
        fi.Remove(i)
        Dim sum As Long
        For Each f As Long In fi
            sum += f
        Next

        Return sum
    End Function

    Private Shared Function Factors(ByVal product As Long) As Long()
        Dim f As New List(Of Long)

        Dim limit As Long = Math.Sqrt(product)
        Dim i As Long = 1
        Do While (i <= limit)
            If product Mod i = 0 Then
                f.Add(i)
                Dim j As Long = product / i
                If j <> i Then f.Add(j)
            End If
            i += 1
        Loop

        Return f.ToArray
    End Function
End Class

The answer to this problem is 31626.

I hope you have as much fun with this as I have. Sign up and check it out!