Archives


« Prev:

» Next:


Project Euler problem 12

February 20th, 2009 at 1:15 pm

I’ve got hooked to Project Euler this week, after hearing good stuff about it for a long time. I’ve already solved the first 16 problems, and it has been lots of fun so far.

Most of the problems I’ve encountered are trivial, and can be either solved by a simple brute-force approach or by using a known mathematical formula. Besides, Python’s built-in and efficient arbitrary-precision arithmetic makes many problems very trivial (such as 16 – the sum of digits in the number 2^{1000}).

The first problem that gave me some hard time was 12 – I just couldn’t brute-force it. Eventually, a couple of insights led me to the solution, which was very satisfying.

Below are some tips for solving it, though I don’t provide the full solution.

The most important insight is that you don’t have to enumerate all the numbers up to sqrt{N} and check if they divide it, counting those that do.

A faster method is to factorize N, and use the divisor function to compute the amount of divisors.

If the factorization of N is:

p_{1}^{e_{1}}p_{2}^{e_{2}}…p_{k}^{e_{k}}

Where p_{i} are the prime factors and e_{i} are their exponents, then the total amount of divisors of N is:

(e_{1}+1)(e_{2}+1)…(e_{k}+1)

Even with the crappy factorizing routine I used, this produces the amount of divisors for a given number much faster than the naive method.

The second key insight (without which it would also take too long to solve this problem) is that since we’re looking for the smallest number with 500 divisors, it will definitely have small prime factors. So I just threw away anything that didn’t divide by 2, 3, 5 and so on. After a few experimentations, I had an algorithm that finds the desired number in about 4 seconds.

Related posts:

  1. Project Euler problem 69
  2. Project Euler problem 43
  3. Project Euler problem 26
  4. Project Euler problem 104
  5. Project Euler problem 66 and continued fractions

This entry was posted on Friday, February 20th, 2009 at 13:15 and is filed under Project Euler. You can follow any responses to this entry through the RSS 2.0 feed. Both comments and pings are currently closed.

5 Responses to “Project Euler problem 12”

  1. JOEYNo Gravatar Says:
    February 20th, 2009 at 20:55

    I’ve been enjoying project euler occasionally as well.

    p25 and p26 were good, for 25 I ported the logarithmic complexity Fibonacci routine from SICP exercise 1.19 (even though it makes the program slower), and 26 is well suited to python.

  2. ripper234No Gravatar Says:
    February 21st, 2009 at 13:26

    I really don’t understand what’s the problem here – I brute forced it in C#, counting all factors till sqrt(n) and doubling by 2. It takes 2 seconds to run, in Debug mode.

    So far I’ve done 1-16, 20, 25 (I’m going through them on the order of difficulty, not ID). Funny that the last problem I tackled, #15, is the one I recently blogged about regardless of Project Euler.

    I’m still waiting to reach the more difficult problems. Thanks for the pointer Eli.

  3. elibenNo Gravatar Says:
    February 21st, 2009 at 18:02

    @Ron,

    I wonder why it didn’t work out for me then, hmm… Never mind, it’s a good thing – I had more fun finding a shorter way :-)

    What’s your username on Project Euler? Mine’s eliben.

  4. ripper234No Gravatar Says:
    February 21st, 2009 at 19:13

    ripper234 :0

  5. Benjamin SergeantNo Gravatar Says:
    February 23rd, 2009 at 07:28

    My brute force in C is a real stupid one, and takes 30 minutes !
    (I’m bsergean there).

    Coding on Project Euler is really cool, you can leave it for a long time and come back, you will still enjoy it. And it really feel good to solve a new problem :)

    - Benjamin