Project Euler

p29.py

#!/usr/bin/env python

def main():
    m = []
    for x in xrange(2,101):
        for y in xrange(2,101):
            c = x**y
            if c not in m:
                m.append(c)
    print len(m)

if __name__ == '__main__':
    main()

p31.py

#!/usr/bin/env python

def main():
    m = 0
    for b in xrange(0,3):
        for c in xrange(0,5):
            for d in xrange(0,11):
                for e in xrange(0,21):
                    for f in xrange(0,41):
                        for g in xrange(0,101):
                            for h in xrange(0,201):
                                v = b*100+c*50+d*20+e*10+f*5+g*2+h
                                if v == 200:
                                    m += 1
                                    print b,c,d,e,f,g,h
                                elif v > 200:
                                    break
    print m+1

if __name__ == '__main__':
    main()                     

p35.py

#!/usr/bin/env python

def main():
    m = []
    for x in xrange(2,1000000):
        if x not in m:
            n = get(x)
            b = True
            for v in xrange(0,len(n)):
                if not isprime(n[v]):
                    b = False
                    break
            if b:
                print n
                m += n
    print m
    print len(m)

def isprime(n):
    if n < 2:
        return False
    elif n == 2:
        return True
    else:
        for x in xrange(2, int(n**0.5)+1):
            if n%x == 0:
                return False
        return True

def get(n):
    r = []
    p = n
    m = 0
    while p > 0:
        m += 1
        p /= 10
    p = n
    r.append(n)
    for i in xrange(1, m):
        x = p/10
        y = p%10
        p = y*(10**(m-1))+x
        if p not in r:
            r.append(p)
    return r

if __name__ == '__main__':
    main()

p37.py

#!/usr/bin/env python

def main():
    m = []
    x = 2
    while len(m) < 15:
        if x not in m:
            n = get(x)
            b = True
            for v in xrange(0,len(n)):
                if not isprime(n[v]):
                    b = False
                    break
            if b:
                print n
                if n[0] not in m:
                    m.append(n[0])
        x += 1
    r = []
    for y in m:
        if y > 10:
            r.append(y)
    print r
    s = 0
    for y in r:
        s += y
    print s


def isprime(n):
    if n < 2:
        return False
    elif n == 2:
        return True
    else:
        for x in xrange(2, int(n**0.5)+1):
            if n%x == 0:
                return False
        return True

def get(n):
    r = []
    p = n
    m = 0
    while p > 0:
        m += 1
        p /= 10
    r.append(n)
    for i in xrange(1, m):
        x = n%(10**i)
        y = (n-x)/(10**i)
        if x not in r:
            r.append(x)
        if y not in r:
            r.append(y)
    return r

if __name__ == '__main__':
    main()

p41.py

#!/usr/bin/env python

def main():
    ma = 0
    for x in xrange(4,9):
        v = pan(x)
        for y in v:
            if isprime(y):
                print y
                if y > ma:
                    ma = y
    print ma

def isprime(n):
    if n < 2:
        return False
    elif n == 2:
        return True
    else:
        for x in xrange(2, int(n**0.5)+1):
            if n%x == 0:
                return False
        return True

def pan(n):
    if n <= 1:
        return [1]
    else:
        l = pan(n-1)
        r = []
        for x in l:
            y = x
            c = 0
            while y > 0:
                y /= 10
                c += 1
            for i in xrange(0,c+1):
                a = x%(10**i)
                b = x - a
                v = b*10 + n*(10**i) + a
                r.append(v)
        return r
            


if __name__ == '__main__':
    main()

p43.py

#!/usr/bin/env python

def pan(n):
    if n <= 1:
        return [10, 01]
    else:
        l = pan(n-1)
        r = []
        for x in l:
            y = x
            c = 0
            while y > 0:
                y /= 10
                c += 1
            for i in xrange(0,c+1):
                a = x%(10**i)
                b = x - a
                v = b*10 + n*(10**i) + a
                r.append(v)
        return r

def main():
    l = pan(9)
    m = 0
    for x in l:
        if ((x/1000000)%1000)%2 == 0 and \
        ((x/100000)%1000)%3 == 0 and \
        ((x/10000)%1000)%5 == 0 and \
        ((x/1000)%1000)%7 == 0 and \
        ((x/100)%1000)%11 == 0 and \
        ((x/10)%1000)%13 == 0 and \
        (x%1000)%17 == 0:
            m += x
            print x
    print 'Got:', m


if __name__ == '__main__':
    main()

p45.py

#!/usr/bin/env python

def depen(p):
    v = p*24+1
    d = int(v**0.5)
    if d**2 == v and (d+1)%6 == 0:
        return (d+1)/6
    else:
        return None

def detri(t):
    v = t*8+1
    d = int(v**0.5)
    if d**2 == v and (d-1)%2 == 0:
        return (d-1)/2
    else:
        return None

def dehex(h):
    v = h*8+1
    d = int(v**0.5)
    if d**2 == v and (d+1)%4 == 0:
        return (d+1)/4
    else:
        return None

def main():
    x = 1
    while True:
        y = x*(3*x-1)/2
        if detri(y) > 0 and dehex(y) > 0:
            print y, depen(y), detri(y), dehex(y)
            if y > 40755:
                print "Got:", y
                break
        x += 1

if __name__ == '__main__':
    main()

p46.py

#!/usr/bin/env python

def isprime(n):
    if n < 2:
        return False
    elif n == 2:
        return True
    else:
        for x in xrange(2, int(n**0.5)+1):
            if n%x == 0:
                return False
        return True

def main():
    x = 3
    while True:
        x += 2
        if isprime(x):
            continue
        r = False
        j = 0
        v = 0
        for i in xrange(1,int((x/2)**0.5)+2):
            v = x - (i**2)*2
            print i,v
            if isprime(v):
                r = True
                j = i
                break
        if r:
            print x,'=',v, '+', 2, '*',j,'^',2
        else:
            break
    print "Got:", x

if __name__ == '__main__':
    main()

p53.py

#!/usr/bin/env python

def ncr(n, r):
    if r >= n/2:
        a = n
        b = r
        while r > 1:
            n -= 1
            r -= 1
            a *= n
            b *= r
        return a/b
    else:
        return ncr(n, n-r)

def main():
    s = 0
    for x in xrange(1,101):
        for y in xrange(1,x+1):
            if ncr(x,y) > 1000000:
                s += 1
    print s

if __name__ == '__main__':
    main()

p56.py

#!/usr/bin/env python

def digsum(number):
    r = 0
    while number > 0:
        r += number%10
        number /= 10
    return r

def main():
    max = 0
    for x in xrange(1,100):
        for y in xrange(1,100):
            s = digsum(x**y)
            if max < s:
                max = s
    print max

if __name__ == '__main__':
    main()