I have coded the following solution for project euler.
Here is the code which I have written and it gives correct output as far as testing is done for the small numbers.
There is a function called as isAbundant(int...) they work fine,is boolean telling whether the number is abundant or no
And here is what Output I get.
BTW what part am I doing wrong, for smaller values i.e considering from 1to12, expected abundant number is 12 and the number which can be expressed as sum of 2 abundant numbers is 24 and this is abundant number so absum=24.
The total sum=1014(verified in excel as well as through program).
The subtraction must give me the sum of numbers which cannot be represented a sum of any two abundant numbers so answer is 1014-24=990 as the output, but this method doesnot produce correct answer for numbers upto 28123.
Kindly help me to locate where I have made the mistake.
I have hand verified the code as above but due to large calculations, this is not possible for large numbers.
The incorrect answer I am getting is
From what I'm reading in the linked problem is "As 12 is the smallest abundant number... the smallest number that can be written as the sum of two abundant numbers is 24." The problem is asking for the sum of all the positive integers which cannot be written as the sum of two abundant numbers. If the largest number was 33, then the the sum of all positive integers (1 + 2 + 3...+ 33) is 561. The abundant numbers from 1 - 33 are 12, 18, 20, 24, and 30. Of these, 24, 30, and 32 are the only numbers that are the sum of two abundant numbers (these total 86). This would make the sum of all positive integers between 1 and 33 that cannot be written as the sum of two abundant numbers 475.
Just apply that logic to all of the numbers between 1 and 20161.
BTW - They gave you the wrong maximum size, it's 20161, not 28123
Joined: Dec 29, 2009
@Emil and Luigi: Thanks a lot.
@Emil: Well I interpreted the sum of two numbers as in 1+1,1+2.. and so on so there is addition of the same numbers as well, i.e 24 can be expressed as 12+12 so int the case of sum of all numbers it should be 1+1,1+2... +33+33.
@Luigi:Is there any relation between abundant numbers and amicable pairs?
Yes I have solved the problem related to amicable pairs.
My main problem is how to take the sum is it 1+2+3+4+... or is it 1+1+1+2+1+3... +n+n type of sum.
The similarity between this one and problem 21 is that both require you to work out the proper divisors of the natural numbers... since I already had the code to do this from P21 I re-used it - you can probably cannibalise your P21 solution in the same way.
I don't think there's anything unclear about the problem wording.
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.
Just start by making a list of all the proper divisors of each number
then add the divisors together so that you have a list of abundant numbers
then check each number from 1 to 28,123 to see if it's the sum of two of these numbers from your list; if so, add to total
@Emil, I don't think the question is wrong. It's just saying that 28,123 is the smallest that can be proven analytically. You can find the actual smallest by writing a computer program like this one to do it by brute force.
@fred, snap, I'm also up to 53 (including 51!)... haven't done any in a while though because I've tried the TopCoder algorithm competitions and found the problems a bit more interesting - if you haven't tried them and you like Project Euler, they're definitely worth looking at.
Yep, I got 67. 97 and 112 are also pretty easy. I spent ages doing 317 and managed to get the right answer, although I still haven't worked out exactly how I did it.
Joined: Jul 09, 2010
@Luigi, I simply mentioned the 20161 based on the facts presented by Weisstein, Eric W. "Abundant Number." From MathWorld--A Wolfram Web Resource. http://mathworld.wolfram.com/AbundantNumber.html . And depending how this problem is solved, the results are the same when using 20161 and 28123, but the execution time is faster when using 20161. My initial attempt at this was to make a list of abundant numbers, then from that make a list of the sums of the abundant numbers, then use a loop to check each value from 1 to 28123 (and 20161) to see if it matched a sum of two abundant numbers. The processing time between using 20161 and 28123 was more than half. I'm sure this isn't the most efficient way of doing this, but it was Sunday after all
@Ashish - You could always try both types of summing just to see what happens. BTW, I've never seen the project euler site before...now I guess I'll have to join you and start working these problems out.
I'm not too worried about making the routine run faster when it takes less than a second to find the answer (0.56 seconds, to be exact)! If yours was taking a long time to run it's probably because there's something systematically wrong with your algorithm, and looking up a lower maximum isn't really the solution!
Joined: Dec 29, 2009
Thanks for all replies here.
Actually this question was not difficult to solve, just interpreted it wrongly and then as usual, messed it up.
People who are looking for speed here, is a small tip which might help to cut time into half.
Mathematically, multiple of any perfect number or abundant number will be abundant and can be expressed as sum of 2 abundant numbers.
Based on this fact, its very easy to derive that after 46 all even numbers can be expressed as sum of abundant numbers,
I wrote a small program to brute force for even numbers which can be expressed as sum of two abundant numbers,
So while adding we can just skip the even numbers after 46.
and found that its quiet intresting that my logic holds true.
*(Some how 76 is a different number it can be summed as 56+20, but not as multiple of 6.)
This should definitely give boost in speed.
I have not implemented this as yet, without this, speed of my algorithm is 0.9msec on 2.47GHz,4GB RAM,dell studio 15.
Post your timing if possible.