GeekDad Puzzle of the Week Solution – Excessive Sums

Reading Time: 2 minutes

Last week’s puzzle as posted:

indecent_e_story
An excessive number of digits of e

In the field of Number Theory, you can classify a given counting number based on how it compares to the sum of its proper divisors.

If a number is exactly equal to the sum of its proper divisors, it is a Perfect Number. These are the least common, and are really rather sparse. The first few Perfect Numbers are 6, 28, 496, and 8128. That is, 6 can be divided by 1, 2, and 3, and 1 + 2 + 3 = 6. The 10th lowest perfect number has over 50 digits, and the 16th lowest over 1000 digits.

If a number is greater than the sum of its proper divisors, it is a Deficient Number. Most odd numbers are Deficient, as are all the prime numbers. The first few Deficient Numbers are 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 13, 14, 15, 16, and 17.

If a number is not greater than or equal to the sum of its proper divisors, it is an Excessive Number (also known as an Abundant Number.) The first few Excessive Numbers are 12, 18, 20, 24, 30, 36, 40, 42, 48, and 54. That is, the proper divisor of 24 for example are 1, 2, 3, 4, 6, 8, and 12, and 1 + 2 + 3 + 4 + 6 + 8 + 12 = 36 > 24.

The smallest number that can be represented as the sum of two Excessive Numbers is 24, as 12 is the lowest Excessive Number. Because of their relative density, most numbers higher than 50 can be written as the sum of exactly two Excessive Numbers.

This week’s GeekDad Puzzle of the Week is simple: How many positive integers less than 1,000,000 cannot be written as the sum of exactly two Excessive Numbers?

The most popular solution to this puzzle was obtained through brute force / complete evaluation testing. Using straightforward code, most solutions created a list of Excessive Numbers under 10,000,000, then looped through each number from 24 to 10,000,000 attempting to build that value from the set of Excessive Number that could possibly sum to it.

Some solutions searched around a bit on the web to find that every number over 20,161 could definitely be expressed as the sum of two Excessive Numbers and stopped their loops there (shaving off some 99.8% of the processing!)

In either case, congratulations to Goh Han for being the winner of this week’s GeekDad Puzzle of the Week. Their solution of 1456 was correct and was selected at random from the list of correct entries. Goh will soon be the owner of a $50 Gift Certificate from the selective sundry store known as ThinkGeek. Thanks to Goh and to everyone that submitted an answer to the week’s puzzle.

Happy Puzzling!

Get the Official GeekDad Books!