aspose file tools*
The moose likes Java in General and the fly likes Project Euler : Problem 23 Big Moose Saloon
  Search | Java FAQ | Recent Topics | Flagged Topics | Hot Topics | Zero Replies
Register / Login
JavaRanch » Java Forums » Java » Java in General
Bookmark "Project Euler : Problem 23" Watch "Project Euler : Problem 23" New topic
Author

Project Euler : Problem 23

Ashish Schottky
Ranch Hand

Joined: Dec 29, 2009
Posts: 93
Here is the link for the http://projecteuler.net/index.php?section=problems&id=23

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
Thank you.
Luigi Plinge
Ranch Hand

Joined: Jan 06, 2011
Posts: 441

It's a bit hard to analyse someone else's code without a lot of effort, but if it's any use, here's how I solved it (not very elegant or optimised, but it works):

I can't remember the details, but it looks like I just changed my solution to P021 (Amicable numbers) a bit. So you might find it easier if you've done that one first.

Emil Jennings
Ranch Hand

Joined: Jul 09, 2010
Posts: 48
Ashish,

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
Ashish Schottky
Ranch Hand

Joined: Dec 29, 2009
Posts: 93
@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.

Thank you.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11314
    
  16

I interpreted the problem this way...

Find all the numbers less than 28123 that can be written as the sum of two abundant numbers. add up the others.

In other words, 1 CANNOT be written as the sum of two abundant numbers. It should be in your sum.

Same for 2,3,4...23.

However, since 24 CAN be written as the sum of two abundant numbers, it should NOT be included in your sum.

25 should be, etc.

since the sum of all numbers from 1 - 28,123 is 395,465,626, your answer should be less than this.


There are only two hard things in computer science: cache invalidation, naming things, and off-by-one errors
Ashish Schottky
Ranch Hand

Joined: Dec 29, 2009
Posts: 93
@fred:
Thanks.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11314
    
  16

no problem. FWIW, my entire solution is 72 lines (four are blank) - although there are no comments. I have solved all the Euler problems up through 53 (except 51), and also 67. They are great fun!!!
Luigi Plinge
Ranch Hand

Joined: Jan 06, 2011
Posts: 441

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.
fred rosenberger
lowercase baba
Bartender

Joined: Oct 02, 2003
Posts: 11314
    
  16

if you've done 18 efficiently, 67 is cake.
Luigi Plinge
Ranch Hand

Joined: Jan 06, 2011
Posts: 441

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.
Emil Jennings
Ranch Hand

Joined: Jul 09, 2010
Posts: 48
@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.
Luigi Plinge
Ranch Hand

Joined: Jan 06, 2011
Posts: 441

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!
Ashish Schottky
Ranch Hand

Joined: Dec 29, 2009
Posts: 93
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.
 
 
subject: Project Euler : Problem 23