

Gamecommunity =GCHQ= 

Author 
Message 
Chips=GCHQ=

Post subject: Divisors problem :P Posted: Sun Jan 11, 2009 6:42 pm 


I'm ghey 4 teh Hoff! 

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 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 neverending 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 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? 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 P41500. 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.





nicey=GCHQ=

Post subject: Re: Divisors problem :P Posted: Sun Jan 11, 2009 7:09 pm 


it is I! Diabetes man! 

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

69
_________________ Went to a zoo, they only had one animal there, a dog............. It was a shitzu.... I’z leakin… bring amberlamps





LeBeourfCurtaine

Post subject: Re: Divisors problem :P Posted: Sun Jan 11, 2009 9:06 pm 


Decidedly uninterested 

Joined: Thu Mar 18, 2004 11:10 pm Posts: 10184 Location: I watch you while you sleep

That's your age Geoff
_________________ 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





EkO=GCHQ=

Post subject: Re: Divisors problem :P Posted: Mon Jan 12, 2009 10:37 pm 


Humping a Super Model 

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?
_________________ 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...





elbow=GCHQ=

Post subject: Re: Divisors problem :P Posted: Tue Jan 13, 2009 1:20 am 


Comin' outta Gallifrey 

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!”





maddogeasytarget=GCHQ=

Post subject: Re: Divisors problem :P Posted: Tue Jan 13, 2009 2:05 am 


Apprentice bacon herder 

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
_________________ 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...





elbow=GCHQ=

Post subject: Re: Divisors problem :P Posted: Tue Jan 13, 2009 6:10 pm 


Comin' outta Gallifrey 

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!”





elbow=GCHQ=

Post subject: Re: Divisors problem :P Posted: Tue Jan 13, 2009 6:37 pm 


Comin' outta Gallifrey 

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!”





happyslappy

Post subject: Re: Divisors problem :P Posted: Tue Jan 13, 2009 9:32 pm 


that was a stupid comment btw 

Joined: Wed Mar 03, 2004 12:40 pm Posts: 109346 Location: manchester

im moving atm but ill take a look more at this in a week
_________________





Chips=GCHQ=

Post subject: Re: Divisors problem :P Posted: Tue Jan 13, 2009 11:18 pm 


I'm ghey 4 teh Hoff! 

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

nice 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: runsingle: It is 76576500 Time: 547ms
Simple optimisation, often overlooked 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 )  in my own implementation 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 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 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 So I didn't really solve that one, I cheated 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 ).
Last edited by Chips=GCHQ= on Tue Jan 13, 2009 11:42 pm, edited 3 times in total.





Ernie

Post subject: Re: Divisors problem :P Posted: Tue Jan 13, 2009 11:29 pm 


Pure sex on legs 
Joined: Wed Feb 08, 2006 3:55 am Posts: 687 Location: UK

I think my head exploded :/
_________________





TheMacOne=GCHQ=

Post subject: Re: Divisors problem :P Posted: Wed Jan 14, 2009 4:40 pm 


Bow down to the master 

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 Mine still swish around in there (after reading that, that is )





elbow=GCHQ=

Post subject: Re: Divisors problem :P Posted: Sun Jan 18, 2009 1:13 am 


Comin' outta Gallifrey 

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_programmingto 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
_________________ “There are some people in this world who don’t love their fellow man, and I HATE people like that!”





TheMacOne=GCHQ=

Post subject: Re: Divisors problem :P Posted: Sun Jan 18, 2009 1:45 am 


Bow down to the master 

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 You know, that feeling.. when you realise...... ur waaaaaaaaaaaaaaaay out of your depth?





LeBeourfCurtaine

Post subject: Re: Divisors problem :P Posted: Sun Jan 18, 2009 11:00 am 


Decidedly uninterested 

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 That would be MENSA genius
_________________ 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






Users browsing this forum: No registered users and 3 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

test

