Skip to main content

Project Euler Problem #12

"""
Project Euler Problem #12
==========================

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?
"""

limit = 100000
data=[0] * limit
for i in xrange(1,int(limit/2+1)):
    data[i::i] = [ x+1 for x in data[i::i]]

def find():
    s = 1
    while True:
        if s % 2 == 0:
            total = data[s//2] * data[s+1]
        else:
            total = data[s]*data[(s+1)//2]
        if total > 500:
            print s*(s+1)/2
            return
        s+=1
find()

====================
running time:

$ time python 012.py 
76576500

real 0m0.119s
user 0m0.113s
sys 0m0.006s

Comments

Post a Comment

Popular posts from this blog

How to send command / input to multiple Putty window simultaneously

Putty is one of the best and must-have freeware for people working on Linux/Unix but use Windows as client like me.  We need to manage many servers and sometimes we are hoping we can run/execute same command on multiple host at same time, or just input same thing to multiple host. I searched online for a tool can do this. And it looks like PuTTYCS (PuTTY Command Sender) is the only one existing. But I’m a little bit disappointing after tried the software, it’s good but not good enough. It can only send command to each window one by one, and you have to wait until last window got input. So I think I should do something, and puttyCluster was born ( https://github.com/mingbowan/puttyCluster ) interface is simple: When you input Windows title pattern in the text box, you will be prompt for how many windows matching the pattern, like this: and you click the edit box under “cluster input”, what ever key you pressed will pass to all those windows simultaneously, even “Ctrl-C”, “Esc” ...
2 comments
Read more

enable special character support in Graphite metric name

Problem Graphite doesn’t support special characters like “ “ (empty space), “/” slash etc. Because it expect everything to be just ASCII to split/processing them, and then make directories based on metric name. For example:   Metric:     datacenter1.server1.app1.metric1.abc Will create datacenter1/server1/app1/metric1/abc.wsp But Metric: datacentter1.this is a test/with/path.app.test will fail when create directory So any special name not allow to appear in directory/file name is not supported by Graphite.   What we can do?   We can urlEncode the metric name which has special characters. So like “/var/opt” (not valid file name) will become “%2Fvar%2Fopt”(now valid), using urlEncode instead of others (like BASE64) is because this will keep most of data readable.   So what to change? 1. urlEncode metric name before send to Graphite (if you always sending metrics using text/line mode instead of pickle/batch mode, then you may consider modify ...
2 comments
Read more