Skip to content

Instantly share code, notes, and snippets.

@colomon
Created January 12, 2014 02:22
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save colomon/8379810 to your computer and use it in GitHub Desktop.
Save colomon/8379810 to your computer and use it in GitHub Desktop.
Euler 23 solution, started with shlomif's code and went my own way with it.
# Adapted by Shlomi Fish.
#
# Solution for:
#
# http://projecteuler.net/problem=23
#
# 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.
#
use v6;
my $MAX = 28_123;
my @primes = (1..$MAX).grep(*.is-prime);
sub prime-factorization(Int $num is copy) {
my $factors = BagHash.new;
my $pi = 0;
while $num > 1 {
if $num %% @primes[$pi] {
$num div= @primes[$pi];
$factors{@primes[$pi]}++;
} else {
if $pi < @primes {
$pi++;
} else {
last;
}
}
}
$factors;
}
sub base-whatever-digits($num is copy, @bases) {
@bases.map: -> $base {
my $digit = $num % $base;
$num = ($num - $digit) div $base;
$digit;
}
}
sub divisors(Int $num) {
my $factors = prime-factorization($num);
my @factors = $factors.keys;
my @bases = @factors.map({ $factors{$_} + 1 });
(^(([*] @bases) - 1)).map: -> $i {
my @bwd = base-whatever-digits($i, @bases);
[*] @factors Z** @bwd;
}
}
sub sum-divisors(Int $num)
{
[+] divisors($num);
}
sub is-abundant(Int $num)
{
sum-divisors($num) > $num;
}
my @abundant = (1..$MAX).grep({ is-abundant($_) });
my $abundant-sum-numbers = (@abundant X+ @abundant).grep(* <= $MAX).Set;
say "Sum == ", [+] (1..$MAX).grep(* ∉ $abundant-sum-numbers);
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment