Self-hatred

Project Euler Problem #23

This problem sucked. A benchmark for my solution is seemingly required for proper horn-tooting:

00:00:03.9170605

This problem, like Problem #19 threw me to the mental wolves. Keeping with the comparisons to #19, I also had to build up a supporting clade of methods to process the different elements of the problem. The core of the problem is simple:

An abundant number, n, is any integer whose proper divisors are >n. Take 12: It’s proper divisors are 1+2+3+4+6, which equal 16. List the sum of all numbers below 28123 that aren’t the product of two abundant numbers.

The first part of the solution requires me to determine all abundant numbers below 28123. A prime cannot be an abundant number (the proper divisors of a prime always equal 1), so I exclude them and test every other integer and put it into the list. There are 4995, which is just over 17% of all (of the) numbers.

Anyway. The bit that really led me in mental circle was this: If I did not pursue an efficient algorithm to solve this problem, then the processing time starts to approach several days. The most basic of approaches that doesn’t take an Age of Man to complete is this:

1. Find all abundant numbers between 1 and 28123.
2. Add them to a list, a.
3. Methodically add every item in a with every other item in a and add the result to list b.
4. For performance, prune b of duplicates.
5. Loop from 1 to n. Check i against list b. If it isn’t on the list (if it isn’t a product of two abundant numbers), add it to the running total.
6. Output the sum, and go blog.

Steps #3 through #6 were painful. My first approach was just compile a list of abundants and test subtract i from each of them. If the result was abundant, then I discarded it. While the simplest solution, it was the slowest, at twenty-odd minutes.

My second approach was the same as the first, but I made minor improvements in the algorithms to test for primality and abundantness.

My third approach involved World of Warcraft.

My fourth approach came courtesy of hints: I determined all possible sums of abundant numbers, and from there started reducing my run time. It was an ugly, groping, brute force process – a more savvy programmer would describe his workflow as “emulating natural Darwinism”.

using System;
using System.Linq;
using System.Collections.Generic;

public class TwentyThree
{
	static void Main()
	{
		int	  n = 28123;
		List<int> a = AbundantSums(n);
		int	  b = 0;

		for (int i = 0; i <= n; i++)
			if (!a.Contains(i))
				b += i;

		Console.WriteLine("\n{0}\n", b);
	}

	// List all possible sums of abundant numbers up to n using Abundant().
	static List<int> AbundantSums(int n)
	{
		List<int> a = ListA(n);
		List<int> b = new List<int>();

		for (int i = 0; i < a.Count; i++)
			for (int j = 0; j < a.Count; j++)
				b.Add(a[i] + a[j]);

		b = b.Distinct().ToList();

		return b;
	}

	// Generates list of abundant numbers up to n (inclusive).
	static List<int> ListA(int n)
	{
		List<int> b = new List<int>();

		for (int i = 1; i <= n; i++)
			if (!Prime(i))
				if (Abundant(i))
					b.Add(i);

		return b;
	}

	// Test for abundancy up to n.
	static bool Abundant(int n)
	{
		int  b = 0;
		bool c = false;

		for (int i = 1; i < = (n/2); i++)
			if (n % i == 0)
				b += i;

		if (b > n)
			c = true;

		return c;
	}

	// Test for primality up to n.
	static bool Prime(int n)
	{
		bool b = true;

		if (n % 2 == 0)
			b = false;

		for (int i = 3; i <= Math.Sqrt(n); i += 2)
				if (n % i == 0)
				{
					b = false;
					break;
				}

		return b;
	}
}

Tagged with: 23, abundant, c, csharp, mathematics, prime, problem, project euler, projecteuler, solution, twenty three

Categorised as: programming