project euler 23 MATLAB

waywardEevee

I'm slowly working my way though problem 23 in project Euler but I;ve run into a snag. Problem #23 involves trying to find the sum of all numbers that cannot be creat by two abundant numbers.

First here's my code:

function [divisors] = SOEdivisors(num)
%SOEDIVISORS This function finds the proper divisors of a number using the sieve
%of eratosthenes


%check for primality
if isprime(num) == 1
    divisors = [1];


%if not prime find divisors
else
    divisors = [0 2:num/2]; %hard code a zero at one.

    for i = 2:num/2
        if divisors(i) %if divisors i ~= 0

            %if the remainder is not zero it is not a divisor
            if rem(num, divisors(i)) ~= 0

                %remove that number and all its multiples from the list
                divisors(i:i:fix(num/2)) = 0;
            end
        end
    end

    %add 1 back and remove all zeros
    divisors(1) = 1;
    divisors = divisors(divisors ~= 0);
end
end

This function finds abundant numbers

function [abundantvecfinal] = abundantnum(limitnum)
%ABUNDANTNUM creates a vector of abundant numbers up to a limit.


abundantvec = [];

%abundant number count
count = 1;

%test for abundance
for i = 1:limitnum

    %find divisors
    divisors = SOEdivisors(i);

    %if sum of divisors is greater than number it is abundant, add it to
    %vector
    if i < sum(divisors)
        abundantvec(count) = i;
        count = count + 1;
    end


end

abundantvecfinal = abundantvec;
end

And this is the main script

%This finds the sum of all numbers that cannot be written as the sum of two
%abundant numbers and under 28123

%get abundant numbers
abundant = abundantnum(28153);

%total non abundant numbers
total = 0;

%sums
sums = [];

%count moves through the newsums vector allowing for a new space for each
%new sum
count = 1;

%get complete list of possible sums under using abundant numbers under
%28123 then store them in a vector
for i = 1:length(abundant)
    for x = 1:length(abundant)

        %make sure it is not the same number being added to itself
        if i ~= x
            sums(count) = abundant(i) + abundant(x);
            count = count + 1;
        end
    end
end

%setdiff function compares two vectors and removes all similar elements
total = sum(setdiff(1:28153, sums));


disp(total)

The first problem is it gives me the wrong answer. I know that I'm getting the correct proper divisors and the correct abundant numbers so the problem probably lies in the main script. And it seems as though it almost certainly lies in the creation of the abundant sums. I was hoping someone might be able to find an error I havent been able to.

Beyond that, the code is slow due to the multiple for loops, so I'm also looking for ways to do problems like this more efficiently.

Thanks!

Zook

Well, I don't have enough reputation to just comment. Why are you ruling out adding the same number to itself? The problem statement gives the example 12+12=24.

I also don't see a reason that x should ever be less than i. You don't need to sum the same two numbers twice.

Collected from the Internet

Please contact [email protected] to delete if infringement.

edited at
0

Comments

0 comments
Login to comment

Related