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