Project Euler Problem 26 repeating sequences

[970, 971]
[27, 972]
[1, 973]
[486, 974]
[6, 975]
[60, 976]
[976, 977]
[81, 978]
[44, 979]
[42, 980]
[108, 981]
[1, 982]
[982, 983]
[5, 984]
[98, 985]
[112, 986]
[138, 987]
[18, 988]
[462, 989]
[2, 990]
[495, 991]
[15, 992]
[110, 993]
[210, 994]
[99, 995]
[41, 996]
[166, 997]
[498, 998]
[3, 999]
>>> twentysix.d(983)
'0.001017293997965412004069175991861648016276703967446592065106815869786368260427263479145473041709053916581892166836215666327568667344862665310274669379450661241098677517802644964394710071210579857578840284842319430315361139369277721261444557477110885045778229908443540183112919633774160732451678535096642929806714140386571719226856561546286876907426246185147507629704984740590030518819938962360122075279755849440488301119023397761953204476093591047812817904374364191251271617497456765005086469989827060020345879959308240081383519837232960325534079348931841302136317395727365208545269582909460834181078331637843336724313326551373346897253306205493387589013224821973550356052899287894201424211597151576805696846388606307222787385554425228891149542217700915564598168870803662258392675483214649033570701932858596134282807731434384537131230925737538148524923702950152594099694811800610376398779247202441505595116988809766022380467955239064089521871820956256358087487283825025432349949135300101729399796541200406917599186164801627670396744659206510681586978636826042726347914547304170905391658189216683621566632756866734486266531027466937945066124109867751780264496439471007121057985757884028484231943031536113936927772126144455747711088504577822990844354018311291963377416073245167853509664292980671414038657171922685656154628687690742624618514750762970498474059003051881993896236012207527975584944048830111902339776195320447609359104781281790437436419125127161749745676500508646998982706002034587995930824008138351983723296032553407934893184130213631739572736520854526958290946083418107833163784333672431332655137334689725330620549338758901322482197355035605289928789420142421159715157680569684638860630722278738555442522889114954221770091556459816887080366225839267548321464903357070193285859613428280773143438453713123092573753814852492370295015259409969481180061037639877924720244150559511698880976602238046795523906408952187182095625635808748728382502543234994913530010172939979654120040691759918616480162767039674465920651068158697863682604272634791454'
/home/user> cat twentysix.py
from decimal import *
import re
getcontext().prec = 2050
getcontext().rounding = ROUND_DOWN
num = Decimal(1)
def d(den):
return str(Decimal(num/den))
p = re.compile(r'(?P\d+?)(?P=word)')
def getExactNum(n):
for i in range(1,n):
m = p.match(d(i)[15:] + '00')
yield [len(m.group(1)), i]
return

Project Euler Problem 25 Fibonacci number lengths

[root@www ~]# python twentyfive.py
4000 836
4780 999
4782 1000
Started at: Sun Sep 21 01:16:27 2008 Ended at: Sun Sep 21 01:16:27 2008
[root@www ~]# cat twentyfive.py

# -*- coding: utf-8 -*-
"""
<+ MODULE_NAME +>
Project Euler Problem Set
<+ DESCRIPTION +>
Problem 25
Solutions in Python to the problems at http://projecteuler.net

Licensed under the Creative Commons license; see http://creativecommons.org for more details. In short, this means you can freely reuse, modify and distribute this program, also commercially, for as long you provide a proper attribution.

Copyright by Jonathan Mark, jonathanmark.com/aristede.com, jmark@aristede.com

http://en.literateprograms.org/Fibonacci_numbers_%28Python%29#Quick_exact_computation_of_large_individual_Fibonacci_numbers_.28second_take.29
for fib module.

>>> print 881 + 1
882

"""
import time
starttime = time.asctime()

# for any number of digits n, there are either four or five
# fibonacci numbers containing that many digits.
# get fibonacci_LF module from literateprograms.org
import fibonacci_LF
n = 4000
l = len(str(fibonacci_LF.fib(n)))
diff = 1000 - l
print n,l
while diff > 1:
n += 4 * diff
l = len(str(fibonacci_LF.fib(n)))
diff = 1000 - l
print n,l

while diff > 0:
n += 1
l = len(str(fibonacci_LF.fib(n)))
diff = 1000 - l
print n,l


print "Started at: ", starttime, " Ended at: ",time.asctime()

if __name__ == "__main__":
import doctest
doctest.testmod()

Project Euler Problem 24 Ordering Numbers Having Non-Repeating Digits

[root@www ~]# python cartesian.py
[2, 7, 8, 3, 9, 1, 5, 4, 6, 0]
Started at: Sat Sep 20 16:00:06 2008 Ended at: Sat Sep 20 16:00:33 2008
[root@www ~]# cat cartesian.py
# -*- coding: utf-8 -*-
"""
<+ MODULE_NAME +>
Project Euler Problem Set
<+ DESCRIPTION +>
Solutions in Python to the problems at http://projecteuler.net

Licensed under the Creative Commons license; see http://creativecommons.org for more details. In short, this means you can freely reuse, modify and distribute this program, also commercially, for as long you provide a proper attribution.

Copyright by Jonathan Mark, jonathanmark.com/aristede.com, jmark@aristede.com

>>> print 881 + 1
882

"""
import time
starttime = time.asctime()

class UniqueProduct:
"""A list of permutations used to solve problem 24.
9! is 362880. That means that there are 362880 10 digit numbers
in which each digit appears only once and the first digit is 0. The
same applies to such numbers in which the first digit is 1 or 2.

When ordered, the 0s precede the 1s and 2s. Therefore, the first
through 2 * 362880 numbers begin with 0 or 1. The millionth number
is the 1000000 - 2 * 362880 = 274240th number which begins with 2.

Therefore we know that the first digit of the answer is two, and
that a two cannot appear again. This makes our calculations easier.
We find the 274240th unique-digits number formed out of the list
[0,1,3,4,5,6,7,8,9]. That is our answer.
"""

def __init__(self,A,B):
"""
>>> A = [[i] for i in range(10)]
>>> B = A
>>> u = UniqueProduct(A,B)
>>> len(u.permutationList)
90
>>> A = [[1, 4],[3,5]]
>>> B = [[i] for i in range(10)]
>>> u = UniqueProduct(A,B)
>>> len(u.permutationList)
16


"""

self.permutationList = []
for n in uniqueCartesianProduct(A,B):
self.permutationList += [n]


def testForUniqueness(a,b):
"""Tests whether any element of row a has
value of singleton vector b
>>> a = [1,2,3]
>>> b = [1]
>>> testForUniqueness(a,b)
False
>>> b = [0]
>>> testForUniqueness(a,b)
True

"""
for ii in range(len(a)):
if a[ii] == b[0]:
return False
return True

def uniqueCartesianProduct(A,B):
for i in range(len(A)):
for j in range(len(B)):
if testForUniqueness(A[i],B[j]):
yield A[i] + B[j]

B = [[0],[1],[3],[4],[5],[6],[7],[8],[9]]
M1 = B
u = UniqueProduct(M1,B)
M2 = u.permutationList
u = UniqueProduct(M2,B)
M3 = u.permutationList
u = UniqueProduct(M3,B)
M4 = u.permutationList
u = UniqueProduct(M4,B)
M5 = u.permutationList
u = UniqueProduct(M5,B)
M6 = u.permutationList
u = UniqueProduct(M6,B)
M7 = u.permutationList
u = UniqueProduct(M7,B)
M8 = u.permutationList
u = UniqueProduct(M8,B)
M9 = u.permutationList
# The 274240th number has the index 2742439.
print([2] + M9[274239])








print "Started at: ", starttime, " Ended at: ",time.asctime()

if __name__ == "__main__":
import doctest
doctest.testmod()

Project Euler Problem 23 Abundant Numbers

# -*- coding: utf-8 -*-
"""
<+ MODULE_NAME +>
Project Euler Problem Set
<+ DESCRIPTION +>
Solutions in Python to the problems at http://projecteuler.net

Licensed under the Creative Commons license; see http://creativecommons.org for more details. In short, this means you can freely reuse, modify and distribute this program, also commercially, for as long you provide a proper attribution.

Copyright by Jonathan Mark, jonathanmark.com/aristede.com, jmark@aristede.com

>>> print 881 + 1
882

"""
import time

class Abundant:
""" Class for solving Project Euler project 23"""

def __init__(self):
print time.asctime()
self.abundants = filter(self.abundantQ, range(1,20162))
self.abundantSums = [1 for n in range(20162)]


def abundantQ(self,n):
if n < sum(filter(lambda i: n%i == 0, range(1,n/2 + 1))):
return True
else:
return False

a = Abundant()
final = len(a.abundants)
for i in range(final/2 + 1):
for j in range(i,final):
absum = a.abundants[i] + a.abundants[j]
if absum >= 20162:
break
else:
a.abundantSums[absum] = 0

print sum([n*a.abundantSums[n] for n in range(len(a.abundantSums))])
print time.asctime()

if __name__ == "__main__":
import doctest
doctest.testmod()

Project Euler Problem 22

[root@www ~]# python twentytwo.py
871198282
Started at: Wed Sep 17 10:00:57 2008 Ended at: Wed Sep 17 10:00:57 2008
[root@www ~]# cat twentytwo.py
# -*- coding: utf-8 -*-
"""
<+ MODULE_NAME +>
Project Euler Problem Set
<+ DESCRIPTION +>
Solutions in Python to the problems at http://projecteuler.net

Licensed under the Creative Commons license; see http://creativecommons.org for more details. In short, this means you can freely reuse, modify and distribute this program, also commercially, for as long you provide a proper attribution.

Copyright by Jonathan Mark, jonathanmark.com/aristede.com, jmark@aristede.com

>>> print 881 + 1
882

"""
import time
starttime = time.asctime()

class Namescore:
"""A class for solving problem 22 in Project Euler"""
def __init__(self, filename):
"""Reads names from file
"""
f=open(filename, 'r')
self.sL = eval("[" + f.read() + "]")

def length(self):
"""returns number of names

>>> name = Namescore('names.txt')
>>> name.length()
5163
"""
return len(self.sL)

def first(self):
"""return first name in file

>>> name = Namescore('names.txt')
>>> name.first()
'MARY'
"""
return self.sL[0]

def last(self):
"""return last name in file

>>> name = Namescore('names.txt')
>>> name.last()
'ALONSO'
"""
return self.sL[len(self.sL) - 1]

def alphabetical_score(self,name):
"""assigns a score of 1 to 26 for each letter a-z
and uses these scores to sum the letters in a name.

>>> name = Namescore('names.txt')
>>> name.alphabetical_score('COLIN')
53

>>> name = Namescore('names.txt')
>>> name.alphabetical_score('abcdefgHiJklmnopqrstuvwxyz')
351

"""
name = name.lower()
lookup = {'a':1,'b':2,'c':3,'d':4,'e':5,'f':6,'g':7, 'h':8,'i':9,'j':10,'k':11,'l':12,'m':13,'n':14,'o':15,'p':16, 'q':17,'r':18, 's':19, 't':20, 'u':21, 'v':22, 'w':23, 'x':24, 'y':25, 'z':26 }
total = 0
for i in range(len(name)):
total += lookup[name[i]]
return total



totalVal = 0
name = Namescore('names.txt')
name.sL.sort()
nameVal = map(name.alphabetical_score, name.sL)
for n in range(len(nameVal)):
totalVal += (n+1) * nameVal[n]

print totalVal




print "Started at: ", starttime, " Ended at: ",time.asctime()

if __name__ == "__main__":
import doctest
doctest.testmod()

Problem 21 Project Euler Amicable Numbers

[root@www ~]# python twentyone.py
started at: Tue Sep 16 11:32:37 2008
31626
Ended at: Tue Sep 16 11:33:15 2008
[root@www ~]# cat twentyone.py
# -*- coding: utf-8 -*-
"""
<+ MODULE_NAME +>
Project Euler Problem Set
<+ DESCRIPTION +>
Solutions in Python to the problems at http://projecteuler.net

Licensed under the Creative Commons license; see http://creativecommons.org for more details. In short, this means you can freely reuse, modify and distribute this program, also commercially, for as long you provide a proper attribution.

Copyright by Jonathan Mark, jonathanmark.com/aristede.com, jmark@aristede.com

>>> print 881 + 1
882

"""
import time
starttime = time.asctime()
print "started at: ",starttime
class Numbers:
"""Class for solving Problem 21 in Project Euler"""
def sumFactors(self,n):
"""Function to determine common factors

>>> t = Numbers()
>>> t.sumFactors(28)
28
"""
return sum(filter(lambda i: n%i == 0,range(1,n/2 + 1)))

def amicable(self,n,m):
""" Function to test for amicable pairs

>>> t = Numbers()
>>> t.amicable(220,284)
True

>>> t = Numbers()
>>> t.amicable(284,220)
True

>>> t = Numbers()
>>> t.amicable(6,6)
False

>>> t = Numbers()
>>> t.amicable(8,7)
False

"""
return (self.sumFactors(n) == m) and (self.sumFactors(m) == n) and (n != m)

def filterNonAmicable(self,seq):
""" Function to remove non-members of amicable pairs

>>> t = Numbers()
>>> t.filterNonAmicable(range(219,222))
[220]

>>> t = Numbers()
>>> t.filterNonAmicable(range(4))
[]
"""

return filter(lambda i: self.amicable(i,self.sumFactors(i)),seq)

t = Numbers()
print sum(t.filterNonAmicable(range(10000)))


print "Ended at: ",time.asctime()

if __name__ == "__main__":
import doctest
doctest.testmod()

Project Euler 20 sum of digits in 100!

[root@www ~]# python twenty.py
648
[root@www ~]# cat twenty.py
def factorial(n):
if n == 1:
return 1
else:
return n * factorial(n-1)

s = str(factorial(100))
l = [int(s[i]) for i in range(len(s))]
print sum(l)

19 Euler first days of month = sundays.

import calendar
days = [calendar.weekday(y,m,1) for y in range(1901,2001) for m in range(1,13)]
def sundays(n):
... return n == 6
...
onlyOnSundays = filter(sundays, days)
>>> len(onlyOnSundays)
171

Project Euler Problem 67 shortest path

/home/user> python sixtyseven.py
7273
/home/user> cat sixtyseven.py
class TriangleMatrix:
def __init__(self):
self.memoized = {}
self.triangle=[]
self.triangle += [[59]]
self.triangle += [[73,0,41]]
self.triangle += [[52,0,40,0,9]]
self.triangle += [[26,0,53,0,6,0,34]]
self.triangle += [[10,0,51,0,87,0,86,0,81]]
self.triangle += [[61,0,95,0,66,0,57,0,25,0,68]]
self.triangle += [[90,0,81,0,80,0,38,0,92,0,67,0,73]]
self.triangle += [[30,0,28,0,51,0,76,0,81,0,18,0,75,0,44]]
self.triangle += [[84,0,14,0,95,0,87,0,62,0,81,0,17,0,78,0,58]]
self.triangle += [[21,0,46,0,71,0,58,0,2,0,79,0,62,0,39,0,31,0,9]]
self.triangle += [[56,0,34,0,35,0,53,0,78,0,31,0,81,0,18,0,90,0,93,0,15]]
self.triangle += [[78,0,53,0,4,0,21,0,84,0,93,0,32,0,13,0,97,0,11,0,37,0,51]]
self.triangle += [[45,0,3,0,81,0,79,0,5,0,18,0,78,0,86,0,13,0,30,0,63,0,99,0,95]]
self.triangle += [[39,0,87,0,96,0,28,0,3,0,38,0,42,0,17,0,82,0,87,0,58,0,7,0,22,0,57]]
self.triangle += [[6,0,17,0,51,0,17,0,7,0,93,0,9,0,7,0,75,0,97,0,95,0,78,0,87,0,8,0,53]]
self.triangle += [[67,0,66,0,59,0,60,0,88,0,99,0,94,0,65,0,55,0,77,0,55,0,34,0,27,0,53,0,78,0,28]]
self.triangle += [[76,0,40,0,41,0,4,0,87,0,16,0,9,0,42,0,75,0,69,0,23,0,97,0,30,0,60,0,10,0,79,0,87]]
self.triangle += [[12,0,10,0,44,0,26,0,21,0,36,0,32,0,84,0,98,0,60,0,13,0,12,0,36,0,16,0,63,0,31,0,91,0,35]]
self.triangle += [[70,0,39,0,6,0,5,0,55,0,27,0,38,0,48,0,28,0,22,0,34,0,35,0,62,0,62,0,15,0,14,0,94,0,89,0,86]]
self.triangle += [[66,0,56,0,68,0,84,0,96,0,21,0,34,0,34,0,34,0,81,0,62,0,40,0,65,0,54,0,62,0,5,0,98,0,3,0,2,0,60]]
self.triangle += [[38,0,89,0,46,0,37,0,99,0,54,0,34,0,53,0,36,0,14,0,70,0,26,0,2,0,90,0,45,0,13,0,31,0,61,0,83,0,73,0,47]]
self.triangle += [[36,0,10,0,63,0,96,0,60,0,49,0,41,0,5,0,37,0,42,0,14,0,58,0,84,0,93,0,96,0,17,0,9,0,43,0,5,0,43,0,6,0,59]]
self.triangle += [[66,0,57,0,87,0,57,0,61,0,28,0,37,0,51,0,84,0,73,0,79,0,15,0,39,0,95,0,88,0,87,0,43,0,39,0,11,0,86,0,77,0,74,0,18]]
self.triangle += [[54,0,42,0,5,0,79,0,30,0,49,0,99,0,73,0,46,0,37,0,50,0,2,0,45,0,9,0,54,0,52,0,27,0,95,0,27,0,65,0,19,0,45,0,26,0,45]]
self.triangle += [[71,0,39,0,17,0,78,0,76,0,29,0,52,0,90,0,18,0,99,0,78,0,19,0,35,0,62,0,71,0,19,0,23,0,65,0,93,0,85,0,49,0,33,0,75,0,9,0,2]]
self.triangle += [[33,0,24,0,47,0,61,0,60,0,55,0,32,0,88,0,57,0,55,0,91,0,54,0,46,0,57,0,7,0,77,0,98,0,52,0,80,0,99,0,24,0,25,0,46,0,78,0,79,0,5]]
self.triangle += [[92,0,9,0,13,0,55,0,10,0,67,0,26,0,78,0,76,0,82,0,63,0,49,0,51,0,31,0,24,0,68,0,5,0,57,0,7,0,54,0,69,0,21,0,67,0,43,0,17,0,63,0,12]]
self.triangle += [[24,0,59,0,6,0,8,0,98,0,74,0,66,0,26,0,61,0,60,0,13,0,3,0,9,0,9,0,24,0,30,0,71,0,8,0,88,0,70,0,72,0,70,0,29,0,90,0,11,0,82,0,41,0,34]]
self.triangle += [[66,0,82,0,67,0,4,0,36,0,60,0,92,0,77,0,91,0,85,0,62,0,49,0,59,0,61,0,30,0,90,0,29,0,94,0,26,0,41,0,89,0,4,0,53,0,22,0,83,0,41,0,9,0,74,0,90]]
self.triangle += [[48,0,28,0,26,0,37,0,28,0,52,0,77,0,26,0,51,0,32,0,18,0,98,0,79,0,36,0,62,0,13,0,17,0,8,0,19,0,54,0,89,0,29,0,73,0,68,0,42,0,14,0,8,0,16,0,70,0,37]]
self.triangle += [[37,0,60,0,69,0,70,0,72,0,71,0,9,0,59,0,13,0,60,0,38,0,13,0,57,0,36,0,9,0,30,0,43,0,89,0,30,0,39,0,15,0,2,0,44,0,73,0,5,0,73,0,26,0,63,0,56,0,86,0,12]]
self.triangle += [[55,0,55,0,85,0,50,0,62,0,99,0,84,0,77,0,28,0,85,0,3,0,21,0,27,0,22,0,19,0,26,0,82,0,69,0,54,0,4,0,13,0,7,0,85,0,14,0,1,0,15,0,70,0,59,0,89,0,95,0,10,0,19]]
self.triangle += [[04,0,9,0,31,0,92,0,91,0,38,0,92,0,86,0,98,0,75,0,21,0,5,0,64,0,42,0,62,0,84,0,36,0,20,0,73,0,42,0,21,0,23,0,22,0,51,0,51,0,79,0,25,0,45,0,85,0,53,0,3,0,43,0,22]]
self.triangle += [[75,0,63,0,2,0,49,0,14,0,12,0,89,0,14,0,60,0,78,0,92,0,16,0,44,0,82,0,38,0,30,0,72,0,11,0,46,0,52,0,90,0,27,0,8,0,65,0,78,0,3,0,85,0,41,0,57,0,79,0,39,0,52,0,33,0,48]]
self.triangle += [[78,0,27,0,56,0,56,0,39,0,13,0,19,0,43,0,86,0,72,0,58,0,95,0,39,0,7,0,4,0,34,0,21,0,98,0,39,0,15,0,39,0,84,0,89,0,69,0,84,0,46,0,37,0,57,0,59,0,35,0,59,0,50,0,26,0,15,0,93]]
self.triangle += [[42,0,89,0,36,0,27,0,78,0,91,0,24,0,11,0,17,0,41,0,5,0,94,0,7,0,69,0,51,0,96,0,3,0,96,0,47,0,90,0,90,0,45,0,91,0,20,0,50,0,56,0,10,0,32,0,36,0,49,0,4,0,53,0,85,0,92,0,25,0,65]]
self.triangle += [[52,0,9,0,61,0,30,0,61,0,97,0,66,0,21,0,96,0,92,0,98,0,90,0,6,0,34,0,96,0,60,0,32,0,69,0,68,0,33,0,75,0,84,0,18,0,31,0,71,0,50,0,84,0,63,0,3,0,3,0,19,0,11,0,28,0,42,0,75,0,45,0,45]]
self.triangle += [[61,0,31,0,61,0,68,0,96,0,34,0,49,0,39,0,5,0,71,0,76,0,59,0,62,0,67,0,6,0,47,0,96,0,99,0,34,0,21,0,32,0,47,0,52,0,7,0,71,0,60,0,42,0,72,0,94,0,56,0,82,0,83,0,84,0,40,0,94,0,87,0,82,0,46]]
self.triangle += [[1,0,20,0,60,0,14,0,17,0,38,0,26,0,78,0,66,0,81,0,45,0,95,0,18,0,51,0,98,0,81,0,48,0,16,0,53,0,88,0,37,0,52,0,69,0,95,0,72,0,93,0,22,0,34,0,98,0,20,0,54,0,27,0,73,0,61,0,56,0,63,0,60,0,34,0,63]]
self.triangle += [[93,0,42,0,94,0,83,0,47,0,61,0,27,0,51,0,79,0,79,0,45,0,1,0,44,0,73,0,31,0,70,0,83,0,42,0,88,0,25,0,53,0,51,0,30,0,15,0,65,0,94,0,80,0,44,0,61,0,84,0,12,0,77,0,2,0,62,0,2,0,65,0,94,0,42,0,14,0,94]]
self.triangle += [[32,0,73,0,9,0,67,0,68,0,29,0,74,0,98,0,10,0,19,0,85,0,48,0,38,0,31,0,85,0,67,0,53,0,93,0,93,0,77,0,47,0,67,0,39,0,72,0,94,0,53,0,18,0,43,0,77,0,40,0,78,0,32,0,29,0,59,0,24,0,6,0,2,0,83,0,50,0,60,0,66]]
self.triangle += [[32,0,1,0,44,0,30,0,16,0,51,0,15,0,81,0,98,0,15,0,10,0,62,0,86,0,79,0,50,0,62,0,45,0,60,0,70,0,38,0,31,0,85,0,65,0,61,0,64,0,6,0,69,0,84,0,14,0,22,0,56,0,43,0,9,0,48,0,66,0,69,0,83,0,91,0,60,0,40,0,36,0,61]]
self.triangle += [[92,0,48,0,22,0,99,0,15,0,95,0,64,0,43,0,1,0,16,0,94,0,2,0,99,0,19,0,17,0,69,0,11,0,58,0,97,0,56,0,89,0,31,0,77,0,45,0,67,0,96,0,12,0,73,0,8,0,20,0,36,0,47,0,81,0,44,0,50,0,64,0,68,0,85,0,40,0,81,0,85,0,52,0,9]]
self.triangle += [[91,0,35,0,92,0,45,0,32,0,84,0,62,0,15,0,19,0,64,0,21,0,66,0,6,0,1,0,52,0,80,0,62,0,59,0,12,0,25,0,88,0,28,0,91,0,50,0,40,0,16,0,22,0,99,0,92,0,79,0,87,0,51,0,21,0,77,0,74,0,77,0,7,0,42,0,38,0,42,0,74,0,83,0,2,0,5]]
self.triangle += [[46,0,19,0,77,0,66,0,24,0,18,0,5,0,32,0,2,0,84,0,31,0,99,0,92,0,58,0,96,0,72,0,91,0,36,0,62,0,99,0,55,0,29,0,53,0,42,0,12,0,37,0,26,0,58,0,89,0,50,0,66,0,19,0,82,0,75,0,12,0,48,0,24,0,87,0,91,0,85,0,2,0,7,0,3,0,76,0,86]]
self.triangle += [[99,0,98,0,84,0,93,0,7,0,17,0,33,0,61,0,92,0,20,0,66,0,60,0,24,0,66,0,40,0,30,0,67,0,5,0,37,0,29,0,24,0,96,0,3,0,27,0,70,0,62,0,13,0,4,0,45,0,47,0,59,0,88,0,43,0,20,0,66,0,15,0,46,0,92,0,30,0,4,0,71,0,66,0,78,0,70,0,53,0,99]]
self.triangle += [[67,0,60,0,38,0,6,0,88,0,4,0,17,0,72,0,10,0,99,0,71,0,7,0,42,0,25,0,54,0,5,0,26,0,64,0,91,0,50,0,45,0,71,0,6,0,30,0,67,0,48,0,69,0,82,0,8,0,56,0,80,0,67,0,18,0,46,0,66,0,63,0,1,0,20,0,8,0,80,0,47,0,7,0,91,0,16,0,3,0,79,0,87]]
self.triangle += [[18,0,54,0,78,0,49,0,80,0,48,0,77,0,40,0,68,0,23,0,60,0,88,0,58,0,80,0,33,0,57,0,11,0,69,0,55,0,53,0,64,0,2,0,94,0,49,0,60,0,92,0,16,0,35,0,81,0,21,0,82,0,96,0,25,0,24,0,96,0,18,0,2,0,5,0,49,0,3,0,50,0,77,0,6,0,32,0,84,0,27,0,18,0,38]]
self.triangle += [[68,0,1,0,50,0,4,0,3,0,21,0,42,0,94,0,53,0,24,0,89,0,5,0,92,0,26,0,52,0,36,0,68,0,11,0,85,0,1,0,4,0,42,0,2,0,45,0,15,0,6,0,50,0,4,0,53,0,73,0,25,0,74,0,81,0,88,0,98,0,21,0,67,0,84,0,79,0,97,0,99,0,20,0,95,0,4,0,40,0,46,0,2,0,58,0,87]]
self.triangle += [[94,0,10,0,2,0,78,0,88,0,52,0,21,0,3,0,88,0,60,0,6,0,53,0,49,0,71,0,20,0,91,0,12,0,65,0,7,0,49,0,21,0,22,0,11,0,41,0,58,0,99,0,36,0,16,0,9,0,48,0,17,0,24,0,52,0,36,0,23,0,15,0,72,0,16,0,84,0,56,0,2,0,99,0,43,0,76,0,81,0,71,0,29,0,39,0,49,0,17]]
self.triangle += [[64,0,39,0,59,0,84,0,86,0,16,0,17,0,66,0,3,0,9,0,43,0,6,0,64,0,18,0,63,0,29,0,68,0,6,0,23,0,7,0,87,0,14,0,26,0,35,0,17,0,12,0,98,0,41,0,53,0,64,0,78,0,18,0,98,0,27,0,28,0,84,0,80,0,67,0,75,0,62,0,10,0,11,0,76,0,90,0,54,0,10,0,5,0,54,0,41,0,39,0,66]]
self.triangle += [[43,0,83,0,18,0,37,0,32,0,31,0,52,0,29,0,95,0,47,0,8,0,76,0,35,0,11,0,4,0,53,0,35,0,43,0,34,0,10,0,52,0,57,0,12,0,36,0,20,0,39,0,40,0,55,0,78,0,44,0,7,0,31,0,38,0,26,0,8,0,15,0,56,0,88,0,86,0,1,0,52,0,62,0,10,0,24,0,32,0,5,0,60,0,65,0,53,0,28,0,57,0,99]]
self.triangle += [[3,0,50,0,3,0,52,0,7,0,73,0,49,0,92,0,66,0,80,0,1,0,46,0,8,0,67,0,25,0,36,0,73,0,93,0,7,0,42,0,25,0,53,0,13,0,96,0,76,0,83,0,87,0,90,0,54,0,89,0,78,0,22,0,78,0,91,0,73,0,51,0,69,0,9,0,79,0,94,0,83,0,53,0,9,0,40,0,69,0,62,0,10,0,79,0,49,0,47,0,3,0,81,0,30]]
self.triangle += [[71,0,54,0,73,0,33,0,51,0,76,0,59,0,54,0,79,0,37,0,56,0,45,0,84,0,17,0,62,0,21,0,98,0,69,0,41,0,95,0,65,0,24,0,39,0,37,0,62,0,3,0,24,0,48,0,54,0,64,0,46,0,82,0,71,0,78,0,33,0,67,0,9,0,16,0,96,0,68,0,52,0,74,0,79,0,68,0,32,0,21,0,13,0,78,0,96,0,60,0,9,0,69,0,20,0,36]]
self.triangle += [[73,0,26,0,21,0,44,0,46,0,38,0,17,0,83,0,65,0,98,0,7,0,23,0,52,0,46,0,61,0,97,0,33,0,13,0,60,0,31,0,70,0,15,0,36,0,77,0,31,0,58,0,56,0,93,0,75,0,68,0,21,0,36,0,69,0,53,0,90,0,75,0,25,0,82,0,39,0,50,0,65,0,94,0,29,0,30,0,11,0,33,0,11,0,13,0,96,0,2,0,56,0,47,0,7,0,49,0,2]]
self.triangle += [[76,0,46,0,73,0,30,0,10,0,20,0,60,0,70,0,14,0,56,0,34,0,26,0,37,0,39,0,48,0,24,0,55,0,76,0,84,0,91,0,39,0,86,0,95,0,61,0,50,0,14,0,53,0,93,0,64,0,67,0,37,0,31,0,10,0,84,0,42,0,70,0,48,0,20,0,10,0,72,0,60,0,61,0,84,0,79,0,69,0,65,0,99,0,73,0,89,0,25,0,85,0,48,0,92,0,56,0,97,0,16]]
self.triangle += [[03,0,14,0,80,0,27,0,22,0,30,0,44,0,27,0,67,0,75,0,79,0,32,0,51,0,54,0,81,0,29,0,65,0,14,0,19,0,4,0,13,0,82,0,4,0,91,0,43,0,40,0,12,0,52,0,29,0,99,0,7,0,76,0,60,0,25,0,1,0,7,0,61,0,71,0,37,0,92,0,40,0,47,0,99,0,66,0,57,0,1,0,43,0,44,0,22,0,40,0,53,0,53,0,9,0,69,0,26,0,81,0,7]]
self.triangle += [[49,0,80,0,56,0,90,0,93,0,87,0,47,0,13,0,75,0,28,0,87,0,23,0,72,0,79,0,32,0,18,0,27,0,20,0,28,0,10,0,37,0,59,0,21,0,18,0,70,0,4,0,79,0,96,0,3,0,31,0,45,0,71,0,81,0,6,0,14,0,18,0,17,0,5,0,31,0,50,0,92,0,79,0,23,0,47,0,9,0,39,0,47,0,91,0,43,0,54,0,69,0,47,0,42,0,95,0,62,0,46,0,32,0,85]]
self.triangle += [[37,0,18,0,62,0,85,0,87,0,28,0,64,0,5,0,77,0,51,0,47,0,26,0,30,0,65,0,5,0,70,0,65,0,75,0,59,0,80,0,42,0,52,0,25,0,20,0,44,0,10,0,92,0,17,0,71,0,95,0,52,0,14,0,77,0,13,0,24,0,55,0,11,0,65,0,26,0,91,0,1,0,30,0,63,0,15,0,49,0,48,0,41,0,17,0,67,0,47,0,3,0,68,0,20,0,90,0,98,0,32,0,4,0,40,0,68]]
self.triangle += [[90,0,51,0,58,0,60,0,6,0,55,0,23,0,68,0,5,0,19,0,76,0,94,0,82,0,36,0,96,0,43,0,38,0,90,0,87,0,28,0,33,0,83,0,5,0,17,0,70,0,83,0,96,0,93,0,6,0,4,0,78,0,47,0,80,0,6,0,23,0,84,0,75,0,23,0,87,0,72,0,99,0,14,0,50,0,98,0,92,0,38,0,90,0,64,0,61,0,58,0,76,0,94,0,36,0,66,0,87,0,80,0,51,0,35,0,61,0,38]]
self.triangle += [[57,0,95,0,64,0,6,0,53,0,36,0,82,0,51,0,40,0,33,0,47,0,14,0,7,0,98,0,78,0,65,0,39,0,58,0,53,0,6,0,50,0,53,0,4,0,69,0,40,0,68,0,36,0,69,0,75,0,78,0,75,0,60,0,3,0,32,0,39,0,24,0,74,0,47,0,26,0,90,0,13,0,40,0,44,0,71,0,90,0,76,0,51,0,24,0,36,0,50,0,25,0,45,0,70,0,80,0,61,0,80,0,61,0,43,0,90,0,64,0,11]]
self.triangle += [[18,0,29,0,86,0,56,0,68,0,42,0,79,0,10,0,42,0,44,0,30,0,12,0,96,0,18,0,23,0,18,0,52,0,59,0,2,0,99,0,67,0,46,0,60,0,86,0,43,0,38,0,55,0,17,0,44,0,93,0,42,0,21,0,55,0,14,0,47,0,34,0,55,0,16,0,49,0,24,0,23,0,29,0,96,0,51,0,55,0,10,0,46,0,53,0,27,0,92,0,27,0,46,0,63,0,57,0,30,0,65,0,43,0,27,0,21,0,20,0,24,0,83]]
self.triangle += [[81,0,72,0,93,0,19,0,69,0,52,0,48,0,1,0,13,0,83,0,92,0,69,0,20,0,48,0,69,0,59,0,20,0,62,0,5,0,42,0,28,0,89,0,90,0,99,0,32,0,72,0,84,0,17,0,8,0,87,0,36,0,3,0,60,0,31,0,36,0,36,0,81,0,26,0,97,0,36,0,48,0,54,0,56,0,56,0,27,0,16,0,91,0,8,0,23,0,11,0,87,0,99,0,33,0,47,0,2,0,14,0,44,0,73,0,70,0,99,0,43,0,35,0,33]]
self.triangle += [[90,0,56,0,61,0,86,0,56,0,12,0,70,0,59,0,63,0,32,0,1,0,15,0,81,0,47,0,71,0,76,0,95,0,32,0,65,0,80,0,54,0,70,0,34,0,51,0,40,0,45,0,33,0,4,0,64,0,55,0,78,0,68,0,88,0,47,0,31,0,47,0,68,0,87,0,3,0,84,0,23,0,44,0,89,0,72,0,35,0,8,0,31,0,76,0,63,0,26,0,90,0,85,0,96,0,67,0,65,0,91,0,19,0,14,0,17,0,86,0,4,0,71,0,32,0,95]]
self.triangle += [[37,0,13,0,4,0,22,0,64,0,37,0,37,0,28,0,56,0,62,0,86,0,33,0,7,0,37,0,10,0,44,0,52,0,82,0,52,0,6,0,19,0,52,0,57,0,75,0,90,0,26,0,91,0,24,0,6,0,21,0,14,0,67,0,76,0,30,0,46,0,14,0,35,0,89,0,89,0,41,0,3,0,64,0,56,0,97,0,87,0,63,0,22,0,34,0,3,0,79,0,17,0,45,0,11,0,53,0,25,0,56,0,96,0,61,0,23,0,18,0,63,0,31,0,37,0,37,0,47]]
self.triangle += [[77,0,23,0,26,0,70,0,72,0,76,0,77,0,4,0,28,0,64,0,71,0,69,0,14,0,85,0,96,0,54,0,95,0,48,0,6,0,62,0,99,0,83,0,86,0,77,0,97,0,75,0,71,0,66,0,30,0,19,0,57,0,90,0,33,0,1,0,60,0,61,0,14,0,12,0,90,0,99,0,32,0,77,0,56,0,41,0,18,0,14,0,87,0,49,0,10,0,14,0,90,0,64,0,18,0,50,0,21,0,74,0,14,0,16,0,88,0,5,0,45,0,73,0,82,0,47,0,74,0,44]]
self.triangle += [[22,0,97,0,41,0,13,0,34,0,31,0,54,0,61,0,56,0,94,0,3,0,24,0,59,0,27,0,98,0,77,0,4,0,9,0,37,0,40,0,12,0,26,0,87,0,9,0,71,0,70,0,7,0,18,0,64,0,57,0,80,0,21,0,12,0,71,0,83,0,94,0,60,0,39,0,73,0,79,0,73,0,19,0,97,0,32,0,64,0,29,0,41,0,7,0,48,0,84,0,85,0,67,0,12,0,74,0,95,0,20,0,24,0,52,0,41,0,67,0,56,0,61,0,29,0,93,0,35,0,72,0,69]]
self.triangle += [[72,0,23,0,63,0,66,0,1,0,11,0,7,0,30,0,52,0,56,0,95,0,16,0,65,0,26,0,83,0,90,0,50,0,74,0,60,0,18,0,16,0,48,0,43,0,77,0,37,0,11,0,99,0,98,0,30,0,94,0,91,0,26,0,62,0,73,0,45,0,12,0,87,0,73,0,47,0,27,0,1,0,88,0,66,0,99,0,21,0,41,0,95,0,80,0,2,0,53,0,23,0,32,0,61,0,48,0,32,0,43,0,43,0,83,0,14,0,66,0,95,0,91,0,19,0,81,0,80,0,67,0,25,0,88]]
self.triangle += [[8,0,62,0,32,0,18,0,92,0,14,0,83,0,71,0,37,0,96,0,11,0,83,0,39,0,99,0,5,0,16,0,23,0,27,0,10,0,67,0,2,0,25,0,44,0,11,0,55,0,31,0,46,0,64,0,41,0,56,0,44,0,74,0,26,0,81,0,51,0,31,0,45,0,85,0,87,0,9,0,81,0,95,0,22,0,28,0,76,0,69,0,46,0,48,0,64,0,87,0,67,0,76,0,27,0,89,0,31,0,11,0,74,0,16,0,62,0,3,0,60,0,94,0,42,0,47,0,9,0,34,0,94,0,93,0,72]]
self.triangle += [[56,0,18,0,90,0,18,0,42,0,17,0,42,0,32,0,14,0,86,0,6,0,53,0,33,0,95,0,99,0,35,0,29,0,15,0,44,0,20,0,49,0,59,0,25,0,54,0,34,0,59,0,84,0,21,0,23,0,54,0,35,0,90,0,78,0,16,0,93,0,13,0,37,0,88,0,54,0,19,0,86,0,67,0,68,0,55,0,66,0,84,0,65,0,42,0,98,0,37,0,87,0,56,0,33,0,28,0,58,0,38,0,28,0,38,0,66,0,27,0,52,0,21,0,81,0,15,0,8,0,22,0,97,0,32,0,85,0,27]]
self.triangle += [[91,0,53,0,40,0,28,0,13,0,34,0,91,0,25,0,1,0,63,0,50,0,37,0,22,0,49,0,71,0,58,0,32,0,28,0,30,0,18,0,68,0,94,0,23,0,83,0,63,0,62,0,94,0,76,0,80,0,41,0,90,0,22,0,82,0,52,0,29,0,12,0,18,0,56,0,10,0,8,0,35,0,14,0,37,0,57,0,23,0,65,0,67,0,40,0,72,0,39,0,93,0,39,0,70,0,89,0,40,0,34,0,7,0,46,0,94,0,22,0,20,0,5,0,53,0,64,0,56,0,30,0,5,0,56,0,61,0,88,0,27]]
self.triangle += [[23,0,95,0,11,0,12,0,37,0,69,0,68,0,24,0,66,0,10,0,87,0,70,0,43,0,50,0,75,0,7,0,62,0,41,0,83,0,58,0,95,0,93,0,89,0,79,0,45,0,39,0,2,0,22,0,5,0,22,0,95,0,43,0,62,0,11,0,68,0,29,0,17,0,40,0,26,0,44,0,25,0,71,0,87,0,16,0,70,0,85,0,19,0,25,0,59,0,94,0,90,0,41,0,41,0,80,0,61,0,70,0,55,0,60,0,84,0,33,0,95,0,76,0,42,0,63,0,15,0,9,0,3,0,40,0,38,0,12,0,3,0,32]]
self.triangle += [[9,0,84,0,56,0,80,0,61,0,55,0,85,0,97,0,16,0,94,0,82,0,94,0,98,0,57,0,84,0,30,0,84,0,48,0,93,0,90,0,71,0,5,0,95,0,90,0,73,0,17,0,30,0,98,0,40,0,64,0,65,0,89,0,7,0,79,0,9,0,19,0,56,0,36,0,42,0,30,0,23,0,69,0,73,0,72,0,7,0,5,0,27,0,61,0,24,0,31,0,43,0,48,0,71,0,84,0,21,0,28,0,26,0,65,0,65,0,59,0,65,0,74,0,77,0,20,0,10,0,81,0,61,0,84,0,95,0,8,0,52,0,23,0,70]]
self.triangle += [[47,0,81,0,28,0,9,0,98,0,51,0,67,0,64,0,35,0,51,0,59,0,36,0,92,0,82,0,77,0,65,0,80,0,24,0,72,0,53,0,22,0,7,0,27,0,10,0,21,0,28,0,30,0,22,0,48,0,82,0,80,0,48,0,56,0,20,0,14,0,43,0,18,0,25,0,50,0,95,0,90,0,31,0,77,0,8,0,9,0,48,0,44,0,80,0,90,0,22,0,93,0,45,0,82,0,17,0,13,0,96,0,25,0,26,0,8,0,73,0,34,0,99,0,6,0,49,0,24,0,6,0,83,0,51,0,40,0,14,0,15,0,10,0,25,0,1]]
self.triangle += [[54,0,25,0,10,0,81,0,30,0,64,0,24,0,74,0,75,0,80,0,36,0,75,0,82,0,60,0,22,0,69,0,72,0,91,0,45,0,67,0,3,0,62,0,79,0,54,0,89,0,74,0,44,0,83,0,64,0,96,0,66,0,73,0,44,0,30,0,74,0,50,0,37,0,5,0,9,0,97,0,70,0,1,0,60,0,46,0,37,0,91,0,39,0,75,0,75,0,18,0,58,0,52,0,72,0,78,0,51,0,81,0,86,0,52,0,8,0,97,0,1,0,46,0,43,0,66,0,98,0,62,0,81,0,18,0,70,0,93,0,73,0,8,0,32,0,46,0,34]]
self.triangle += [[96,0,80,0,82,0,7,0,59,0,71,0,92,0,53,0,19,0,20,0,88,0,66,0,3,0,26,0,26,0,10,0,24,0,27,0,50,0,82,0,94,0,73,0,63,0,8,0,51,0,33,0,22,0,45,0,19,0,13,0,58,0,33,0,90,0,15,0,22,0,50,0,36,0,13,0,55,0,6,0,35,0,47,0,82,0,52,0,33,0,61,0,36,0,27,0,28,0,46,0,98,0,14,0,73,0,20,0,73,0,32,0,16,0,26,0,80,0,53,0,47,0,66,0,76,0,38,0,94,0,45,0,2,0,1,0,22,0,52,0,47,0,96,0,64,0,58,0,52,0,39]]
self.triangle += [[88,0,46,0,23,0,39,0,74,0,63,0,81,0,64,0,20,0,90,0,33,0,33,0,76,0,55,0,58,0,26,0,10,0,46,0,42,0,26,0,74,0,74,0,12,0,83,0,32,0,43,0,9,0,2,0,73,0,55,0,86,0,54,0,85,0,34,0,28,0,23,0,29,0,79,0,91,0,62,0,47,0,41,0,82,0,87,0,99,0,22,0,48,0,90,0,20,0,5,0,96,0,75,0,95,0,4,0,43,0,28,0,81,0,39,0,81,0,1,0,28,0,42,0,78,0,25,0,39,0,77,0,90,0,57,0,58,0,98,0,17,0,36,0,73,0,22,0,63,0,74,0,51]]
self.triangle += [[29,0,39,0,74,0,94,0,95,0,78,0,64,0,24,0,38,0,86,0,63,0,87,0,93,0,6,0,70,0,92,0,22,0,16,0,80,0,64,0,29,0,52,0,20,0,27,0,23,0,50,0,14,0,13,0,87,0,15,0,72,0,96,0,81,0,22,0,8,0,49,0,72,0,30,0,70,0,24,0,79,0,31,0,16,0,64,0,59,0,21,0,89,0,34,0,96,0,91,0,48,0,76,0,43,0,53,0,88,0,1,0,57,0,80,0,23,0,81,0,90,0,79,0,58,0,1,0,80,0,87,0,17,0,99,0,86,0,90,0,72,0,63,0,32,0,69,0,14,0,28,0,88,0,69]]
self.triangle += [[37,0,17,0,71,0,95,0,56,0,93,0,71,0,35,0,43,0,45,0,4,0,98,0,92,0,94,0,84,0,96,0,11,0,30,0,31,0,27,0,31,0,60,0,92,0,3,0,48,0,5,0,98,0,91,0,86,0,94,0,35,0,90,0,90,0,8,0,48,0,19,0,33,0,28,0,68,0,37,0,59,0,26,0,65,0,96,0,50,0,68,0,22,0,7,0,9,0,49,0,34,0,31,0,77,0,49,0,43,0,6,0,75,0,17,0,81,0,87,0,61,0,79,0,52,0,26,0,27,0,72,0,29,0,50,0,7,0,98,0,86,0,1,0,17,0,10,0,46,0,64,0,24,0,18,0,56]]
self.triangle += [[51,0,30,0,25,0,94,0,88,0,85,0,79,0,91,0,40,0,33,0,63,0,84,0,49,0,67,0,98,0,92,0,15,0,26,0,75,0,19,0,82,0,5,0,18,0,78,0,65,0,93,0,61,0,48,0,91,0,43,0,59,0,41,0,70,0,51,0,22,0,15,0,92,0,81,0,67,0,91,0,46,0,98,0,11,0,11,0,65,0,31,0,66,0,10,0,98,0,65,0,83,0,21,0,5,0,56,0,5,0,98,0,73,0,67,0,46,0,74,0,69,0,34,0,8,0,30,0,5,0,52,0,7,0,98,0,32,0,95,0,30,0,94,0,65,0,50,0,24,0,63,0,28,0,81,0,99,0,57]]
self.triangle += [[19,0,23,0,61,0,36,0,9,0,89,0,71,0,98,0,65,0,17,0,30,0,29,0,89,0,26,0,79,0,74,0,94,0,11,0,44,0,48,0,97,0,54,0,81,0,55,0,39,0,66,0,69,0,45,0,28,0,47,0,13,0,86,0,15,0,76,0,74,0,70,0,84,0,32,0,36,0,33,0,79,0,20,0,78,0,14,0,41,0,47,0,89,0,28,0,81,0,5,0,99,0,66,0,81,0,86,0,38,0,26,0,6,0,25,0,13,0,60,0,54,0,55,0,23,0,53,0,27,0,5,0,89,0,25,0,23,0,11,0,13,0,54,0,59,0,54,0,56,0,34,0,16,0,24,0,53,0,44,0,6]]
self.triangle += [[13,0,40,0,57,0,72,0,21,0,15,0,60,0,8,0,4,0,19,0,11,0,98,0,34,0,45,0,9,0,97,0,86,0,71,0,3,0,15,0,56,0,19,0,15,0,44,0,97,0,31,0,90,0,4,0,87,0,87,0,76,0,8,0,12,0,30,0,24,0,62,0,84,0,28,0,12,0,85,0,82,0,53,0,99,0,52,0,13,0,94,0,6,0,65,0,97,0,86,0,9,0,50,0,94,0,68,0,69,0,74,0,30,0,67,0,87,0,94,0,63,0,7,0,78,0,27,0,80,0,36,0,69,0,41,0,6,0,92,0,32,0,78,0,37,0,82,0,30,0,5,0,18,0,87,0,99,0,72,0,19,0,99]]
self.triangle += [[44,0,20,0,55,0,77,0,69,0,91,0,27,0,31,0,28,0,81,0,80,0,27,0,2,0,7,0,97,0,23,0,95,0,98,0,12,0,25,0,75,0,29,0,47,0,71,0,7,0,47,0,78,0,39,0,41,0,59,0,27,0,76,0,13,0,15,0,66,0,61,0,68,0,35,0,69,0,86,0,16,0,53,0,67,0,63,0,99,0,85,0,41,0,56,0,8,0,28,0,33,0,40,0,94,0,76,0,90,0,85,0,31,0,70,0,24,0,65,0,84,0,65,0,99,0,82,0,19,0,25,0,54,0,37,0,21,0,46,0,33,0,2,0,52,0,99,0,51,0,33,0,26,0,4,0,87,0,2,0,8,0,18,0,96]]
self.triangle += [[54,0,42,0,61,0,45,0,91,0,6,0,64,0,79,0,80,0,82,0,32,0,16,0,83,0,63,0,42,0,49,0,19,0,78,0,65,0,97,0,40,0,42,0,14,0,61,0,49,0,34,0,4,0,18,0,25,0,98,0,59,0,30,0,82,0,72,0,26,0,88,0,54,0,36,0,21,0,75,0,3,0,88,0,99,0,53,0,46,0,51,0,55,0,78,0,22,0,94,0,34,0,40,0,68,0,87,0,84,0,25,0,30,0,76,0,25,0,8,0,92,0,84,0,42,0,61,0,40,0,38,0,9,0,99,0,40,0,23,0,29,0,39,0,46,0,55,0,10,0,90,0,35,0,84,0,56,0,70,0,63,0,23,0,91,0,39]]
self.triangle += [[52,0,92,0,3,0,71,0,89,0,7,0,9,0,37,0,68,0,66,0,58,0,20,0,44,0,92,0,51,0,56,0,13,0,71,0,79,0,99,0,26,0,37,0,2,0,6,0,16,0,67,0,36,0,52,0,58,0,16,0,79,0,73,0,56,0,60,0,59,0,27,0,44,0,77,0,94,0,82,0,20,0,50,0,98,0,33,0,9,0,87,0,94,0,37,0,40,0,83,0,64,0,83,0,58,0,85,0,17,0,76,0,53,0,2,0,83,0,52,0,22,0,27,0,39,0,20,0,48,0,92,0,45,0,21,0,9,0,42,0,24,0,23,0,12,0,37,0,52,0,28,0,50,0,78,0,79,0,20,0,86,0,62,0,73,0,20,0,59]]
self.triangle += [[54,0,96,0,80,0,15,0,91,0,90,0,99,0,70,0,10,0,9,0,58,0,90,0,93,0,50,0,81,0,99,0,54,0,38,0,36,0,10,0,30,0,11,0,35,0,84,0,16,0,45,0,82,0,18,0,11,0,97,0,36,0,43,0,96,0,79,0,97,0,65,0,40,0,48,0,23,0,19,0,17,0,31,0,64,0,52,0,65,0,65,0,37,0,32,0,65,0,76,0,99,0,79,0,34,0,65,0,79,0,27,0,55,0,33,0,3,0,1,0,33,0,27,0,61,0,28,0,66,0,8,0,4,0,70,0,49,0,46,0,48,0,83,0,1,0,45,0,19,0,96,0,13,0,81,0,14,0,21,0,31,0,79,0,93,0,85,0,50,0,5]]
self.triangle += [[92,0,92,0,48,0,84,0,59,0,98,0,31,0,53,0,23,0,27,0,15,0,22,0,79,0,95,0,24,0,76,0,5,0,79,0,16,0,93,0,97,0,89,0,38,0,89,0,42,0,83,0,2,0,88,0,94,0,95,0,82,0,21,0,1,0,97,0,48,0,39,0,31,0,78,0,9,0,65,0,50,0,56,0,97,0,61,0,1,0,7,0,65,0,27,0,21,0,23,0,14,0,15,0,80,0,97,0,44,0,78,0,49,0,35,0,33,0,45,0,81,0,74,0,34,0,5,0,31,0,57,0,9,0,38,0,94,0,7,0,69,0,54,0,69,0,32,0,65,0,68,0,46,0,68,0,78,0,90,0,24,0,28,0,49,0,51,0,45,0,86,0,35]]
self.triangle += [[41,0,63,0,89,0,76,0,87,0,31,0,86,0,9,0,46,0,14,0,87,0,82,0,22,0,29,0,47,0,16,0,13,0,10,0,70,0,72,0,82,0,95,0,48,0,64,0,58,0,43,0,13,0,75,0,42,0,69,0,21,0,12,0,67,0,13,0,64,0,85,0,58,0,23,0,98,0,9,0,37,0,76,0,5,0,22,0,31,0,12,0,66,0,50,0,29,0,99,0,86,0,72,0,45,0,25,0,10,0,28,0,19,0,6,0,90,0,43,0,29,0,31,0,67,0,79,0,46,0,25,0,74,0,14,0,97,0,35,0,76,0,37,0,65,0,46,0,23,0,82,0,6,0,22,0,30,0,76,0,93,0,66,0,94,0,17,0,96,0,13,0,20,0,72]]
self.triangle += [[63,0,40,0,78,0,8,0,52,0,9,0,90,0,41,0,70,0,28,0,36,0,14,0,46,0,44,0,85,0,96,0,24,0,52,0,58,0,15,0,87,0,37,0,5,0,98,0,99,0,39,0,13,0,61,0,76,0,38,0,44,0,99,0,83,0,74,0,90,0,22,0,53,0,80,0,56,0,98,0,30,0,51,0,63,0,39,0,44,0,30,0,91,0,91,0,4,0,22,0,27,0,73,0,17,0,35,0,53,0,18,0,35,0,45,0,54,0,56,0,27,0,78,0,48,0,13,0,69,0,36,0,44,0,38,0,71,0,25,0,30,0,56,0,15,0,22,0,73,0,43,0,32,0,69,0,59,0,25,0,93,0,83,0,45,0,11,0,34,0,94,0,44,0,39,0,92]]
self.triangle += [[12,0,36,0,56,0,88,0,13,0,96,0,16,0,12,0,55,0,54,0,11,0,47,0,19,0,78,0,17,0,17,0,68,0,81,0,77,0,51,0,42,0,55,0,99,0,85,0,66,0,27,0,81,0,79,0,93,0,42,0,65,0,61,0,69,0,74,0,14,0,1,0,18,0,56,0,12,0,1,0,58,0,37,0,91,0,22,0,42,0,66,0,83,0,25,0,19,0,4,0,96,0,41,0,25,0,45,0,18,0,69,0,96,0,88,0,36,0,93,0,10,0,12,0,98,0,32,0,44,0,83,0,83,0,4,0,72,0,91,0,4,0,27,0,73,0,7,0,34,0,37,0,71,0,60,0,59,0,31,0,1,0,54,0,54,0,44,0,96,0,93,0,83,0,36,0,4,0,45]]
self.triangle += [[30,0,18,0,22,0,20,0,42,0,96,0,65,0,79,0,17,0,41,0,55,0,69,0,94,0,81,0,29,0,80,0,91,0,31,0,85,0,25,0,47,0,26,0,43,0,49,0,2,0,99,0,34,0,67,0,99,0,76,0,16,0,14,0,15,0,93,0,8,0,32,0,99,0,44,0,61,0,77,0,67,0,50,0,43,0,55,0,87,0,55,0,53,0,72,0,17,0,46,0,62,0,25,0,50,0,99,0,73,0,5,0,93,0,48,0,17,0,31,0,70,0,80,0,59,0,9,0,44,0,59,0,45,0,13,0,74,0,66,0,58,0,94,0,87,0,73,0,16,0,14,0,85,0,38,0,74,0,99,0,64,0,23,0,79,0,28,0,71,0,42,0,20,0,37,0,82,0,31,0,23]]
self.triangle += [[51,0,96,0,39,0,65,0,46,0,71,0,56,0,13,0,29,0,68,0,53,0,86,0,45,0,33,0,51,0,49,0,12,0,91,0,21,0,21,0,76,0,85,0,2,0,17,0,98,0,15,0,46,0,12,0,60,0,21,0,88,0,30,0,92,0,83,0,44,0,59,0,42,0,50,0,27,0,88,0,46,0,86,0,94,0,73,0,45,0,54,0,23,0,24,0,14,0,10,0,94,0,21,0,20,0,34,0,23,0,51,0,4,0,83,0,99,0,75,0,90,0,63,0,60,0,16,0,22,0,33,0,83,0,70,0,11,0,32,0,10,0,50,0,29,0,30,0,83,0,46,0,11,0,5,0,31,0,17,0,86,0,42,0,49,0,1,0,44,0,63,0,28,0,60,0,7,0,78,0,95,0,40]]
self.triangle += [[44,0,61,0,89,0,59,0,4,0,49,0,51,0,27,0,69,0,71,0,46,0,76,0,44,0,4,0,9,0,34,0,56,0,39,0,15,0,6,0,94,0,91,0,75,0,90,0,65,0,27,0,56,0,23,0,74,0,6,0,23,0,33,0,36,0,69,0,14,0,39,0,5,0,34,0,35,0,57,0,33,0,22,0,76,0,46,0,56,0,10,0,61,0,65,0,98,0,9,0,16,0,69,0,4,0,62,0,65,0,18,0,99,0,76,0,49,0,18,0,72,0,66,0,73,0,83,0,82,0,40,0,76,0,31,0,89,0,91,0,27,0,88,0,17,0,35,0,41,0,35,0,32,0,51,0,32,0,67,0,52,0,68,0,74,0,85,0,80,0,57,0,7,0,11,0,62,0,66,0,47,0,22,0,67]]
self.triangle += [[65,0,37,0,19,0,97,0,26,0,17,0,16,0,24,0,24,0,17,0,50,0,37,0,64,0,82,0,24,0,36,0,32,0,11,0,68,0,34,0,69,0,31,0,32,0,89,0,79,0,93,0,96,0,68,0,49,0,90,0,14,0,23,0,4,0,4,0,67,0,99,0,81,0,74,0,70,0,74,0,36,0,96,0,68,0,9,0,64,0,39,0,88,0,35,0,54,0,89,0,96,0,58,0,66,0,27,0,88,0,97,0,32,0,14,0,6,0,35,0,78,0,20,0,71,0,6,0,85,0,66,0,57,0,2,0,58,0,91,0,72,0,5,0,29,0,56,0,73,0,48,0,86,0,52,0,9,0,93,0,22,0,57,0,79,0,42,0,12,0,1,0,31,0,68,0,17,0,59,0,63,0,76,0,7,0,77]]
self.triangle += [[73,0,81,0,14,0,13,0,17,0,20,0,11,0,9,0,1,0,83,0,8,0,85,0,91,0,70,0,84,0,63,0,62,0,77,0,37,0,7,0,47,0,1,0,59,0,95,0,39,0,69,0,39,0,21,0,99,0,9,0,87,0,2,0,97,0,16,0,92,0,36,0,74,0,71,0,90,0,66,0,33,0,73,0,73,0,75,0,52,0,91,0,11,0,12,0,26,0,53,0,5,0,26,0,26,0,48,0,61,0,50,0,90,0,65,0,1,0,87,0,42,0,47,0,74,0,35,0,22,0,73,0,24,0,26,0,56,0,70,0,52,0,5,0,48,0,41,0,31,0,18,0,83,0,27,0,21,0,39,0,80,0,85,0,26,0,8,0,44,0,2,0,71,0,7,0,63,0,22,0,5,0,52,0,19,0,8,0,20]]
self.triangle += [[17,0,25,0,21,0,11,0,72,0,93,0,33,0,49,0,64,0,23,0,53,0,82,0,3,0,13,0,91,0,65,0,85,0,2,0,40,0,5,0,42,0,31,0,77,0,42,0,5,0,36,0,6,0,54,0,4,0,58,0,7,0,76,0,87,0,83,0,25,0,57,0,66,0,12,0,74,0,33,0,85,0,37,0,74,0,32,0,20,0,69,0,3,0,97,0,91,0,68,0,82,0,44,0,19,0,14,0,89,0,28,0,85,0,85,0,80,0,53,0,34,0,87,0,58,0,98,0,88,0,78,0,48,0,65,0,98,0,40,0,11,0,57,0,10,0,67,0,70,0,81,0,60,0,79,0,74,0,72,0,97,0,59,0,79,0,47,0,30,0,20,0,54,0,80,0,89,0,91,0,14,0,5,0,33,0,36,0,79,0,39]]
self.triangle += [[60,0,85,0,59,0,39,0,60,0,7,0,57,0,76,0,77,0,92,0,6,0,35,0,15,0,72,0,23,0,41,0,45,0,52,0,95,0,18,0,64,0,79,0,86,0,53,0,56,0,31,0,69,0,11,0,91,0,31,0,84,0,50,0,44,0,82,0,22,0,81,0,41,0,40,0,30,0,42,0,30,0,91,0,48,0,94,0,74,0,76,0,64,0,58,0,74,0,25,0,96,0,57,0,14,0,19,0,3,0,99,0,28,0,83,0,15,0,75,0,99,0,1,0,89,0,85,0,79,0,50,0,3,0,95,0,32,0,67,0,44,0,8,0,7,0,41,0,62,0,64,0,29,0,20,0,14,0,76,0,26,0,55,0,48,0,71,0,69,0,66,0,19,0,72,0,44,0,25,0,14,0,1,0,48,0,74,0,12,0,98,0,7]]
self.triangle += [[64,0,66,0,84,0,24,0,18,0,16,0,27,0,48,0,20,0,14,0,47,0,69,0,30,0,86,0,48,0,40,0,23,0,16,0,61,0,21,0,51,0,50,0,26,0,47,0,35,0,33,0,91,0,28,0,78,0,64,0,43,0,68,0,4,0,79,0,51,0,8,0,19,0,60,0,52,0,95,0,6,0,68,0,46,0,86,0,35,0,97,0,27,0,58,0,4,0,65,0,30,0,58,0,99,0,12,0,12,0,75,0,91,0,39,0,50,0,31,0,42,0,64,0,70,0,4,0,46,0,7,0,98,0,73,0,98,0,93,0,37,0,89,0,77,0,91,0,64,0,71,0,64,0,65,0,66,0,21,0,78,0,62,0,81,0,74,0,42,0,20,0,83,0,70,0,73,0,95,0,78,0,45,0,92,0,27,0,34,0,53,0,71,0,15]]
self.triangle += [[30,0,11,0,85,0,31,0,34,0,71,0,13,0,48,0,5,0,14,0,44,0,3,0,19,0,67,0,23,0,73,0,19,0,57,0,6,0,90,0,94,0,72,0,57,0,69,0,81,0,62,0,59,0,68,0,88,0,57,0,55,0,69,0,49,0,13,0,7,0,87,0,97,0,80,0,89,0,5,0,71,0,5,0,5,0,26,0,38,0,40,0,16,0,62,0,45,0,99,0,18,0,38,0,98,0,24,0,21,0,26,0,62,0,74,0,69,0,4,0,85,0,57,0,77,0,35,0,58,0,67,0,91,0,79,0,79,0,57,0,86,0,28,0,66,0,34,0,72,0,51,0,76,0,78,0,36,0,95,0,63,0,90,0,8,0,78,0,47,0,63,0,45,0,31,0,22,0,70,0,52,0,48,0,79,0,94,0,15,0,77,0,61,0,67,0,68]]
self.triangle += [[23,0,33,0,44,0,81,0,80,0,92,0,93,0,75,0,94,0,88,0,23,0,61,0,39,0,76,0,22,0,3,0,28,0,94,0,32,0,6,0,49,0,65,0,41,0,34,0,18,0,23,0,8,0,47,0,62,0,60,0,3,0,63,0,33,0,13,0,80,0,52,0,31,0,54,0,73,0,43,0,70,0,26,0,16,0,69,0,57,0,87,0,83,0,31,0,3,0,93,0,70,0,81,0,47,0,95,0,77,0,44,0,29,0,68,0,39,0,51,0,56,0,59,0,63,0,7,0,25,0,70,0,7,0,77,0,43,0,53,0,64,0,3,0,94,0,42,0,95,0,39,0,18,0,1,0,66,0,21,0,16,0,97,0,20,0,50,0,90,0,16,0,70,0,10,0,95,0,69,0,29,0,6,0,25,0,61,0,41,0,26,0,15,0,59,0,63,0,35]]
for n in range(100):
self.triangle[n] = self.reverseZeroes(n) + self.triangle[n]
def reverseZeroes(self,n):
return [0 for i in range(99 - n)]
def recurse(self,n,m):
if n == 98:
return self.triangle[n][m] + max(self.triangle[99][m-1], self.triangle[99][m +1])
else:
self.memoized[(n,m)] = self.triangle[n][m] + max(self.memoizedRecurse(n+1, m-1), self.memoizedRecurse(n+1, m+1))
return self.memoized[(n,m)]

def memoizedRecurse(self,n,m):
if (n,m) in self.memoized:
return self.memoized[(n,m)]
else:
return self.recurse(n,m)


t = TriangleMatrix()
print t.memoizedRecurse(0,99)

Project Euler Problem 18 shortest path

/home/user> python eighteen.py
1074
/home/user> cat eighteen.py
class TriangleMatrix:
def __init__(self):
self.triangle = []
self.triangle +=[[0,0,0,0,0,0,0,0,0,0,0,0,0,0, 75]]
self.triangle += [[0,0,0,0,0,0,0,0,0,0,0,0,0,95,0, 64]]
self.triangle += [[ 0,0,0,0,0,0,0,0,0,0,0,0,17,0, 47,0, 82]]
self.triangle += [[0,0,0,0,0,0,0,0,0,0,0,18,0, 35,0, 87,0, 10]]
self.triangle += [[0,0,0,0,0,0,0,0,0,0,20,0, 4,0, 82,0, 47,0, 65]]
self.triangle += [[0,0,0,0,0,0,0,0,0,19,0, 1,0, 23,0, 75,0, 3,0, 34]]
self.triangle +=[[ 0,0,0,0,0,0,0,0,88,0, 2,0, 77,0, 73,0, 7,0, 63,0, 67]]
self.triangle += [[0,0,0,0,0,0,0,99,0, 65,0, 4,0, 28,0, 6,0, 16,0, 70,0, 92]]
self.triangle += [[0,0,0,0,0,0,41,0, 41,0, 26,0, 56,0, 83,0, 40,0, 80,0, 70,0, 33]]
self.triangle += [[0,0,0,0,0,41,0, 48,0, 72,0, 33,0, 47,0, 32,0, 37,0, 16,0, 94,0, 29]]
self.triangle +=[[0,0,0,0,53,0, 71,0, 44,0, 65,0, 25,0, 43,0, 91,0, 52,0, 97,0, 51,0, 14]]
self.triangle += [[0,0,0,70,0, 11,0, 33,0, 28,0, 77,0, 73,0, 17,0, 78,0, 39,0, 68,0, 17,0, 57]]
self.triangle += [[0,0,91,0, 71,0, 52,0, 38,0, 17,0, 14,0, 91,0, 43,0, 58,0, 50,0, 27,0, 29,0, 48]]
self.triangle += [[0,63,0, 66,0, 4,0, 68,0, 89,0, 53,0, 67,0, 30,0, 73,0, 16,0, 69,0, 87,0, 40,0, 31]]
self.triangle += [[4,0, 62,0, 98,0, 27,0, 23,0, 9,0, 70,0, 98,0, 73,0, 93,0, 38,0, 53,0, 60,0, 4,0, 23]]

def recurse(self,n,m):
if n == 13:
return self.triangle[n][m] + max(self.triangle[14][m-1], self.triangle[14][m +1])
else:
return self.triangle[n][m] + max(self.recurse(n+1, m-1), self.recurse(n+1, m+1))




t = TriangleMatrix()
print t.recurse(0,14)

Euler Project Problem 17 letter counts

/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)

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

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

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()

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)))

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

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$

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()