Calculating all two element sums of [a1 a2 a3 … an

问题:

Context: I'm working on Project Euler Problem 23 using Matlab in order to practice my barely existing programming skills.

My Problem:

Now I have a vector with roughly 6500 numbers (ranging from 12 to 28122) as elements and want to calculate all the two element sums. That is I only need one instance of every sum, so having calculated a1 + an it's not necessary to calculate an + a1.

Edit for clarification: This includes the sums a1+a1, a2+a2,..., an+an.

The problem is that this is much too slow.

Problem specific constraints:

It's a given that sums 28123 or over aren't necessary to calculate, since those can't be used to solve the problem further.

My approach:

AbundentNumberSumsRaw=[];
for i=1:3490
    AbundentNumberSumsRaw=[AbundentNumberSumRaw AbundentNumbers(i)+AbundentNumbers(i:end);
end

This works terribly :p

My Comments:

I'm pretty sure that incrementally increasing the vector AbundentNumbersRaw is bad coding, since that means memory usage will spike unnecessarily. I haven't done so, since a) I don't know what size vector to pre-allocate and b) I couldn't come up with a way to inject the sums into AbundentNumbersRaw in a orderly manner without using some ugly looking nested loops.

"for i=1:3490" is lower than the numbers of elements simply because I checked and saw that all the resulting sums for numbers whose index are above 3490 would be too large for me to use anyway.

I'm pretty sure my main issue is that the program need to do a lot of incremental increases of the vector AbundentNumbersRaw.

Any and all help and suggestions would be much appreciated :)

Cheers

Rasmus

回答1:

Suppose

a = 28110*rand(6500,1)+12;

then

sums = [
 a(1) + a(1:end)
 a(2) + a(2:end)
 ... 
];

is the calculation you're after.

You also state that sums whose value goes over 28123 should be discarded.

This can be generalized like so:

% Compute all 2-element sums without repetitions
C = arrayfun(@(x) a(x)+a(x:end), 1:numel(a), 'uniformoutput', false);
C = cat(1, C{:});

% discard sums exceeding threshold
C(C>28123) = [];

or using a loop

% Compute all 2-element sums without repetitions
E = cell(numel(a),1);
for ii = 1:numel(a)
    E{ii} = a(ii)+a(ii:end); end
E = cat(1, E{:});

% discard sums exceeding threshold
E(E>28123) = [];

Simple testing shows that arrayfun is somewhat faster than the loop, so I'd go for the arrayfun option.

回答2:

As your primary problem is to find out, which integers in a given set can be written as the sum of two integers of a different set, I'd choose a different approach:

AbundantNumbers = 1:6500; % replace with the list you generated somewhere else
maxInteger = 28122;
AbundantNumberSum(1:maxInteger) = true; % logical array

for i = 1:length(AbundantNumbers)
  sumIndices = AbundantNumbers(i) + AbundantNumbers;
  AbundantNumberSum(sumIndices(sumIndices <= maxInteger)) = false;
end

Unfortunantely, this is not an answer to your question but to your problem ;-) For the MatLab way to solve your original question, see the elegant answer of Rody Oldenhuis.

回答3:

My approach would be the following:

v = 1:3490;   % your vector here
s = length(v);
result = zeros(s);  % preallocate memory

for m = 1:s
     result(m,m:end) = v(m)+v(m:end);    
end

You will get a matrix of 3490 x 3490 elements and more than half of them 0.