Skip to main content

Project Euler Problem #14

the solution I got runs more than 1 second, which is terrible. Please help if you have better algorithm


"""
Project Euler Problem #14
==========================

The following iterative sequence is defined for the set of positive
integers:

n->n/2 (n is even)
n->3n + 1 (n is odd)

Using the rule above and starting with 13, we generate the following
sequence:
                  13->40->20->10->5->16->8->4->2->1

It can be seen that this sequence (starting at 13 and finishing at 1)
contains 10 terms. Although it has not been proved yet (Collatz Problem),
it is thought that all starting numbers finish at 1.

Which starting number, under one million, produces the longest chain?

NOTE: Once the chain starts the terms are allowed to go above one million.
"""

limit=1000000
uplimit  = limit * 3
answer = 1
maxval = 0
data = [0] * uplimit
data[1] = 1

for ind in xrange(1,limit):
    cval = ind
    stack = []
    while True:
        if cval < uplimit and data[cval] > 0:
            break
        stack.append(cval)
        if cval % 2 == 0:
            cval = cval / 2
        else:
            cval = cval * 3 + 1
    val = data[cval]
    while stack:
        val += 1
        ind = stack.pop()
        if ind < uplimit:
            data[ind] = val
    if val > maxval:
        maxval = val
        answer = ind

print answer
========================== 

$ time python 014.py 
837799

real 0m1.744s
user 0m1.734s
sys 0m0.011s

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