1. Post #1
    hOnK :o)
    i300's Avatar
    December 2009
    3,987 Posts


    http://projecteuler.net/

    [release]
    What is Project Euler?
    Project Euler (named after Leonhard Euler) is a website dedicated to a series of computational problems intended to be solved with computer programs. The project attracts adults and students interested in mathematics and computer programming. As of 24 January 2012, it includes 368 problems of varying difficulty, each solvable in less than a minute using an efficient algorithm on a modestly powered computer. A forum specific to each question may be viewed after the user has correctly answered the given question. Since its creation in 2001 by Colin Hughes, Project Euler has gained notability and popularity worldwide and currently has about two hundred thousand users worldwide.

    Where should I start?
    That depends on your background. In the Problems table you will be able to see how many people have solved each problem. As a general rule of thumb the more people that have solved it, the easier it is.

    I've written my program but should it take days to get to the answer?
    Absolutely not! Each problem has been designed according to a "one-minute rule", which means that although it may take several hours to design a successful algorithm with more difficult problems, an efficient implementation will allow a solution to be obtained on a modestly powered computer in less than one minute.

    Does it matter if it takes more than one minute to solve?
    Of course not, but that should provide the impetus to return to the problem and see how you can improve your approach. But remember that once you've solved a particular problem you will be able to access a thread relating to that problem and it is here that you may be able to pick some tips from others that have solved it.

    I solved it by using a search engine, does that matter?
    Making use of the internet to research a problem is to be encouraged as there could be hidden treasures of mathematics to be discovered beneath the surface of many of these problems. However, there is a fine line between researching ideas and using the answer you found on another website. If you photocopy a crossword solution then what have you achieved?

    I've checked my program ten times now and I keep getting told my answer is wrong! Have you made a mistake?
    With newly released problems it is quite possible that a small error may have slipped through the net, or maybe the wording is slightly ambiguous and the problem has not been explained as well as it could. However, when so many people have hit the target and one marksman misses ten times on the run, he/she can hardly shoot his/her own foot and conclude that because the gun is working properly the fault must lie in the target.

    Do you have any hints on solving problems?
    Read the details of the problem very carefully and make note of any example cases given. Experiment with pencil and paper to get a feel for the ideas behind the problem. If the ideas are new to you, use the internet or books to get some background; the problem should contain clues as to what to look-up. Try writing a program to generate for simple cases and check that your output agrees with the example cases; this will confirm you've understood the problem and are heading in the right direction. Based on this try to extrapolate to estimate the time it will take to get the final answer and if it's going to take significantly more than a minute rethink your strategy.

    What are the levels and awards all about?
    For every twenty-five problems you solve you will advance one level, which should help encourage you to make short term targets. The awards are earned for a variety of reasons and if you are wondering what you need to do to earn an award go to the Statistics page and you can see a complete list of current awards. In the case of both levels and awards you can click on the image on the Statistics page to see which members are currently at that level or who has earned a particular award. It is hoped that the levels and awards will provide a bit of extra fun as you solve the problems.

    How did Project Euler all start?
    Project Euler was started by Colin Hughes (a.k.a. euler) in October 2001 as a sub-section on mathschallenge.net. Who could have known how popular these types of problems would turn out to be? Since then the membership has continued to grow and Project Euler moved to its own domain in 2006.

    Who runs Project Euler?
    Ideas for new problems come from our own members and they are developed by a team of hard working and talented mathematicians and programmers. So to put it simply, it is the members that run Project Euler.
    [/release]

    Reply With Quote Edit / Delete Reply Mac United States Show Events Winner Winner x 3 (list)

  2. Post #2
    Moderator Illuminati
    Hexxeh's Avatar
    June 2006
    5,091 Posts
    Solved 23 so far. Writing all my solutions in C++ to practice for an internship interview.

    My solution to problem 23 takes around 5 seconds to run (VPS on 3ghz quad core with 4GB RAM), which is pretty poor, still trying to improve it.

    Edit: Got it down to 670ms, much better.

    Edit 2: Got it down to 318ms, gonna leave it at that and go back improve earlier ones with what I've learnt.

    All my solutions except 10 are under 500ms at this point, with many of them less than 10ms.
    Reply With Quote Edit / Delete Reply Mac United Kingdom Show Events Programming King Programming King x 6 (list)

  3. Post #3
    Gold Member
    pebkac's Avatar
    January 2009
    2,613 Posts
    Solved 23 so far. Writing all my solutions in C++ to practice for an internship interview.

    My solution to problem 23 takes around 5 seconds to run (VPS on 3ghz quad core with 4GB RAM), which is pretty poor, still trying to improve it.

    Edit: Got it down to 670ms, much better.
    I used to do these months ago but it seems I gave up at problem 23. At first I couldn't find a fast enough solution, then I did the but answer came out wrong.
    Gotta start solving again, it feels great to come up with answers to complex problems.

  4. Post #4
    Gold Member
    _Twitch_'s Avatar
    January 2005
    1,017 Posts
    I've completed 37 problems. It's great practice for any language.

  5. Post #5
    Gold Member

    May 2008
    1,986 Posts
    I only have 19 solved. I should get back into it.

  6. Post #6
    Gold Member
    Neo Kabuto's Avatar
    November 2008
    5,641 Posts
    Wow, I thought I had more, but it turns out I only submitted the first 11 problems... I know I did up to 20 something in class one day, but they were on my flash drive that died, so I'm going to have to redo them.

  7. Post #7

    August 2011
    192 Posts
    Code:
    main(_) {int x = ~(-_); do x+=_%3==0?_:_%5==0?_:0; while (++_^1000); printf("%d",x);}
    Wasn't this about obfuscation?
    Reply With Quote Edit / Delete Reply Windows 7 Switzerland Show Events Disagree Disagree x 1 (list)

  8. Post #8
    Gold Member
    Neo Kabuto's Avatar
    November 2008
    5,641 Posts
    Code:
    main(_) {int x = ~(-_); do x+=_%3==0?_:_%5==0?_:0; while (++_^1000); printf("%d",x);}
    Wasn't this about obfuscation?
    Maybe you're thinking of The International Obfuscated C Code Contest?

  9. Post #9

    August 2011
    192 Posts
    that's where I took most of my obfuscate ideas ;p

  10. Post #10
    Gold Member
    Neo Kabuto's Avatar
    November 2008
    5,641 Posts
    Ugh, some of these problems just take so much time to compute. I thought I'd try some of the rarely solved higher number problems, just to see if I could, and right now my program for 368 is running without showing any sign of converging at all after half an hour, so I'm going to assume solving it the obvious way would take a supercomputer.

  11. Post #11
    Moderator Illuminati
    Hexxeh's Avatar
    June 2006
    5,091 Posts
    None of them should take any longer than a minute to solve with an efficient algorithm. I've just finished number 28, and so far all my solutions take at most 500ms to run.
    Reply With Quote Edit / Delete Reply Mac United Kingdom Show Events Agree Agree x 2Disagree Disagree x 1 (list)

  12. Post #12
    Gold Member
    Neo Kabuto's Avatar
    November 2008
    5,641 Posts
    None of them should take any longer than a minute to solve with an efficient algorithm. I've just finished number 28, and so far all my solutions take at most 500ms to run.
    I'm talking about ones in the 300's. They start to seem crazier the further you go. 365 requires you to compute C(10^18,10^9), which it says has 9 billion digits, and then find the sum of the modulus of it and all combinations of prime numbers between 1000 and 5000 (IIRC, it's like 125 million combinations). I don't remember if there's a modular arithmetic trick for this, but it seems like the kind of problem that takes way more than a second.

  13. Post #13
    Moderator Illuminati
    Hexxeh's Avatar
    June 2006
    5,091 Posts
    I'm talking about ones in the 300's. They start to seem crazier the further you go. 365 requires you to compute C(10^18,10^9), which it says has 9 billion digits, and then find the sum of the modulus of it and all combinations of prime numbers between 1000 and 5000 (IIRC, it's like 125 million combinations). I don't remember if there's a modular arithmetic trick for this, but it seems like the kind of problem that takes way more than a second.
    Ah, I meant the earlier ones. Even the later ones should be possible to complete in under 60 seconds, though.

  14. Post #14
    Ask Rohan about rust keys!
    Bumrang's Avatar
    August 2011
    2,647 Posts
    I've only solved two
    Reply With Quote Edit / Delete Reply Windows 7 United States Show Events Programming King Programming King x 2 (list)

  15. Post #15
    Gold Member
    SamPerson123's Avatar
    September 2007
    3,524 Posts
    I've done around sixty of these. After a while they got really hard and I couldn't figure out an efficient way to do any of them.
    Reply With Quote Edit / Delete Reply Windows 7 United States Show Events Agree Agree x 1 (list)

  16. Post #16
    Zyx
    Guest 3855 is lost and can't find the park exit
    Zyx's Avatar
    February 2005
    2,826 Posts
    Problem 363 bezier curves: http://projecteuler.net/problem=363
    I already made that Well, the program to draw the curve anyway. No idea about the actual question.



    Maybe I should start doing some others, could be fun.
    Reply With Quote Edit / Delete Reply Windows 7 Show Events Funny Funny x 1Artistic Artistic x 1 (list)

  17. Post #17

    January 2012
    414 Posts
    I've done up to number 9, I did 3 today, I had previously done 6.

    How long do these take you to code, on average, if you had to guess?

  18. Post #18
    Plastical's Avatar
    August 2009
    583 Posts
    I've done about 40, takes me about half an hour on average to think about and code them.
    Reply With Quote Edit / Delete Reply Windows 7 United States Show Events Agree Agree x 1Winner Winner x 1 (list)

  19. Post #19
    ElTacoLad's Avatar
    July 2009
    1,400 Posts

    =(
    Reply With Quote Edit / Delete Reply Windows 7 Canada Show Events Agree Agree x 2Programming King Programming King x 2 (list)

  20. Post #20
    Person
    geel9's Avatar
    June 2008
    5,590 Posts

  21. Post #21

    February 2012
    8 Posts

    Fun. Solving in Java and Python, depending on the problem, sometimes both if I'm feeling pro :D

    EDIT: Dont' wanna spoil anyone's fun, but solved problem 5 with TI-84 BASIC:
    Code:
    :1→I
    :1→N
    :For(I,1,20)
    :lcm(N,I)→N
    :End
    :Disp N
    Reply With Quote Edit / Delete Reply Windows 7 United States Show Events Programming King Programming King x 1 (list)

  22. Post #22
    Gold Member
    atl101's Avatar
    March 2008
    761 Posts


    in Scala
    Reply With Quote Edit / Delete Reply Windows 7 United States Show Events Programming King Programming King x 1 (list)