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: 14173
    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: 109346
    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 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

    Search for:
    Jump to:  
    • Shoutbox
    • Shout Message


    test
    cron