Please note: This wiki is currently running in test mode after an attack on January 5 2013. All passwords were reset, so you will have to use the password recovery function to get a new password. To edit wiki pages, please log in first. See the wiki attack description page for more details. If you find problems, please report them to the pydotorg-www mailing list.

Python solutions and commentary for Programming Challenges

Index

# Problem 110101: The 3n + 1 problem

```    def memoized(fn):
memoized_lengths = [0] * 1000000
def fn2(n):
if not memoized_lengths[n]:
memoized_lengths[n] = fn(n)
return memoized_lengths[n]
return fn2

@memoized
def cycle_length(n):
if n == 1: return 1
if n % 2:
return cycle_length(n * 3 + 1) + 1
return cycle_length(n / 2) + 1

def problem(i,j):
return max([cycle_length(x) for x in range(i, j+1)])

def test_cycle_length():
assert cycle_length(22) == 16
assert cycle_length(10) == 7
assert cycle_length(11) == 15
print 'OK'

def test_problem():
print 1, 10, problem(1, 10)
print 100, 200, problem(100, 200)
print 201, 210, problem(201, 210)
print 900, 100, problem(900, 1000)

if __name__ == '__main__': test_problem()```

ProblemSets/Programming Challenges Solutions (last edited 2008-11-15 14:00:22 by localhost)