Login    Forum    Register    Search    FAQ

Board index » HELP AND ADVICE » G33K'S CORNER




Post new topic Reply to topic  [ 16 posts ]  Go to page 1, 2  Next
Author Message
 Post subject: Divisors problem :P
 Post Posted: Sun Jan 11, 2009 6:42 pm 
Offline
I'm ghey 4 teh Hoff!
User avatar

Joined: Wed Sep 21, 2005 5:18 pm
Posts: 4142
So there was I, tinkin.

And I thought maybe others would like to think a bit too :P

It's from projecteuler.net. It's one of the "easier" ones, it's not actually about writing something that works. That's not tough. It's about writing something that works and solves it within a reasonable amount of time (preferably seconds, not days!).

Quote:
The sequence of triangle numbers is generated by adding the natural numbers. So the 7^(th) triangle number would be 1 + 2 + 3 + 4 + 5 + 6 + 7 = 28. The first ten terms would be:

1, 3, 6, 10, 15, 21, 28, 36, 45, 55, ...

Let us list the factors of the first seven triangle numbers:

1: 1
3: 1,3
6: 1,2,3,6
10: 1,2,5,10
15: 1,3,5,15
21: 1,3,7,21
28: 1,2,4,7,14,28

We can see that 28 is the first triangle number to have over five divisors.

What is the value of the first triangle number to have over five hundred divisors?


No, the actual problem isn't that hard per say, you can simply brute force it to find the number. But brute force = bad.

So, trying to come up with an elegant method of doing this, so it solves within the shortest time possible. A starter...

Firstly we have to work all the "triangle numbers" or whatever. Just do a never-ending loop...
Code:
int sum = 0;
int i = 1;
while(true){

}

Sum? That'll just be a simple sum to get the "triangle" number.
i is representing the ith number ;)
so inside something along the lines of
Code:
sum += i;

to keep track of our "triangle number", course, we need to increment i. Completing it a bit...

Code:
int sum = 0;
int i = 1;
while(true){
sum += i;
if(divisors(sum) >= 500){
  System.out.println(sum);
  break;
}
i++;
}


The if statement is merely calling a method "divisors" which will return the number of divisors that the number has. If it's more than 500, print it and exit.
So what are some solutions for it? Elegance over brute force preferred :P

The code I wrote took 1.79 seconds to find the answer, however someone else has solved it with a different solution in 94ms (mine is 1719ms!)

Give it a go, how long did it take and what was the answer and your code? :P

Fastest seen on the actual problem is in the solution paper, which is as follows:
Quote:
Written in assembly and
almost fully optimized, it runs in less than 1 millisec on a P4-1500. It should easily run in less
than 10 millisec when written in most modern compiled languages.

Bugger!


Last edited by Chips=GCHQ= on Sun Jan 11, 2009 7:09 pm, edited 1 time in total.

Top 
 Profile  
 
 Post subject: Re: Divisors problem :P
 Post Posted: Sun Jan 11, 2009 7:09 pm 
Offline
it is I! Diabetes man!
User avatar

Joined: Wed Mar 03, 2004 1:15 pm
Posts: 14174
Location: anywhere but nowhere
69

_________________
Image



Image
Went to a zoo, they only had one animal there, a dog............. It was a shitzu....



I’z leakin… bring amberlamps


Top 
 Profile  
 
 Post subject: Re: Divisors problem :P
 Post Posted: Sun Jan 11, 2009 9:06 pm 
Offline
Decidedly uninterested
User avatar

Joined: Thu Mar 18, 2004 11:10 pm
Posts: 10184
Location: I watch you while you sleep
That's your age Geoff :o7:

_________________
Image
The Pancreas of S.T.F.U. | Never take life too seriously - nobody gets out alive anyway.
Disco_jim: um..... I have no excuse. | Chips: Thank the Beef | Rev Dr: Beef, I think i wee'd a little


Top 
 Profile  
 
 Post subject: Re: Divisors problem :P
 Post Posted: Mon Jan 12, 2009 10:37 pm 
Offline
Humping a Super Model
User avatar

Joined: Sun May 16, 2004 4:17 pm
Posts: 3762
Location: NOT in IRAN!!!!!!!!!!!
Answers on the back of a postcard to the usual address...........








Anyone have a feckin clue wtf he was on about there?

_________________
Image
LINUX : If it was any good, they'd charge for it.
I want to die peacefully in my sleep just like my Grandad, not kicking and screaming like his passengers...


Top 
 Profile  
 
 Post subject: Re: Divisors problem :P
 Post Posted: Tue Jan 13, 2009 1:20 am 
Offline
Comin' outta Gallifrey
User avatar

Joined: Mon Aug 01, 2005 9:44 pm
Posts: 7821
Location: banging with enamor
I'm working through, done the first 5....apparently there's some trick with prime factors...I'll have a go when I get there.

_________________
“There are some people in this world who don’t love their fellow man, and I HATE people like that!”


Top 
 Profile  
 
 Post subject: Re: Divisors problem :P
 Post Posted: Tue Jan 13, 2009 2:05 am 
Offline
Apprentice bacon herder
User avatar

Joined: Mon Jan 10, 2005 5:46 pm
Posts: 3346
Location: southampton
EkO=GCHQ= wrote:
Anyone have a feckin clue wtf he was on about there?


elbow=GCHQ= wrote:
I'm working through, done the first 5....apparently there's some trick with prime factors...I'll have a go when I get there.


thats a no :grin:

_________________
Image
Games: DC, CSS, BF2, Insurgency, Cod2, Cod4, Cod5, BFBC2, Surpreme Commander, Hidden Source, bfbc2/vietnam, Cod black ops, need for speeds (underground 1 and 2, prostreet, hot pursuit, most wanted), juiced 1 and 2, im sure theres more...


Top 
 Profile  
 
 Post subject: Re: Divisors problem :P
 Post Posted: Tue Jan 13, 2009 6:10 pm 
Offline
Comin' outta Gallifrey
User avatar

Joined: Mon Aug 01, 2005 9:44 pm
Posts: 7821
Location: banging with enamor
What language are you using chips?

in p*thon i can do it in 1.38 seconds (hey, it's an interpreted language) by working out prime factors. .19 seconds is generating a list of primes up to 65500, which is probably a bit exessive.

In p*thon the brute force method that chips is using takes minutes to run, so I'm not sure what our comparison is.

my code is pretty much

Code:
o = 0
i = 1               
t = 1
while o < 500:
    t+=1
    i+=t
    o = numfactors(prime_factor(i, plist))


prime_factor will return a dictionary of prime factors along with their exponents, ie

12 is made from 2^2 and 3^1, so {2:2, 3:1}

and numfactors will calcualte the number of factors based on the exponents (have a look on wikipedia). plist is my list of primes - I should be able to not pass it I'm sure, which should save time, but I cba to fix it now

[edit] Just seen the solution - might try implementing that too, see how much faster it goes

_________________
“There are some people in this world who don’t love their fellow man, and I HATE people like that!”


Top 
 Profile  
 
 Post subject: Re: Divisors problem :P
 Post Posted: Tue Jan 13, 2009 6:37 pm 
Offline
Comin' outta Gallifrey
User avatar

Joined: Mon Aug 01, 2005 9:44 pm
Posts: 7821
Location: banging with enamor
changing it actually made it worse - which means that there's something pretty shitty in my code :) I think the numfactors I can include optimise by just having a running total of exponents in prime_factor

[edit] nope, turns out the dictionary is most efficient!

_________________
“There are some people in this world who don’t love their fellow man, and I HATE people like that!”


Top 
 Profile  
 
 Post subject: Re: Divisors problem :P
 Post Posted: Tue Jan 13, 2009 9:32 pm 
Offline
that was a stupid comment btw
User avatar

Joined: Wed Mar 03, 2004 12:40 pm
Posts: 109344
Location: manchester
im moving atm but ill take a look more at this in a week

_________________
Image
Image


Top 
 Profile  
 
 Post subject: Re: Divisors problem :P
 Post Posted: Tue Jan 13, 2009 11:18 pm 
Offline
I'm ghey 4 teh Hoff!
User avatar

Joined: Wed Sep 21, 2005 5:18 pm
Posts: 4142
nice :D

Am using Java ;) Currently completed up to problem 22*

For the Divisors problem my brute force was the following method:
Code:
public static int divisors(int sum){
        int divisors = 2;
        for(int i = 2; i <= Math.sqrt(sum) + 1 ; i++){
            if(sum % i == 0){
                divisors += 2;
            }
        }
        return divisors;
    }


However, remembering some optimisations I made during my summer placement whilst writing code - I replaced the for loops calculation with a reference to the actual calculation value.

Code:
public static int divisors(int sum){
        int divisors = 2;
        double root = Math.sqrt(sum);
        for(int i = 2; i <= root ; i++){
            if(sum % i == 0){
                divisors += 2;
            }
        }
        return divisors;
    }

Suddenly you are cutting out Math.sqrt(sum) amounts of square root calculations per method call. This, in fact, shaves over 1.2 seconds off the execution time - bringing it down to
Quote:
run-single:
It is 76576500
Time: 547ms


Simple optimisation, often overlooked :D


For the primes calculations problems I basically used a sieve of Eratosthenes (I didn't know at the time, I just happened to write it :D) - in my own implementation :o
Basically, apart from the number 1, a prime was any number not divisable by any other prime. Once a prime is found, it's added to a collection of primes for numbers to be tested against...
So 2 isn't divisible by any prime as there are none at the moment. Add to collection. 3 isn't divisible by 2, so add to collection. 4 is, so ignore, 5 isn't divisible by 2 or 3... so add to collection. Lather rinse and repeat.

I don't think my sieve is 100% correct though as it took 5 mins to find all the primes this way, and then sum them up (for the problem of summing all primes below 2 million)!

* A few confessions:

1) I haven't done number 18 yet. Reason why is simply not knowing my algorithms well enough and (shamefully) the tree's implemented in Java collections :oops:

Well, I know the theory of the algorithms, but have never written them - and simple breadth first, or even depth first, is not an "elegant" solution :D

2) Number 15, finding the paths in a 20x20 grid. I couldn't actually come up with an algorithm to solve this whatsoever (by myself) so I had to look up with regards to algorithms and it basically gave me the answer :evil:
So I didn't really solve that one, I cheated :oops:

Then again, not doing this for any other reason than I like problems (despite being, as said, crap at maths) and I wanted to practice/learn algorithms and their implementations :)
Later on I assume I'll be referring to textbooks repeatedly, however, at the moment I can get by with just making them up on the spot (problem 21 took 3 minutes from start to finish, I found it to be fairly trivial... but 23 I'm not even sure I understand yet :oops:).


Last edited by Chips=GCHQ= on Tue Jan 13, 2009 11:42 pm, edited 3 times in total.

Top 
 Profile  
 
 Post subject: Re: Divisors problem :P
 Post Posted: Tue Jan 13, 2009 11:29 pm 
Offline
Pure sex on legs

Joined: Wed Feb 08, 2006 3:55 am
Posts: 687
Location: UK
I think my head exploded :/

_________________
Image


Top 
 Profile  
 
 Post subject: Re: Divisors problem :P
 Post Posted: Wed Jan 14, 2009 4:40 pm 
Offline
Bow down to the master
User avatar

Joined: Mon Oct 01, 2007 6:38 pm
Posts: 2499
Location: Between .local and dev:null :D
Ernie=GCHQ= wrote:
I think my head exploded :/

At least the contents of ur head released :shock: Mine still swish around in there :shock: (after reading that, that is ;))

_________________
Image
My work blog | My Flickr | Complaints form | Get Image


Top 
 Profile  
 
 Post subject: Re: Divisors problem :P
 Post Posted: Sun Jan 18, 2009 1:13 am 
Offline
Comin' outta Gallifrey
User avatar

Joined: Mon Aug 01, 2005 9:44 pm
Posts: 7821
Location: banging with enamor
wrt to 18, apparently you need to read
http://en.wikipedia.org/wiki/Dynamic_programming
to be able to approach it...

I'm running out of ones that are interesting and doable - the ones like find the number of xs under N are just tedious...problem 102 was fun though :D

_________________
“There are some people in this world who don’t love their fellow man, and I HATE people like that!”


Top 
 Profile  
 
 Post subject: Re: Divisors problem :P
 Post Posted: Sun Jan 18, 2009 1:45 am 
Offline
Bow down to the master
User avatar

Joined: Mon Oct 01, 2007 6:38 pm
Posts: 2499
Location: Between .local and dev:null :D
I feel like I'm in MENZA or something :shock:
You know, that feeling.. when you realise...... ur waaaaaaaaaaaaaaaay out of your depth? :scratch: :pale:

_________________
Image
My work blog | My Flickr | Complaints form | Get Image


Top 
 Profile  
 
 Post subject: Re: Divisors problem :P
 Post Posted: Sun Jan 18, 2009 11:00 am 
Offline
Decidedly uninterested
User avatar

Joined: Thu Mar 18, 2004 11:10 pm
Posts: 10184
Location: I watch you while you sleep
TheMacOne=GCHQ= wrote:
I feel like I'm in MENZA or something :shock:

That would be MENSA genius :roll: :lol:

_________________
Image
The Pancreas of S.T.F.U. | Never take life too seriously - nobody gets out alive anyway.
Disco_jim: um..... I have no excuse. | Chips: Thank the Beef | Rev Dr: Beef, I think i wee'd a little


Top 
 Profile  
 
Display posts from previous:  Sort by  
 
Post new topic Reply to topic  [ 16 posts ]  Go to page 1, 2  Next

Board index » HELP AND ADVICE » G33K'S CORNER


Who is online

Users browsing this forum: No registered users and 11 guests

 
 

 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum

Search for:
Jump to:  
  • Shoutbox
  • Shout Message


test
cron