/home/user> python seventeen.py | more
21124
/home/user> cat seventeen.py
# dict which we will map over to get number of letters
numbers = {}
# create dict for 0 through 999
for i in range(0,10):
for j in range(0,10):
for k in range(0,10):
numbers[i*100+j*10+k] = [i,j,k]
# delete zero, since it is not included in statement of problem.
del numbers[0]
# Create lookup table for converting first digit 1 to 9 to words
hundredsLookup = {}
hundredsLookup[1] = "onehundredand"
hundredsLookup[2] = "twohundredand"
hundredsLookup[3] = "threehundredand"
hundredsLookup[4] = "fourhundredand"
hundredsLookup[5] = "fivehundredand"
hundredsLookup[6] = "sixhundredand"
hundredsLookup[7] = "sevenhundredand"
hundredsLookup[8] = "eighthundredand"
hundredsLookup[9] = "ninehundredand"
hundredsLookup[0] = ''
for n in numbers.keys():
numbers[n][0] = hundredsLookup[numbers[n][0]]
# remove 'and' from even hundreds.
numbers[100][0], numbers[100][1], numbers[100][2]= "onehundred", '',''
numbers[200][0], numbers[200][1], numbers[300][2]= "twohundred", '',''
numbers[300][0], numbers[300][1], numbers[300][2]= "threehundred", '',''
numbers[400][0], numbers[400][1], numbers[400][2]= "fourhundred", '',''
numbers[500][0], numbers[500][1], numbers[500][2]= "fivehundred", '',''
numbers[600][0], numbers[600][1], numbers[600][2]= "sixhundred", '',''
numbers[700][0], numbers[700][1], numbers[700][2]= "sevenhundred", '',''
numbers[800][0], numbers[800][1], numbers[800][2]= "eighthundred", '',''
numbers[900][0], numbers[900][1], numbers[900][2]= "ninehundred", '',''
#create a lookup table for converting teens to words
teensLookup = {}
teensLookup[0] = 'ten'
teensLookup[1] = 'eleven'
teensLookup[2] = 'twelve'
teensLookup[3] = 'thirteen'
teensLookup[4] = 'fourteen'
teensLookup[5] = 'fifteen'
teensLookup[6] = 'sixteen'
teensLookup[7] = 'seventeen'
teensLookup[8] = 'eighteen'
teensLookup[9] = 'nineteen'
for n in range(1,1000):
if numbers[n][1] == 1:
numbers[n][1] = ''
numbers[n][2] = teensLookup[numbers[n][2]]
elif numbers[n][1] == 0:
numbers[n][1] = ''
elif numbers[n][1] == 2:
numbers[n][1] = 'twenty'
elif numbers[n][1] == 3:
numbers[n][1] = 'thirty'
elif numbers[n][1] == 4:
numbers[n][1] = 'forty'
elif numbers[n][1] == 5:
numbers[n][1] = 'fifty'
elif numbers[n][1] == 6:
numbers[n][1] = 'sixty'
elif numbers[n][1] == 7:
numbers[n][1] = 'seventy'
elif numbers[n][1] == 8:
numbers[n][1] = 'eighty'
elif numbers[n][1] == 9:
numbers[n][1] = 'ninety'
if numbers[n][2] == 0:
numbers[n][2] = ''
elif numbers[n][2] == 1:
numbers[n][2] = 'one'
elif numbers[n][2] == 2:
numbers[n][2] = 'two'
elif numbers[n][2] == 3:
numbers [n][2] = 'three'
elif numbers[n][2] == 4:
numbers[n][2] = 'four'
elif numbers[n][2] == 5:
numbers[n][2] = 'five'
elif numbers[n][2] == 6:
numbers[n][2] = 'six'
elif numbers[n][2] == 7:
numbers[n][2] = 'seven'
elif numbers[n][2] == 8:
numbers[n][2] = 'eight'
elif numbers[n][2] == 9:
numbers[n][2] = 'nine'
results = [numbers[n][0] + numbers[n][1] + numbers[n][2] for n in numbers.keys()] + ['onethousand']
counts = [len(s) for s in results]
print sum(counts)
Thursday, September 11, 2008
Friday, September 5, 2008
Euler Project Problem 16
>>> tot = str(2**1000)
>>> tot
'10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376'
>>> total = [tot[i] for i in range(len(tot))]
>>> total
['1', '0', '7', '1', '5', '0', '8', '6', '0', '7', '1', '8', '6', '2', '6', '7', '3', '2', '0', '9', '4', '8', '4', '2', '5', '0', '4', '9', '0', '6', '0', '0', '0', '1', '8', '1', '0', '5', '6', '1', '4', '0', '4', '8', '1', '1', '7', '0', '5', '5', '3', '3', '6', '0', '7', '4', '4', '3', '7', '5', '0', '3', '8', '8', '3', '7', '0', '3', '5', '1', '0', '5', '1', '1', '2', '4', '9', '3', '6', '1', '2', '2', '4', '9', '3', '1', '9', '8', '3', '7', '8', '8', '1', '5', '6', '9', '5', '8', '5', '8', '1', '2', '7', '5', '9', '4', '6', '7', '2', '9', '1', '7', '5', '5', '3', '1', '4', '6', '8', '2', '5', '1', '8', '7', '1', '4', '5', '2', '8', '5', '6', '9', '2', '3', '1', '4', '0', '4', '3', '5', '9', '8', '4', '5', '7', '7', '5', '7', '4', '6', '9', '8', '5', '7', '4', '8', '0', '3', '9', '3', '4', '5', '6', '7', '7', '7', '4', '8', '2', '4', '2', '3', '0', '9', '8', '5', '4', '2', '1', '0', '7', '4', '6', '0', '5', '0', '6', '2', '3', '7', '1', '1', '4', '1', '8', '7', '7', '9', '5', '4', '1', '8', '2', '1', '5', '3', '0', '4', '6', '4', '7', '4', '9', '8', '3', '5', '8', '1', '9', '4', '1', '2', '6', '7', '3', '9', '8', '7', '6', '7', '5', '5', '9', '1', '6', '5', '5', '4', '3', '9', '4', '6', '0', '7', '7', '0', '6', '2', '9', '1', '4', '5', '7', '1', '1', '9', '6', '4', '7', '7', '6', '8', '6', '5', '4', '2', '1', '6', '7', '6', '6', '0', '4', '2', '9', '8', '3', '1', '6', '5', '2', '6', '2', '4', '3', '8', '6', '8', '3', '7', '2', '0', '5', '6', '6', '8', '0', '6', '9', '3', '7', '6']
>>> totalInt = map(int, total)
>>> totalInt
[1, 0, 7, 1, 5, 0, 8, 6, 0, 7, 1, 8, 6, 2, 6, 7, 3, 2, 0, 9, 4, 8, 4, 2, 5, 0, 4, 9, 0, 6, 0, 0, 0, 1, 8, 1, 0, 5, 6, 1, 4, 0, 4, 8, 1, 1, 7, 0, 5, 5, 3, 3, 6, 0, 7, 4, 4, 3, 7, 5, 0, 3, 8, 8, 3, 7, 0, 3, 5, 1, 0, 5, 1, 1, 2, 4, 9, 3, 6, 1, 2, 2, 4, 9, 3, 1, 9, 8, 3, 7, 8, 8, 1, 5, 6, 9, 5, 8, 5, 8, 1, 2, 7, 5, 9, 4, 6, 7, 2, 9, 1, 7, 5, 5, 3, 1, 4, 6, 8, 2, 5, 1, 8, 7, 1, 4, 5, 2, 8, 5, 6, 9, 2, 3, 1, 4, 0, 4, 3, 5, 9, 8, 4, 5, 7, 7, 5, 7, 4, 6, 9, 8, 5, 7, 4, 8, 0, 3, 9, 3, 4, 5, 6, 7, 7, 7, 4, 8, 2, 4, 2, 3, 0, 9, 8, 5, 4, 2, 1, 0, 7, 4, 6, 0, 5, 0, 6, 2, 3, 7, 1, 1, 4, 1, 8, 7, 7, 9, 5, 4, 1, 8, 2, 1, 5, 3, 0, 4, 6, 4, 7, 4, 9, 8, 3, 5, 8, 1, 9, 4, 1, 2, 6, 7, 3, 9, 8, 7, 6, 7, 5, 5, 9, 1, 6, 5, 5, 4, 3, 9, 4, 6, 0, 7, 7, 0, 6, 2, 9, 1, 4, 5, 7, 1, 1, 9, 6, 4, 7, 7, 6, 8, 6, 5, 4, 2, 1, 6, 7, 6, 6, 0, 4, 2, 9, 8, 3, 1, 6, 5, 2, 6, 2, 4, 3, 8, 6, 8, 3, 7, 2, 0, 5, 6, 6, 8, 0, 6, 9, 3, 7, 6]
>>> sum(totalInt)
1366
>>> tot
'10715086071862673209484250490600018105614048117055336074437503883703510511249361224931983788156958581275946729175531468251871452856923140435984577574698574803934567774824230985421074605062371141877954182153046474983581941267398767559165543946077062914571196477686542167660429831652624386837205668069376'
>>> total = [tot[i] for i in range(len(tot))]
>>> total
['1', '0', '7', '1', '5', '0', '8', '6', '0', '7', '1', '8', '6', '2', '6', '7', '3', '2', '0', '9', '4', '8', '4', '2', '5', '0', '4', '9', '0', '6', '0', '0', '0', '1', '8', '1', '0', '5', '6', '1', '4', '0', '4', '8', '1', '1', '7', '0', '5', '5', '3', '3', '6', '0', '7', '4', '4', '3', '7', '5', '0', '3', '8', '8', '3', '7', '0', '3', '5', '1', '0', '5', '1', '1', '2', '4', '9', '3', '6', '1', '2', '2', '4', '9', '3', '1', '9', '8', '3', '7', '8', '8', '1', '5', '6', '9', '5', '8', '5', '8', '1', '2', '7', '5', '9', '4', '6', '7', '2', '9', '1', '7', '5', '5', '3', '1', '4', '6', '8', '2', '5', '1', '8', '7', '1', '4', '5', '2', '8', '5', '6', '9', '2', '3', '1', '4', '0', '4', '3', '5', '9', '8', '4', '5', '7', '7', '5', '7', '4', '6', '9', '8', '5', '7', '4', '8', '0', '3', '9', '3', '4', '5', '6', '7', '7', '7', '4', '8', '2', '4', '2', '3', '0', '9', '8', '5', '4', '2', '1', '0', '7', '4', '6', '0', '5', '0', '6', '2', '3', '7', '1', '1', '4', '1', '8', '7', '7', '9', '5', '4', '1', '8', '2', '1', '5', '3', '0', '4', '6', '4', '7', '4', '9', '8', '3', '5', '8', '1', '9', '4', '1', '2', '6', '7', '3', '9', '8', '7', '6', '7', '5', '5', '9', '1', '6', '5', '5', '4', '3', '9', '4', '6', '0', '7', '7', '0', '6', '2', '9', '1', '4', '5', '7', '1', '1', '9', '6', '4', '7', '7', '6', '8', '6', '5', '4', '2', '1', '6', '7', '6', '6', '0', '4', '2', '9', '8', '3', '1', '6', '5', '2', '6', '2', '4', '3', '8', '6', '8', '3', '7', '2', '0', '5', '6', '6', '8', '0', '6', '9', '3', '7', '6']
>>> totalInt = map(int, total)
>>> totalInt
[1, 0, 7, 1, 5, 0, 8, 6, 0, 7, 1, 8, 6, 2, 6, 7, 3, 2, 0, 9, 4, 8, 4, 2, 5, 0, 4, 9, 0, 6, 0, 0, 0, 1, 8, 1, 0, 5, 6, 1, 4, 0, 4, 8, 1, 1, 7, 0, 5, 5, 3, 3, 6, 0, 7, 4, 4, 3, 7, 5, 0, 3, 8, 8, 3, 7, 0, 3, 5, 1, 0, 5, 1, 1, 2, 4, 9, 3, 6, 1, 2, 2, 4, 9, 3, 1, 9, 8, 3, 7, 8, 8, 1, 5, 6, 9, 5, 8, 5, 8, 1, 2, 7, 5, 9, 4, 6, 7, 2, 9, 1, 7, 5, 5, 3, 1, 4, 6, 8, 2, 5, 1, 8, 7, 1, 4, 5, 2, 8, 5, 6, 9, 2, 3, 1, 4, 0, 4, 3, 5, 9, 8, 4, 5, 7, 7, 5, 7, 4, 6, 9, 8, 5, 7, 4, 8, 0, 3, 9, 3, 4, 5, 6, 7, 7, 7, 4, 8, 2, 4, 2, 3, 0, 9, 8, 5, 4, 2, 1, 0, 7, 4, 6, 0, 5, 0, 6, 2, 3, 7, 1, 1, 4, 1, 8, 7, 7, 9, 5, 4, 1, 8, 2, 1, 5, 3, 0, 4, 6, 4, 7, 4, 9, 8, 3, 5, 8, 1, 9, 4, 1, 2, 6, 7, 3, 9, 8, 7, 6, 7, 5, 5, 9, 1, 6, 5, 5, 4, 3, 9, 4, 6, 0, 7, 7, 0, 6, 2, 9, 1, 4, 5, 7, 1, 1, 9, 6, 4, 7, 7, 6, 8, 6, 5, 4, 2, 1, 6, 7, 6, 6, 0, 4, 2, 9, 8, 3, 1, 6, 5, 2, 6, 2, 4, 3, 8, 6, 8, 3, 7, 2, 0, 5, 6, 6, 8, 0, 6, 9, 3, 7, 6]
>>> sum(totalInt)
1366
Euler Project Problem 15 factorial
[jmark@www ~]$ cat factorial.py
def fact(n):
if n == 0:
return 1
else:
return n * fact(n-1)
>>> factorial.fact(40)/(factorial.fact(20)**2)
137846528820L
def fact(n):
if n == 0:
return 1
else:
return n * fact(n-1)
>>> factorial.fact(40)/(factorial.fact(20)**2)
137846528820L
Thursday, September 4, 2008
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()
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()
Wednesday, September 3, 2008
Euler Problem 13
/home/user> python problem13.py
5537376230
/home/user> cat problem13.py
def first10(n):
stringn= str(n)
stringn=stringn[0:10]
return int(stringn)
x=[37107287533902102798797998220837590246510135740250,
46376937677490009712648124896970078050417018260538,
74324986199524741059474233309513058123726617309629,
91942213363574161572522430563301811072406154908250,
23067588207539346171171980310421047513778063246676,
89261670696623633820136378418383684178734361726757,
28112879812849979408065481931592621691275889832738,
44274228917432520321923589422876796487670272189318,
47451445736001306439091167216856844588711603153276,
70386486105843025439939619828917593665686757934951,
62176457141856560629502157223196586755079324193331,
64906352462741904929101432445813822663347944758178,
92575867718337217661963751590579239728245598838407,
58203565325359399008402633568948830189458628227828,
80181199384826282014278194139940567587151170094390,
35398664372827112653829987240784473053190104293586,
86515506006295864861532075273371959191420517255829,
71693888707715466499115593487603532921714970056938,
54370070576826684624621495650076471787294438377604,
53282654108756828443191190634694037855217779295145,
36123272525000296071075082563815656710885258350721,
45876576172410976447339110607218265236877223636045,
17423706905851860660448207621209813287860733969412,
81142660418086830619328460811191061556940512689692,
51934325451728388641918047049293215058642563049483,
62467221648435076201727918039944693004732956340691,
15732444386908125794514089057706229429197107928209,
55037687525678773091862540744969844508330393682126,
18336384825330154686196124348767681297534375946515,
80386287592878490201521685554828717201219257766954,
78182833757993103614740356856449095527097864797581,
16726320100436897842553539920931837441497806860984,
48403098129077791799088218795327364475675590848030,
87086987551392711854517078544161852424320693150332,
59959406895756536782107074926966537676326235447210,
69793950679652694742597709739166693763042633987085,
41052684708299085211399427365734116182760315001271,
65378607361501080857009149939512557028198746004375,
35829035317434717326932123578154982629742552737307,
94953759765105305946966067683156574377167401875275,
88902802571733229619176668713819931811048770190271,
25267680276078003013678680992525463401061632866526,
36270218540497705585629946580636237993140746255962,
24074486908231174977792365466257246923322810917141,
91430288197103288597806669760892938638285025333403,
34413065578016127815921815005561868836468420090470,
23053081172816430487623791969842487255036638784583,
11487696932154902810424020138335124462181441773470,
63783299490636259666498587618221225225512486764533,
67720186971698544312419572409913959008952310058822,
95548255300263520781532296796249481641953868218774,
76085327132285723110424803456124867697064507995236,
37774242535411291684276865538926205024910326572967,
23701913275725675285653248258265463092207058596522,
29798860272258331913126375147341994889534765745501,
18495701454879288984856827726077713721403798879715,
38298203783031473527721580348144513491373226651381,
34829543829199918180278916522431027392251122869539,
40957953066405232632538044100059654939159879593635,
29746152185502371307642255121183693803580388584903,
41698116222072977186158236678424689157993532961922,
62467957194401269043877107275048102390895523597457,
23189706772547915061505504953922979530901129967519,
86188088225875314529584099251203829009407770775672,
11306739708304724483816533873502340845647058077308,
82959174767140363198008187129011875491310547126581,
97623331044818386269515456334926366572897563400500,
42846280183517070527831839425882145521227251250327,
55121603546981200581762165212827652751691296897789,
32238195734329339946437501907836945765883352399886,
75506164965184775180738168837861091527357929701337,
62177842752192623401942399639168044983993173312731,
32924185707147349566916674687634660915035914677504,
99518671430235219628894890102423325116913619626622,
73267460800591547471830798392868535206946944540724,
76841822524674417161514036427982273348055556214818,
97142617910342598647204516893989422179826088076852,
87783646182799346313767754307809363333018982642090,
10848802521674670883215120185883543223812876952786,
71329612474782464538636993009049310363619763878039,
62184073572399794223406235393808339651327408011116,
66627891981488087797941876876144230030984490851411,
60661826293682836764744779239180335110989069790714,
85786944089552990653640447425576083659976645795096,
66024396409905389607120198219976047599490197230297,
64913982680032973156037120041377903785566085089252,
16730939319872750275468906903707539413042652315011,
94809377245048795150954100921645863754710598436791,
78639167021187492431995700641917969777599028300699,
15368713711936614952811305876380278410754449733078,
40789923115535562561142322423255033685442488917353,
44889911501440648020369068063960672322193204149535,
41503128880339536053299340368006977710650566631954,
81234880673210146739058568557934581403627822703280,
82616570773948327592232845941706525094512325230608,
22918802058777319719839450180888072429661980811197,
77158542502016545090413245809786882778948721859617,
72107838435069186155435662884062257473692284509516,
20849603980134001723930671666823555245252804609722,
53503534226472524250874054075591789781264330331690]
print first10((sum(x)))
5537376230
/home/user> cat problem13.py
def first10(n):
stringn= str(n)
stringn=stringn[0:10]
return int(stringn)
x=[37107287533902102798797998220837590246510135740250,
46376937677490009712648124896970078050417018260538,
74324986199524741059474233309513058123726617309629,
91942213363574161572522430563301811072406154908250,
23067588207539346171171980310421047513778063246676,
89261670696623633820136378418383684178734361726757,
28112879812849979408065481931592621691275889832738,
44274228917432520321923589422876796487670272189318,
47451445736001306439091167216856844588711603153276,
70386486105843025439939619828917593665686757934951,
62176457141856560629502157223196586755079324193331,
64906352462741904929101432445813822663347944758178,
92575867718337217661963751590579239728245598838407,
58203565325359399008402633568948830189458628227828,
80181199384826282014278194139940567587151170094390,
35398664372827112653829987240784473053190104293586,
86515506006295864861532075273371959191420517255829,
71693888707715466499115593487603532921714970056938,
54370070576826684624621495650076471787294438377604,
53282654108756828443191190634694037855217779295145,
36123272525000296071075082563815656710885258350721,
45876576172410976447339110607218265236877223636045,
17423706905851860660448207621209813287860733969412,
81142660418086830619328460811191061556940512689692,
51934325451728388641918047049293215058642563049483,
62467221648435076201727918039944693004732956340691,
15732444386908125794514089057706229429197107928209,
55037687525678773091862540744969844508330393682126,
18336384825330154686196124348767681297534375946515,
80386287592878490201521685554828717201219257766954,
78182833757993103614740356856449095527097864797581,
16726320100436897842553539920931837441497806860984,
48403098129077791799088218795327364475675590848030,
87086987551392711854517078544161852424320693150332,
59959406895756536782107074926966537676326235447210,
69793950679652694742597709739166693763042633987085,
41052684708299085211399427365734116182760315001271,
65378607361501080857009149939512557028198746004375,
35829035317434717326932123578154982629742552737307,
94953759765105305946966067683156574377167401875275,
88902802571733229619176668713819931811048770190271,
25267680276078003013678680992525463401061632866526,
36270218540497705585629946580636237993140746255962,
24074486908231174977792365466257246923322810917141,
91430288197103288597806669760892938638285025333403,
34413065578016127815921815005561868836468420090470,
23053081172816430487623791969842487255036638784583,
11487696932154902810424020138335124462181441773470,
63783299490636259666498587618221225225512486764533,
67720186971698544312419572409913959008952310058822,
95548255300263520781532296796249481641953868218774,
76085327132285723110424803456124867697064507995236,
37774242535411291684276865538926205024910326572967,
23701913275725675285653248258265463092207058596522,
29798860272258331913126375147341994889534765745501,
18495701454879288984856827726077713721403798879715,
38298203783031473527721580348144513491373226651381,
34829543829199918180278916522431027392251122869539,
40957953066405232632538044100059654939159879593635,
29746152185502371307642255121183693803580388584903,
41698116222072977186158236678424689157993532961922,
62467957194401269043877107275048102390895523597457,
23189706772547915061505504953922979530901129967519,
86188088225875314529584099251203829009407770775672,
11306739708304724483816533873502340845647058077308,
82959174767140363198008187129011875491310547126581,
97623331044818386269515456334926366572897563400500,
42846280183517070527831839425882145521227251250327,
55121603546981200581762165212827652751691296897789,
32238195734329339946437501907836945765883352399886,
75506164965184775180738168837861091527357929701337,
62177842752192623401942399639168044983993173312731,
32924185707147349566916674687634660915035914677504,
99518671430235219628894890102423325116913619626622,
73267460800591547471830798392868535206946944540724,
76841822524674417161514036427982273348055556214818,
97142617910342598647204516893989422179826088076852,
87783646182799346313767754307809363333018982642090,
10848802521674670883215120185883543223812876952786,
71329612474782464538636993009049310363619763878039,
62184073572399794223406235393808339651327408011116,
66627891981488087797941876876144230030984490851411,
60661826293682836764744779239180335110989069790714,
85786944089552990653640447425576083659976645795096,
66024396409905389607120198219976047599490197230297,
64913982680032973156037120041377903785566085089252,
16730939319872750275468906903707539413042652315011,
94809377245048795150954100921645863754710598436791,
78639167021187492431995700641917969777599028300699,
15368713711936614952811305876380278410754449733078,
40789923115535562561142322423255033685442488917353,
44889911501440648020369068063960672322193204149535,
41503128880339536053299340368006977710650566631954,
81234880673210146739058568557934581403627822703280,
82616570773948327592232845941706525094512325230608,
22918802058777319719839450180888072429661980811197,
77158542502016545090413245809786882778948721859617,
72107838435069186155435662884062257473692284509516,
20849603980134001723930671666823555245252804609722,
53503534226472524250874054075591789781264330331690]
print first10((sum(x)))
Tuesday, September 2, 2008
Project Euler Problem 12 Triangular Numbers
"""Mark-Jason Dominus provides a useful result from number theory which we can use to solve this problem using a method other than pure brute force. He writes:
http://blog.plover.com/oops/triangular-phi.html
Dominus states that his own solution using these formulas took 90 seconds using python. If the solution takes more than 60 seconds then first try it on faster machines.
Based on http://www.mindstab.net/wordpress/archives/tag/primes there is reason to think that Python is extremely slow when it comes to calculating prime numbers and is much slower than C#. Therefore Boo is also faster than Python. So if Python is still too slow then convert to Boo and try.
As it happens, my solution takes 40 seconds on my iMac but 2.:45 minutes on my Asus EEE and 1:05 minutes on my generic Intel server.
========================================================================
http://wj32.wordpress.com/2007/10/08/factor-for-python/
# """
# Factor a number
#
# Wj.
# """
#
# # Simple factoring
# def factor(n, noduplicates = False):
# intn = int(n)
# factors = {}
# lastfactor = n
# i = 0
#
# # 1 is a special case
# if n == 1:
# return {1: 1}
#
# while 1:
# i += 1
#
# # avoid duplicates like {1: 3, 3: 1}
# if noduplicates and lastfactor <= i:
# break
#
# # stop when i is bigger than n
# if i > n:
# break
#
# if n % i == 0:
# factors[i] = n / i
# lastfactor = n / i
#
# return factors
#
# if __name__ == "__main__":
# import sys
#
# print "Enter an integer:"
# number = sys.stdin.readline()
# print "Factors: " + str(factor(int(number), True))
========================================================
And here is my solution, which is based upon Dominus's method and factor.py
new-host-2:~ gayelynntaxey$ python factor.py
sys:1: DeprecationWarning: Non-ASCII character '\xce' in file factor.py on line 36, but no encoding declared; see http://www.python.org/peps/pep-0263.html for details
Tue Sep 2 21:10:15 2008
76576500
Tue Sep 2 21:10:55 2008
new-host-2:~ gayelynntaxey$ cat factor.py
def factor(n, noduplicates = False):
intn = int(n)
factors = {}
lastfactor = n
i = 0
# 1 is a special case
if n == 1:
return {1: 1}
while 1:
i += 1
# avoid duplicates like {1: 3, 3: 1}
if noduplicates and lastfactor <= i:
break
# stop when i is bigger than n
if i > n:
break
if n % i == 0:
factors[i] = n / i
lastfactor = n / i
return factors
def factorCount(n):
return len(factor(n))
def T(k):
return (k*k + k)/2
# either n is even, and ν(T) = ν(n/2)·ν(n+1), or n is odd, and ν(T) = ν(n)·ν((n+1)/2).
def vT(n):
if n % 2 == 0:
return factorCount(n/2) * factorCount(n+1)
else:
return factorCount(n)*factorCount((n+1)/2)
import time
print time.asctime()
n = 2
while vT(n) < 500:
n += 1
print T(n)
print time.asctime()
new-host-2:~ gayelynntaxey$
http://blog.plover.com/oops/triangular-phi.html
Abhijit Menon-Sen wrote to me to ask for advice in finding the smallest triangular number that has at least 500 divisors. (That is, he wants the smallest n such that both n = (k2 + k)/2 for some integer k and also ν(n) ≥ 500, where ν(n) is the number of integers that divide n.) He said in his note that he believed that brute-force search would take too long, and asked how I might trim down the search.
The first thing that occurred to me was that ν is a multiplicative function, which means that ν(ab) = ν(a)ν(b) whenever a and b are relatively prime. Since n and n-1 are relatively prime, we have that ν(n(n-1)) = ν(n)·ν(n-1), and so if T is triangular, it should be easy to calculate ν(T). In particular, either n is even, and ν(T) = ν(n/2)·ν(n+1), or n is odd, and ν(T) = ν(n)·ν((n+1)/2).
Dominus states that his own solution using these formulas took 90 seconds using python. If the solution takes more than 60 seconds then first try it on faster machines.
Based on http://www.mindstab.net/wordpress/archives/tag/primes there is reason to think that Python is extremely slow when it comes to calculating prime numbers and is much slower than C#. Therefore Boo is also faster than Python. So if Python is still too slow then convert to Boo and try.
As it happens, my solution takes 40 seconds on my iMac but 2.:45 minutes on my Asus EEE and 1:05 minutes on my generic Intel server.
========================================================================
http://wj32.wordpress.com/2007/10/08/factor-for-python/
# """
# Factor a number
#
# Wj.
# """
#
# # Simple factoring
# def factor(n, noduplicates = False):
# intn = int(n)
# factors = {}
# lastfactor = n
# i = 0
#
# # 1 is a special case
# if n == 1:
# return {1: 1}
#
# while 1:
# i += 1
#
# # avoid duplicates like {1: 3, 3: 1}
# if noduplicates and lastfactor <= i:
# break
#
# # stop when i is bigger than n
# if i > n:
# break
#
# if n % i == 0:
# factors[i] = n / i
# lastfactor = n / i
#
# return factors
#
# if __name__ == "__main__":
# import sys
#
# print "Enter an integer:"
# number = sys.stdin.readline()
# print "Factors: " + str(factor(int(number), True))
========================================================
And here is my solution, which is based upon Dominus's method and factor.py
new-host-2:~ gayelynntaxey$ python factor.py
sys:1: DeprecationWarning: Non-ASCII character '\xce' in file factor.py on line 36, but no encoding declared; see http://www.python.org/peps/pep-0263.html for details
Tue Sep 2 21:10:15 2008
76576500
Tue Sep 2 21:10:55 2008
new-host-2:~ gayelynntaxey$ cat factor.py
def factor(n, noduplicates = False):
intn = int(n)
factors = {}
lastfactor = n
i = 0
# 1 is a special case
if n == 1:
return {1: 1}
while 1:
i += 1
# avoid duplicates like {1: 3, 3: 1}
if noduplicates and lastfactor <= i:
break
# stop when i is bigger than n
if i > n:
break
if n % i == 0:
factors[i] = n / i
lastfactor = n / i
return factors
def factorCount(n):
return len(factor(n))
def T(k):
return (k*k + k)/2
# either n is even, and ν(T) = ν(n/2)·ν(n+1), or n is odd, and ν(T) = ν(n)·ν((n+1)/2).
def vT(n):
if n % 2 == 0:
return factorCount(n/2) * factorCount(n+1)
else:
return factorCount(n)*factorCount((n+1)/2)
import time
print time.asctime()
n = 2
while vT(n) < 500:
n += 1
print T(n)
print time.asctime()
new-host-2:~ gayelynntaxey$
Monday, September 1, 2008
Euler Problem 11 Diagonal multiplication
/home/user> python num.py
70600674
/home/user> cat num.py
from Numeric import *
a =array(((8,2,22,97,38,15,0,40,0,75,4,5,7,78,52,12,50,77,91,8), (49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,4,56,62,0), (81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,3,49,13,36,65), (52,70,95,23,4,60,11,42,69,24,68,56,1,32,56,71,37,2,36,91), (22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80), (24,47,32,60,99,3,45,2,44,75,33,53,78,36,84,20,35,17,12,50), (32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70), (67,26,20,68,2,62,12,20,95,63,94,39,63,8,40,91,66,49,94,21), (24,55,58,5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72), (21,36,23,9,75,0,76,44,20,45,35,14,0,61,33,97,34,31,33,95), (78,17,53,28,22,75,31,67,15,94,3,80,4,62,16,14,9,53,56,92), (16,39,5,42,96,35,31,47,55,58,88,24,0,17,54,24,36,29,85,57), (86,56,0,48,35,71,89,7,5,44,44,37,44,60,21,58,51,54,17,58), (19,80,81,68,5,94,47,69,28,73,92,13,86,52,17,77,4,89,55,40), (4,52,8,83,97,35,99,16,7,97,57,32,16,26,26,79,33,27,98,66), (88,36,68,87,57,62,20,72,3,46,33,67,46,55,12,32,63,93,53,69), (4,42,16,73,38,25,39,11,24,94,72,18,8,46,29,32,40,62,76,36), (20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,4,36,16), (20,73,35,29,78,31,90,1,74,31,49,71,48,86,81,16,23,57,5,54), (1,70,54,71,83,51,54,69,16,92,33,48,61,43,52,1,89,19,67,48)))
def horiz(n,m):
return a[n,m]*a[n,m+1]*a[n,m+2]*a[n,m+3]
def vert(n,m):
return a[n,m]*a[n+1,m]*a[n+2,m]*a[n+3,m]
def rightDownDiag(n,m):
return a[n,m]*a[n+1,m+1]*a[n+2,m+2]*a[n+3,m+3]
def rightUpDiag(n,m):
return a[n,m]*a[n-1,m+1]*a[n-2,m+2]*a[n-3,m+3]
def maxRow(n):
return max(horiz(n,i) for i in range(17))
def maxHoriz():
return max(maxRow(n) for n in range(20))
def maxCol(m):
return max(vert(i,m) for i in range(17))
def maxVert():
return max(maxCol(m) for m in range(20))
def maxRightDownDiag():
return max([rightDownDiag(n,m) for n in range(17) for m in range(17)])
def maxRightUpDiag():
return max([rightUpDiag(n,m) for n in range(3,20) for m in range(17)])
def globalMax():
return max(maxHoriz(), maxVert(), maxRightDownDiag(), maxRightUpDiag())
print globalMax()
70600674
/home/user> cat num.py
from Numeric import *
a =array(((8,2,22,97,38,15,0,40,0,75,4,5,7,78,52,12,50,77,91,8), (49,49,99,40,17,81,18,57,60,87,17,40,98,43,69,48,4,56,62,0), (81,49,31,73,55,79,14,29,93,71,40,67,53,88,30,3,49,13,36,65), (52,70,95,23,4,60,11,42,69,24,68,56,1,32,56,71,37,2,36,91), (22,31,16,71,51,67,63,89,41,92,36,54,22,40,40,28,66,33,13,80), (24,47,32,60,99,3,45,2,44,75,33,53,78,36,84,20,35,17,12,50), (32,98,81,28,64,23,67,10,26,38,40,67,59,54,70,66,18,38,64,70), (67,26,20,68,2,62,12,20,95,63,94,39,63,8,40,91,66,49,94,21), (24,55,58,5,66,73,99,26,97,17,78,78,96,83,14,88,34,89,63,72), (21,36,23,9,75,0,76,44,20,45,35,14,0,61,33,97,34,31,33,95), (78,17,53,28,22,75,31,67,15,94,3,80,4,62,16,14,9,53,56,92), (16,39,5,42,96,35,31,47,55,58,88,24,0,17,54,24,36,29,85,57), (86,56,0,48,35,71,89,7,5,44,44,37,44,60,21,58,51,54,17,58), (19,80,81,68,5,94,47,69,28,73,92,13,86,52,17,77,4,89,55,40), (4,52,8,83,97,35,99,16,7,97,57,32,16,26,26,79,33,27,98,66), (88,36,68,87,57,62,20,72,3,46,33,67,46,55,12,32,63,93,53,69), (4,42,16,73,38,25,39,11,24,94,72,18,8,46,29,32,40,62,76,36), (20,69,36,41,72,30,23,88,34,62,99,69,82,67,59,85,74,4,36,16), (20,73,35,29,78,31,90,1,74,31,49,71,48,86,81,16,23,57,5,54), (1,70,54,71,83,51,54,69,16,92,33,48,61,43,52,1,89,19,67,48)))
def horiz(n,m):
return a[n,m]*a[n,m+1]*a[n,m+2]*a[n,m+3]
def vert(n,m):
return a[n,m]*a[n+1,m]*a[n+2,m]*a[n+3,m]
def rightDownDiag(n,m):
return a[n,m]*a[n+1,m+1]*a[n+2,m+2]*a[n+3,m+3]
def rightUpDiag(n,m):
return a[n,m]*a[n-1,m+1]*a[n-2,m+2]*a[n-3,m+3]
def maxRow(n):
return max(horiz(n,i) for i in range(17))
def maxHoriz():
return max(maxRow(n) for n in range(20))
def maxCol(m):
return max(vert(i,m) for i in range(17))
def maxVert():
return max(maxCol(m) for m in range(20))
def maxRightDownDiag():
return max([rightDownDiag(n,m) for n in range(17) for m in range(17)])
def maxRightUpDiag():
return max([rightUpDiag(n,m) for n in range(3,20) for m in range(17)])
def globalMax():
return max(maxHoriz(), maxVert(), maxRightDownDiag(), maxRightUpDiag())
print globalMax()
Subscribe to:
Posts (Atom)