Problems 31 40

Euler 31: How many different ways can 2 pounds be made using any number of coins?

def euler31(total):
    type_coins = [200, 100, 50, 20, 10, 5, 2, 1]
    def get_coins(coins=(), current=0):
        def get_match(x, subtotal):
            if subtotal == total:
                padding = (len(type_coins)-len(coins)-1)
                return [coins+(0,)*padding]
            elif len(coins) < len(type_coins)-1:    
                return get_coins(coins+(x,), subtotal)
            else: return []
        peso = type_coins[len(coins)]
        coin_range = xrange(0, (total-current)/peso+1)
        return (y for x in coin_range for y in get_match(x, current+x*peso))
    return iterlen(get_coins())

Euler 32: Find the sum of all products whose multiplicand/multiplier/product identity can be written as a 1 through 9 pandigital

def different_items(it):
    lst = list(it)
    return (len(set(lst)) == len(lst))
 
def euler32():
    different = lambda x: different_items(digsnum(x))
    getdigs = lambda nums: flatten(imap(digsnum, nums))
    condition = lambda n, n1: different(n/n1) and ispandigital(getdigs([n1, n/n1, n]))
    test_divisors = lambda n: takewhile(lambda x: x < sqrt(n), get_divisors(n))
    get_n1 = lambda num: ifilter(different, test_divisors(num))
    candidates = ifilter(different, xrange(1000, 10000))
    return sum(unique(num for num in candidates \
        for n1 in get_n1(num) if condition(num, n1)))

Euler 33: If the product of these four fractions is given in its lowest common terms, find the value of the denominator

def euler33():
    def quotient(a, b):
        gcd = greatest_common_divisor([a, b])
        return [x/gcd for x in a, b]
    def condition1(n1):
        a, b = digsnum(n1)
        return (a != 0 and b != 0 and a != b)
    def condition2((n1, n2)):
        if n1 == n2 or n1 > n2:
            return False
        a, b = digsnum(n1)
        c, d = digsnum(n2)
        lstquotient = lambda a, b: quotient(*map(numdigs, [a, b]))
        q0 = lstquotient([a, b], [c, d])
        checks = [(a, c, b, d), (a, d, b, c), (b, c, a, d), (b, d, a, c)]
        def check(x1, y1, x2, y2):        
            return (x1 == y1 and q0 == quotient(x2, y2))
        return any(starmap(check, checks))
 
    candidates = filter(condition1, xrange(10, 100))
    pairs = filter(condition2, icross(candidates, candidates))
    mulq = lambda n: mul(imap(operator.itemgetter(n), pairs))
    return quotient(mulq(0), mulq(1))[1]

Euler 34: Find the sum of all numbers which are equal to the sum of the factorial of their digits

def euler34():
    limit_condition = lambda n: ndigits(n*(factorial(9))) > n
    limit = factorial(9)*last(takewhile(limit_condition, count(1)))
    factorial_cache = dict((n, factorial(n)) for n in xrange(0, 10))
    cfactorial = lambda x: factorial_cache[x]
    condition = lambda x: (x == sum(imap(cfactorial, digsnum(x))))
    return sum(ifilter(condition, xrange(10, limit+1)))

Euler 35: How many circular primes are there below one million?

def euler35(end):    
    def rotatelst(n, lst):
        n0 = n%len(lst)
        return lst[n0:]+lst[:n0]    
    condition1 = lambda x: x < 10 or all(y in (1,3,7,9) for y in digsnum(x))
    condition2 = lambda x: all(isprime(numdigs(rotatelst(r, digsnum(x)))) \
        for r in xrange(ndigits(x)))
    return iterlen(ifilter(condition2, ifilter(condition1, xrange(2, end))))

Find the sum of all numbers, less than one million, which are palindromic in base 10 and base 2

def ispalindromic(num, base=10):
    """Check if 'num' in base 'base' is a palindrome, that's it, if it can be
    read from left to right and right to left being the same number"""
    digitslst = digsnum(num, base)
    return digitslst == list(reversed(digitslst))
 
def euler36(end, bases):
    condition = lambda x: all(ispalindromic(x, base) for base in bases)
    return sum(ifilter(condition, xrange(1, end+1)))

Euler37: Find the sum of the only eleven primes that are both truncatable from left to right and right to left

def euler37(total):
    cutr = lambda digits, n: numdigs(digits[:len(digits)-n])
    cutl = lambda digits, n: numdigs(digits[n:])
    condition = lambda digits: all(isprime(cutr(digits, n)) and \
        isprime(cutl(digits, n)) for n in reversed(xrange(len(digits))))
    candidates0 = lambda ndigs: icross(*([[2,3,5,7]]+[[1,3,7,9]]*(ndigs-1)))
    candidates = (digits for n in count(2) for digits in candidates0(n))
    return sum(imap(numdigs, take(total, ifilter(condition, candidates))))

Euler38: Excluding the trivial example, 987654321, what is the largest 1 to 9 pandigital number that can be formed this way?

def euler38():
    def process_num(x):
        genmuls0 = lambda x, m: [digsnum(x*n) for n in xrange(1, m+1)]
        genmuls = lambda x: imap(flatten, (genmuls0(x, m) for m in count(1)))
        return last(takewhile(different_items, genmuls(x)))
    candidates = xrange(int(1e4))
    return numdigs(max(ifilter(ispandigital, imap(process_num, candidates))))

Euler 39: For which value of p < 1000, is the number of solutions maximised?

def euler39(end):
    acand = lambda p: ((p-b-c,b,c) for b in xrange(1,p/2) for c in xrange(1,b))
    trangles = lambda end: (y for x in imap(acand, xrange(4,end,2)) for y in x)
    maxocurrence = lambda oculst: max(ocurrences(oculst, exchange=True))[1]
    return maxocurrence(map(sum, ifilter(is_pythagorean, trangles(end))))

Euler 40: f dn represents the nth digit of the fractional part, find the value of the following expression

def euler40():
    limit = lambda n: (((8+9*(n-2))*(10**(n-1))+1)/9)+1
    getn = lambda x: first(n-1 for n in count(1) if limit(n) > x)
    def getdecimal(x):                 
        n = getn(x)
        c, d = divmod(x-limit(n), n)
        return digsnum(c+10**(n-1))[d]
    return mul(getdecimal(x) for x in [10**y for y in xrange(5+1)])