Project Euler Problem 34 Factorions

[root@www ~]# python thirtyfour.py
145
40585
Started at: Thu Oct 23 13:20:38 2008 Ended at: Thu Oct 23 13:21:23 2008
[root@www ~]# cat thirtyfour.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()

# 145 is a curious number, as 1! + 4! + 5! = 1 + 24 + 120 = 145.

# Find the sum of all numbers which are equal to the sum of the factorial of their digits.

# Note: as 1! = 1 and 2! = 2 are not sums they are not included.

# An 8 digit number cannot be less than 10,000,000

# Nine factorial is 362880

# So the largest sum-of-factorials which an 8 digit number can have

# is 8 * 362880 = 2903040

# Similarly for 9 or more digits.

# Therefore a curious number can have at most seven digits.

# The largest curious number can be at most 7 * 362880 = 2540160


def factorial(n):
"""
Factorial function

>>> factorial(5)
120

>>> factorial(1)
1

>>> factorial(0)
1

"""
if n < 0:
return -999999
elif n < 2:
return 1
else:
return n * factorial(n - 1)

class precalc:
def __init__(self):
"""
Stores precalculated factorials

>>> x = precalc()
>>> x.ten[0]
1

"""
self.ten = [1] + [factorial(n) for n in range(1,10)]

pc = precalc()
fact = pc.ten

def getFact(n):
"""
Reads precalculated single-digit factorials

>>> getFact(5)
120

>>> getFact(4)
24

>>> getFact(0)
1

>>> getFact(8)
40320


"""

return fact[int(n)]


def sumOfFactorialsHelper(n):
"""
Find the sum of the factorials in each digit of n

>>> sumOfFactorialsHelper(145)
[1, 24, 120]

mathworld.wolfram.com says that there are only four
factorions: 1,2, 145 and 40585

>>> sumOfFactorialsHelper(40585)
[24, 1, 120, 40320, 120]



"""
s = str(n)
digits = [s[i] for i in range(len(s))]
factDigits = map(getFact, digits)
return factDigits

for n in range(10, 2540161):
if sum(sumOfFactorialsHelper(n)) == n:
print n



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

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

Project Euler Problem 33 Curious Fractions

[root@www ~]# python thirtythree.py
[16, 64]
[19, 95]
[26, 65]
[49, 98]
There were 4 curious fractions.
Started at: Sat Oct 18 21:53:18 2008 Ended at: Sat Oct 18 21:53:18 2008
[root@www ~]# cat thirtythree.py
from __future__ import division
"""
<+ 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()

# The fraction 49/98 is a curious fraction,
# as an inexperienced mathematician in attempting to simplify it
# may incorrectly believe that 49/98 = 4/8,

def shortcut(numerator, denominator, n,m):
"""
Tests for a non-zero digit which is in both the two-digit numerator
and the two-digit denominator

>>> shortcut(49, 98, 1,0)
True

>>> shortcut(48,98, 1,0)
False

>>> shortcut(40,80, 1,1)
False

>>> shortcut(77,77,1,1)
False

>>> shortcut(9,99,0,0)
False

>>> shortcut(9,99,0,1)
False

>>> shortcut(11,111, 1,1)
False

"""
if numerator < 10 or numerator > 99 or denominator < 10 or denominator > 99:
return False
if numerator >= denominator:
return False
if str(numerator)[n] == str(denominator)[m]:
if str(numerator)[n] == '0':
return False
else:
return True
else:
return False

def flip(n):
"""
Turns a zero into a one and a one into a zero

>>> flip(0)
1

>>> flip(1)
0

"""

return (n + 1) % 2

def testShortcut(numerator, denominator,n,m):
"""
Tests to see whether applying a shortcut produces
an incorrect answer.

First make sure that Python's division is working properly
>>> 1/2
0.5

>>> testShortcut(49,98,1,0)
[49, 98]

>>> testShortcut(49,98,0,1)
False

>>> testShortcut(49,88,0,0)
False

"""
if shortcut(numerator, denominator, n,m):
num = int(str(numerator)[flip(n)])
den = int(str(denominator)[flip(m)])
if den == 0:
return False
if numerator/denominator == num/den:
return [numerator,denominator]
return False

def countCurious():
"""
returns how many curious numbers there are with two digit
numerators and denominators

"""

count = 0
for numerator in range(10,100):
for denominator in range(numerator,100):
for n in range(2):
for m in range(2):
result = testShortcut(numerator, denominator,n,m)
if result:
print result
count += 1
return "There were " + str(count) + " curious fractions."

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

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

Project Euler Pandigital Numbers Problem 32

[root@www ~]# python thirtytwo.py
45228
Started at: Tue Oct 14 13:38:21 2008 Ended at: Tue Oct 14 13:38:27 2008
[root@www ~]# cat thirtytwo.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()


def testExactlyOnce(s,n):
"""
Returns true if a digit appears exactly once in a string
and the string contains no zeroes

>>> testExactlyOnce('11234567890',1)
False

>>> testExactlyOnce('123456789',0)
False

>>> testExactlyOnce('123456789',9)
True

>>> testExactlyOnce('123450',6)
False

"""

s = str(s)
if s.count(str(0)) > 0:
return False
if s.count(str(n)) == 1:
return True
else:
return False


def concatenate(n1,n2):
"""
Multiplies n1 * n2 and concatenates result to n1 and n2

>>> concatenate(186,39)
'186397254'

"""

return str(n1)+ str(n2) + str(n1*n2)

def testBothPandigital(n):
"""
tests whether a five digit number, when split into
numbers of lengths 4,1 and 3,2, produces Pandigital
numbers

>>> testBothPandigital(18639)
7254

"""
tot = 0
if testPandigital(concatenate(int(str(n)[:4]),int(str(n)[4]))):
tot = int(str(n)[:4]) * int(str(n)[4])
if testPandigital(concatenate(int(str(n)[:3]),int(str(n)[3:]))):
tot = int(str(n)[:3]) * int(str(n)[3:])
return tot

def testPandigital(s):
"""
tests whether n1, n2 and n1*n2 cof concatenate(int(str(n)[:4]),int(str(n)[4]):
contain each of the digits
0 - 9 exactly once.

>>> testPandigital('186397254')
True

>>> testPandigital('2323')
False

"""

for i in range(1,10):
if testExactlyOnce(s,i) == False:
return False
return True

def unique100000():
"""
return a range consisting of all numbers less than 100000
which do not contain any zeroes and in which no digit
appears more than one time.

>>> len(unique100000())
15120

"""

numbers = []
for n in range(11111,100000):
unique = True
for i in range(len(str(n))):
if not testExactlyOnce(str(n), int(str(n)[i])):
unique = False
if str(n).count('0') > 0:
unique = False
if unique:
numbers.append(n)
return numbers

final ={}

for n in unique100000():
if testBothPandigital(n) > 1111:
final[testBothPandigital(n)] = 0
print sum(final.keys())


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

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

Problem 31 Project Euler British currency combinations

[root@www ~]# python thirtyone.py
73682
Started at: Sun Oct 12 18:26:02 2008 Ended at: Sun Oct 12 18:26:02 2008
[root@www ~]# cat thirtyone.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()
count = 0
# 2p, 5p, 10p, 20p, 50p, £1 (100p) and £2 (200p).
for p5 in range(41):
for p10 in range (21):
for p20 in range(11):
for p50 in range(5):
for p100 in range(3):
for p200 in range(2):
sum = p5*5 + p10*10 + p20*20 + p50*50 + p100*100 + p200*200
if (sum <= 200):
count += (200 -sum)//2 + 1

print count


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

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

Project Euler Sum Of Powers Problem 30

[root@www ~]# python thirty.py
4150
4151
54748
92727
93084
194979
The total is 443839
Started at: Sat Oct 11 10:53:50 2008 Ended at: Sat Oct 11 10:54:01 2008
[root@www ~]# cat thirty.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()

# A 7 digit number must equal at least 1,000,000.
# The sum of the fifth powers of a 7-digit number cannot be
# greater than 7*9**5 equals about 420,000.
# Using similar reasoning n > 7, no number which equals the sum
# of the fifth powers of its digits can have more than six digits.

def sumOfPowers(p,n):
"""takes each digit of a number, raises it to the pth power,
and sums it.

>>> sumOfPowers(5,123)
276

"""

s = str(n)
tot = 0
for i in range(len(s)):
tot += int(s[i])**p
return tot

sum = 0
for n in range(2, 1000000):
if n == sumOfPowers(5,n):
print n
sum += n

print "The total is", sum






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

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

Project Euler 29 Unique Exponentiation

[root@www ~]# python twentynine.py
9183
Started at: Fri Oct 10 20:34:29 2008 Ended at: Fri Oct 10 20:34:29 2008
[root@www ~]# cat twentynine.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()

results = {}

for a in range(2,101):
for b in range(2,101):
results[a**b] = 0

print len(results)





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

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

Project Euler Problem 28 diagonals

root@www ~]# python twentyeight.py
669171001
Started at: Wed Oct 8 22:40:25 2008 Ended at: Wed Oct 8 22:40:25 2008
[root@www ~]# cat twentyeight.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()


def listOddSquare(N):
"""
Returns list of odd squares for the first N odd numbers starting
at 3

>>> sum(listOddSquare(2))
34

>>> sum(listOddSquare(1))
9

"""

x = range(1,(N +1) * 2)
oddSquare = map(lambda x: x * x, x)
oddSquare = filter(lambda x: x % 2 == 1, oddSquare)
oddSquare = oddSquare[1:]
return oddSquare

def listEvenSquarePlusOne(N):
"""
Returns list of square-plus-one for the first N even numbers starting
at 2.

>>> sum(listEvenSquarePlusOne(2))
22

>>> sum(listEvenSquarePlusOne(1))
5

"""
evenSquarePlusOne = filter(lambda x: x % 2 == 0, range(1,(N + 1) * 2 ))
evenSquarePlusOne = map(lambda x: x*x + 1, evenSquarePlusOne)
return evenSquarePlusOne

def listUpperLeft(N):
"""
for returning average of listOddSquare and listEvenSquarePlusOne

>>> upperLeft(2)
28

>>> upperLeft(1)
7

"""


return listOddSquare(N) + listEvenSquarePlusOne(N)

def upperLeft(N):
return sum(listUpperLeft(N))/2

def listLowerRight(N):
"""Returns n-th element of listEvenSquarePlusOne minus n

>>> sum(listLowerRight(2))
16

>>> sum(listLowerRight(1))
3

"""
return [listEvenSquarePlusOne(N)[i] - (2*(i + 1) ) for i in range(N)]

def total(N):
"""Return sum of diagonals except that center is only counted once

>>> total(2)
101


"""

return sum(listEvenSquarePlusOne(N) + listOddSquare(N) + listLowerRight(N)) + upperLeft(N) + 1

print total(500)

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

if __name__ == "__main__":
import doctest
doctest.testmod()
[root@www ~]#

.vimrc for Python

F4 adds boilerplate. Open existing file. Hit F4.
F5 runs program.

map ,p :!python %
autocmd BufRead *.py set makeprg=python\ -c\ \"import\ py_compile,sys;\ sys.stderr=sys.stdout;\ py_compile.compile(r'%')\"
autocmd BufRead *.py set efm=%C\ %.%#,%A\ \ File\ \"%f\"\\,\ line\ %l%.%#,%Z%[%^\ ]%\\@=%m
autocmd BufRead *.py nmap :!python %
autocmd BufRead *.py set tabstop=4
autocmd BufRead *.py set nowrap
autocmd BufRead *.py set go+=b
autocmd BufRead *.py set nu
autocmd BufRead *.py nmap :r $HOME/python.tmpl

Project Euler problem 27 quadratic formula producing primes

[root@www ~]# python twentyseven.py
(-61, 971) -59231
Started at: Sat Oct 4 21:08:48 2008 Ended at: Sat Oct 4 21:08:51 2008
[root@www ~]# cat twentyseven.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

>>> possibleB[len(possibleB)-1:len(possibleB)]
[997]

>>> possibleAB[0]
(-1, 2)

>>> min([ fBool(s,0) for s in possibleAB])
True

>>> min([ fBool(s,1) for s in possibleAB])
True



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

# f(n) = n*n +a*n + b
# when n = 0, b must be prime number < 1000
# when n = 1, a = f(n) - b - 1

possibleB = filter(numbthy.isprime, range(1,1000))
primesLT2000 = filter(numbthy.isprime, range(1,2000))

def possibleA(b):
"""
Values of a for which f(a,b,1) is prime
>>> possibleA(0)[0]
1

"""

return filter( lambda y: abs(y) < 1000 ,[ ((-b - 1) + x) for x in primesLT2000])


possibleAB = []


for b in possibleB:
tempList = possibleA(b)
for a in tempList:
possibleAB.append((a,b))

def f(a,b,n):
return n*n + a*n + b

def fBool(ab,n):
result = f(ab[0],ab[1], n)
if result > 0:
return numbthy.isprime(result)
else:
return False

def fPrimeRun(ab):
"""
>>> fPrimeRun((0,2))
1

"""
n = 0
while fBool(ab, n + 1):
n += 1
return n

longestRun = max([fPrimeRun(ab) for ab in possibleAB])

for ab in possibleAB:
if fPrimeRun(ab) == 70:
print ab, ab[0] * ab[1]


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

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

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

Euler problem #10, sum of primes <2000000

[jmark@www ~]$ python sumofprimes.py
Sun Aug 31 11:36:05 2008
142913828922 Sun Aug 31 11:36:46 2008
[jmark@www ~]$ cat sumofprimes.py
import time
print time.asctime()
primes = []
r = range(2,2000000)
while r[0] < 1415:
primes = primes +[r[0]]
r = filter(lambda n: (n %r[0]) > 0, r)
print sum(r) + sum(primes), time.asctime()

Problem 9 Pythagorean triplet summing to 1000

/home/user> python pythagorus.py
['Sat Aug 30 02:46:51 2008', 200, 375, 425, 'Sat Aug 30 02:47:02 2008']
/home/user> cat pythagorus.py
import time
starttime = time.asctime()
def findPythag():
for c in range(334,1001):
for b in range(0, c):
for a in range(0,b):
if (a*a+b*b==c*c) and (a + b + c == 1000):
return [starttime,a,b,c,time.asctime()]
return "Not Found"

print findPythag()

Euler Problem 8: Find largest product of five consecutive integers

/home/user/python> cat getx.py
"""
>>> print movingProduct(4)
882
"""

x=7316717653133062491922511967442657474235534919493496983520312774506326239578318016984801869478851843858615607891129494954595017379583319528532088055111254069874715852386305071569329096329522744304355766896648950445244523161731856403098711121722383113622298934233803081353362766142828064444866452387493035890729629049156044077239071381051585930796086670172427121883998797908792274921901699720888093776657273330010533678812202354218097512545405947522435258490771167055601360483958644670632441572215539753697817977846174064955149290862569321978468622482839722413756570560574902614079729686524145351004748216637048440319989000889524345065854122758866688116427171479924442928230863465674813919123162824586178664583591245665294765456828489128831426076900422421902267105562632111110937054421750694165896040807198403850962455444362981230987879927244284909188845801561660979191338754992005240636899125607176060588611646710940507754100225698315520005593572972571636269561882670428252483600823257530420752963450

# This script uses the deprecated Python function reduce().
# It will not work in Python 3

x = str(x)
def movingProduct(n):
subRange = [int(x[n - i]) for i in range(5)]
return reduce(lambda a,b: a*b, subRange)

print max(map(movingProduct, range(4,1000)))

if __name__ == "__main__":

import doctest

doctest.testmod()

Problem 7: FInd 10001st prime

# The number of primes less than a number x converges to 1n(x)/x.
# I initially estimated that the 10001st prime would be less than 100000.
# That later turned out to be false and I increased the estimate to 200000.
# Using the Sieve of Eristatothanes

>>> r = range(2,200000)
>>> currentPrime = 2
>>> primes = []
>>> import math
>>> math.sqrt(200000)
447.21359549995793
>>> while currentPrime < 449:
... primes = primes + [currentPrime]
... r = filter(lambda n: (n % currentPrime) > 0, r)
... currentPrime = r[0]
...
>>> len(primes)
86
>>> len(r)
17898
>>> primes[85]
443
>>> r[0]
449
>>> 10001 - 86
9915
>>> r[9914]
104743
>>>

Project Euler Problem #6

difference between square of sum and sum of squares:

>>> (101 * 50 * 101 * 50) - sum(map(lambda x: x * x, range(1,101)))
25164150

Problem #5: find smallest number evenly divisible by all numbers less than 21

# In order for a number to be evenly divisible by all numbers less than 21,
# the number must be evenly divisible by the product of all primes less than 21. Use brute force to # search for all multiples of this product until one which is evenly divisible
# by the non-primes is found.

# The range 11 to 21 contains within it numbers which are evenly divisible by all of the numbers 1 through 10.
# Therefore testing to make sure that a number is evenly divisible by 11 through 21 is sufficient.

>>> primeprod = 2 * 3 * 5 * 7 * 11 * 13 * 17 * 19
>>> def test():
... n = 21
... while (sum(map(lambda i: (n * primeprod) % i,range(11,21) )) > 0):
... n += 1
... return n * primeprod
...
>>> test()
232792560

#4: Find largest palindrome produced by product of three digit numbers

Approach: Create list of palindromes sorted in reverse order. For each palindrome, check to see whether it has a factor between 100 and 1000. Check that the palindrome/factor is also between 100 and 1000.

>>> def findFactor(n):
... for i in range(100, 1000):
... if ( n % i == 0) and ( n//i < 1000):
... return i
... return 1
...

>>> findFactor(999999)
1

>>> def firstFactorable(r):
... for i in r:
... if findFactor(i) > 1:
... return i
... return "None Found"
...


>>> def createPalindrome(n):
... s = str(n)
... return int(s + s[::-1])
...

>>> createPalindrome(123)
123321

>>> def createSequence():
... r = map(createPalindrome, range(100,1000))
... r = r[::-1]
... return r
...
>>> createSequence()
[999999, 998899, 997799, 996699, 995599, 994499, 993399, 992299, 991199, 990099, 989989, 988889, 987789, 986689, 985589, 984489, 983389, 982289, 981189, 980089, 979979, 978879, 977779, 976679, 975579, 974479, 973379, 972279, 971179, 970079, 969969, 968869, 967769, 966669, 965569, 964469, 963369, 962269, 961169, 960069, 959959, 958859, 957759, 956659, 955559, 954459, 953359, 952259, 951159, 950059, 949949, 948849, 947749, 946649, 945549, 944449, 943349, 942249, 941149, 940049, 939939, 938839, 937739, 936639, 935539, 934439, 933339, 932239, 931139, 930039, 929929, 928829, 927729, 926629, 925529, 924429, 923329, 922229, 921129, 920029, 919919, 918819, 917719, 916619, 915519, 914419, 913319, 912219, 911119, 910019, 909909, 908809, 907709, 906609, 905509, 904409, 903309, 902209, 901109, 900009, 899998, 898898, 897798, 896698, 895598, 894498, 893398, 892298, 891198, 890098, 889988, 888888, 887788, 886688, 885588, 884488, 883388, 882288, 881188, 880088, 879978, 878878, 877778, 876678, 875578, 874478, 873378, 872278, 871178, 870078, 869968, 868868, 867768, 866668, 865568, 864468, 863368, 862268, 861168, 860068, 859958, 858858, 857758, 856658, 855558, 854458, 853358, 852258, 851158, 850058, 849948, 848848, 847748, 846648, 845548, 844448, 843348, 842248, 841148, 840048, 839938, 838838, 837738, 836638, 835538, 834438, 833338, 832238, 831138, 830038, 829928, 828828, 827728, 826628, 825528, 824428, 823328, 822228, 821128, 820028, 819918, 818818, 817718, 816618, 815518, 814418, 813318, 812218, 811118, 810018, 809908, 808808, 807708, 806608, 805508, 804408, 803308, 802208, 801108, 800008, 799997, 798897, 797797, 796697, 795597, 794497, 793397, 792297, 791197, 790097, 789987, 788887, 787787, 786687, 785587, 784487, 783387, 782287, 781187, 780087, 779977, 778877, 777777, 776677, 775577, 774477, 773377, 772277, 771177, 770077, 769967, 768867, 767767, 766667, 765567, 764467, 763367, 762267, 761167, 760067, 759957, 758857, 757757, 756657, 755557, 754457, 753357, 752257, 751157, 750057, 749947, 748847, 747747, 746647, 745547, 744447, 743347, 742247, 741147, 740047, 739937, 738837, 737737, 736637, 735537, 734437, 733337, 732237, 731137, 730037, 729927, 728827, 727727, 726627, 725527, 724427, 723327, 722227, 721127, 720027, 719917, 718817, 717717, 716617, 715517, 714417, 713317, 712217, 711117, 710017, 709907, 708807, 707707, 706607, 705507, 704407, 703307, 702207, 701107, 700007, 699996, 698896, 697796, 696696, 695596, 694496, 693396, 692296, 691196, 690096, 689986, 688886, 687786, 686686, 685586, 684486, 683386, 682286, 681186, 680086, 679976, 678876, 677776, 676676, 675576, 674476, 673376, 672276, 671176, 670076, 669966, 668866, 667766, 666666, 665566, 664466, 663366, 662266, 661166, 660066, 659956, 658856, 657756, 656656, 655556, 654456, 653356, 652256, 651156, 650056, 649946, 648846, 647746, 646646, 645546, 644446, 643346, 642246, 641146, 640046, 639936, 638836, 637736, 636636, 635536, 634436, 633336, 632236, 631136, 630036, 629926, 628826, 627726, 626626, 625526, 624426, 623326, 622226, 621126, 620026, 619916, 618816, 617716, 616616, 615516, 614416, 613316, 612216, 611116, 610016, 609906, 608806, 607706, 606606, 605506, 604406, 603306, 602206, 601106, 600006, 599995, 598895, 597795, 596695, 595595, 594495, 593395, 592295, 591195, 590095, 589985, 588885, 587785, 586685, 585585, 584485, 583385, 582285, 581185, 580085, 579975, 578875, 577775, 576675, 575575, 574475, 573375, 572275, 571175, 570075, 569965, 568865, 567765, 566665, 565565, 564465, 563365, 562265, 561165, 560065, 559955, 558855, 557755, 556655, 555555, 554455, 553355, 552255, 551155, 550055, 549945, 548845, 547745, 546645, 545545, 544445, 543345, 542245, 541145, 540045, 539935, 538835, 537735, 536635, 535535, 534435, 533335, 532235, 531135, 530035, 529925, 528825, 527725, 526625, 525525, 524425, 523325, 522225, 521125, 520025, 519915, 518815, 517715, 516615, 515515, 514415, 513315, 512215, 511115, 510015, 509905, 508805, 507705, 506605, 505505, 504405, 503305, 502205, 501105, 500005, 499994, 498894, 497794, 496694, 495594, 494494, 493394, 492294, 491194, 490094, 489984, 488884, 487784, 486684, 485584, 484484, 483384, 482284, 481184, 480084, 479974, 478874, 477774, 476674, 475574, 474474, 473374, 472274, 471174, 470074, 469964, 468864, 467764, 466664, 465564, 464464, 463364, 462264, 461164, 460064, 459954, 458854, 457754, 456654, 455554, 454454, 453354, 452254, 451154, 450054, 449944, 448844, 447744, 446644, 445544, 444444, 443344, 442244, 441144, 440044, 439934, 438834, 437734, 436634, 435534, 434434, 433334, 432234, 431134, 430034, 429924, 428824, 427724, 426624, 425524, 424424, 423324, 422224, 421124, 420024, 419914, 418814, 417714, 416614, 415514, 414414, 413314, 412214, 411114, 410014, 409904, 408804, 407704, 406604, 405504, 404404, 403304, 402204, 401104, 400004, 399993, 398893, 397793, 396693, 395593, 394493, 393393, 392293, 391193, 390093, 389983, 388883, 387783, 386683, 385583, 384483, 383383, 382283, 381183, 380083, 379973, 378873, 377773, 376673, 375573, 374473, 373373, 372273, 371173, 370073, 369963, 368863, 367763, 366663, 365563, 364463, 363363, 362263, 361163, 360063, 359953, 358853, 357753, 356653, 355553, 354453, 353353, 352253, 351153, 350053, 349943, 348843, 347743, 346643, 345543, 344443, 343343, 342243, 341143, 340043, 339933, 338833, 337733, 336633, 335533, 334433, 333333, 332233, 331133, 330033, 329923, 328823, 327723, 326623, 325523, 324423, 323323, 322223, 321123, 320023, 319913, 318813, 317713, 316613, 315513, 314413, 313313, 312213, 311113, 310013, 309903, 308803, 307703, 306603, 305503, 304403, 303303, 302203, 301103, 300003, 299992, 298892, 297792, 296692, 295592, 294492, 293392, 292292, 291192, 290092, 289982, 288882, 287782, 286682, 285582, 284482, 283382, 282282, 281182, 280082, 279972, 278872, 277772, 276672, 275572, 274472, 273372, 272272, 271172, 270072, 269962, 268862, 267762, 266662, 265562, 264462, 263362, 262262, 261162, 260062, 259952, 258852, 257752, 256652, 255552, 254452, 253352, 252252, 251152, 250052, 249942, 248842, 247742, 246642, 245542, 244442, 243342, 242242, 241142, 240042, 239932, 238832, 237732, 236632, 235532, 234432, 233332, 232232, 231132, 230032, 229922, 228822, 227722, 226622, 225522, 224422, 223322, 222222, 221122, 220022, 219912, 218812, 217712, 216612, 215512, 214412, 213312, 212212, 211112, 210012, 209902, 208802, 207702, 206602, 205502, 204402, 203302, 202202, 201102, 200002, 199991, 198891, 197791, 196691, 195591, 194491, 193391, 192291, 191191, 190091, 189981, 188881, 187781, 186681, 185581, 184481, 183381, 182281, 181181, 180081, 179971, 178871, 177771, 176671, 175571, 174471, 173371, 172271, 171171, 170071, 169961, 168861, 167761, 166661, 165561, 164461, 163361, 162261, 161161, 160061, 159951, 158851, 157751, 156651, 155551, 154451, 153351, 152251, 151151, 150051, 149941, 148841, 147741, 146641, 145541, 144441, 143341, 142241, 141141, 140041, 139931, 138831, 137731, 136631, 135531, 134431, 133331, 132231, 131131, 130031, 129921, 128821, 127721, 126621, 125521, 124421, 123321, 122221, 121121, 120021, 119911, 118811, 117711, 116611, 115511, 114411, 113311, 112211, 111111, 110011, 109901, 108801, 107701, 106601, 105501, 104401, 103301, 102201, 101101, 100001]

>>> r = createSequence()

>>> firstFactorable(r)
906609