//
// Euler 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.
// """
//
// This SETL program was created by Hakan Kjellerstrand (hakank@bonetmail.com).
// See also my SETL page: http://www.hakank.org/setl/
sum_divisors := procedure(n) {
s := 0;
for (i in [1..round(n/2)]) {
if (n % i == 0) {
s += i;
}
}
return(s);
};
// Faster version
sum_divisors2 := procedure(n) {
d := floor(sqrt(n));
sum := 1;
for (i in [2..d]) {
if (n % i == 0) {
sum := sum+i;
if (i != n \ i) {
sum += n \ i;
}
}
}
return sum;
};
//
problem23 := procedure() {
print("problem23");
n := 28123;
t1 := now();
abundant := [a : a in [1.. n] | sum_divisors2(a) > a];
hash := {};
for (a in abundant) {
for (b in abundant) {
if (a >= b && a+b <= n) {
hash[a+b] := 1;
} else {
break;
}
}
}
print(+/[a : a in [1..n] | hash[a] == om]);
print("It took $(now()-t1)/1000.0$s");
};
//
// Using vector for the sums
//
problem23b := procedure() {
print("problem23b");
t1 := now();
n := 28123;
abundant := [a : a in [1.. n] | sum_divisors2(a) > a];
vec := [0 : i in [1..n]];
for (a in abundant) {
for (b in abundant) {
if (a >= b && a+b <= n) {
vec[a+b] := 1;
} else {
break;
}
}
}
print(+/[a : a in [1..n] | vec[a] != 1]);
print("It took $(now()-t1)/1000.0$s");
};
//
// Using vector for abundant
//
problem23c := procedure() {
print("problem23c");
t1 := now();
n := 28123;
abundant := [a : a in [1.. n] | sum_divisors2(a) > a];
vec := [0 : i in [1..n]];
alen := #abundant;
for (i in [1..alen]) {
for (j in [i..alen]) {
c := abundant[i]+abundant[j];
if (c <= n) {
vec[c] := 1;
}
}
}
print(+/[a : a in [1..n] | vec[a] != 1]);
print("It took $(now()-t1)/1000.0$s");
};
// problem23();
problem23b();
// problem23c();