Euler Project Problem Number 14

new-host-2:~ gayelynntaxey$ python nonbrute.py
Fri Sep 5 00:25:41 2008
[-99999, 525, 837799]
Fri Sep 5 00:26:36 2008
new-host-2:~ gayelynntaxey$ cat nonbrute.py
class NonCDR(object):
"""By definition any n which is not the first in a sequence of function values is not the n which takes the longest to converge to 1.
"""

def __init__(self):
self.nonCDR = [True for i in range(0,1000000)]
self.nonCDR[0] = False
self.nonCDR[1] = False
def FindAFalse(self, n):
"""Sets to false in nonCDR any n which is known not to be the n which takes longest to converge.
"""
if n % 2 == 0:
self.nonCDR[n//2] = False
if n % 2 == 1:
nextVal = int(n * 3 + 1)
if nextVal < 1000000:
self.nonCDR[nextVal] = False
elif nextVal < 1999998:
self.nonCDR[nextVal//2] = False
def filt(self):
"""Applies the FindAFalse(n) function to the first two million integers.
"""
for i in range(2,1000000):
self.FindAFalse(i)


import time
print time.asctime()

import exceptions
class InputError(exceptions.Exception):
def __init__(self,args=None):
self.args = args
ELEMENT = 0
SERIESLENGTH = 1
ORIGINALELEMENT = 2
zeroError = InputError("Starting number must be greater than zero.")

s = NonCDR()
s.filt()

def f(n):
"""Returns a triplet whose first value is the current n being calculated, whose second value is the number of numbers tested so far in this sequence, and whose third value is the number at the start of the sequence
"""
if n[ELEMENT] == 0:
raise zeroError
if n[SERIESLENGTH] == 0:
n[ORIGINALELEMENT] = n[ELEMENT]
if n[ELEMENT] % 2 == 0:
return f([n[ELEMENT]//2, n[SERIESLENGTH] + 1, n[ORIGINALELEMENT]])
elif n[ELEMENT] == 1:
return [-99999,n[SERIESLENGTH] + 1, n[ORIGINALELEMENT]]
else:
return f([(3 * n[ELEMENT]) + 1, n[SERIESLENGTH] + 1, n[ORIGINALELEMENT]])

maximumSoFar = (1,0,0)
for i in range(2,1000000):
if s.nonCDR[i]:
result = f([i,0,0])
if result[SERIESLENGTH] > maximumSoFar[SERIESLENGTH]:
maximumSoFar = result
print maximumSoFar
print time.asctime()