A fair chunk of my work involves PowerShell Scripting and as a means to expand my general programing knowledge as well as my PowerShell abilities I had taken on the Project Euler question #23. It states:

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 n is called deficient if the sum of its proper divisors is less than n and it is called abundant if this sum exceeds n.

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.

Fortunately I was able to create a solution to this very tricky puzzle. The abundant numbers calculated quickly however I ran out of steam when it came to optimizing the calculations of all sums for the abundant numbers. That portion takes the large majority of the computing. Referencing my work against others it seems very similar (I had also tried two different approaches, such as looping 1 to 28123, then finding the complimentary number and matching against the known abundant numbers) and this is as quick as I can get to go… Perhaps a PowerShell shortcoming?

Spoiler Alert

The code I used is below which runs in under two minutes on my PC.

$maxNum = 28123;

$numDic = @{}
for($i = 1; $i -le $maxNum; $i++){
    $numDic[$i] = 0;
}
for($i = 1; $i -le $maxNum; $i++){
   $j = $i;
    while($j -le $maxNum){
        if($j -ne $i){
            $numDic[$j] += $i
        }
        $j += $i;
   }
}

$totalNumFound = 0;
$abundants = @();
for($i = 1; $i -le $maxNum; $i++){
    if($numDic[$i] -gt $i){
        #$i
        $totalNumFound++
        $abundants+=$i;
    }
}

$additions = new-object bool[] 56246
for($i=0; $i -lt $abundants.Count; $i++){
    for($j=$i; $j -lt $abundants.Count -and $abundants[$i] + $abundants[$j] -le 28123 ; $j++){
        $additions[$abundants[$i] + $abundants[$j]] = $true;
    }
}

$answer = 0;
for($i=0;$i -le $maxNum; $i++){
    if(!($additions[$i])){
        $answer += $i;
    }
}

$answer

1 Comments

Pingbacks