27.py

#!/usr/bin/env python
# -*- coding: latin-1 -*-

# Euler published the remarkable quadratic formula:
#
# n² + n + 41
#
# It turns out that the formula will produce 40 primes for the consecutive values n = 0 to 39. However, when n = 40, 402 + 40 + 41 = 40(40 + 1) + 41 is divisible by 41, and certainly when n = 41, 41² + 41 + 41 is clearly divisible by 41.
#
# Using computers, the incredible formula  n² − 79n + 1601 was discovered, which produces 80 primes for the consecutive values n = 0 to 79. The product of the coefficients, −79 and 1601, is −126479.
#
# Considering quadratics of the form:
#
#     n² + an + b, where |a| < 1000 and |b| < 1000
#
#     where |n| is the modulus/absolute value of n
#     e.g. |11| = 11 and |−4| = 4
#
# Find the product of the coefficients, a and b, for the quadratic expression that produces the maximum number of primes for consecutive values of n, starting with n = 0.

import math

def is_prime(n, mem={0: False, 1: False}):
    if n in mem:
        return mem[n]
    result = True
    for x in xrange(2, int(math.sqrt(abs(n)))):
        if n % x == 0:
            result = False
    mem[n] = result
    return result

best = (0, 0, 0)
for a in xrange(-999, 1000):
    for b in xrange(-999, 1000):
        n = 0
        while is_prime(n ** 2 + (a * n) + b):
            n += 1
        if n > best[0]:
            best = (n, a, b)

print best, best[1] * best[2]

28.py

# Problem 28
#
# Starting with the number 1 and moving to the right in a clockwise direction a 5 by 5 spiral is formed as follows:
#
# 21 22 23 24 25
# 20  7  8  9 10
# 19  6  1  2 11
# 18  5  4  3 12
# 17 16 15 14 13
#
# It can be verified that the sum of the numbers on the diagonals is 101.
#
# What is the sum of the numbers on the diagonals in a 1001 by 1001 spiral formed in the same way?

import sys

def diag(size, mem={1: 1}):
    if size in mem:
        return mem[size]
    else:
        total = mem[size] = (size ** 2) * 4 - ((size-1) * 6) + diag(size-2)
        return total

print diag(1001)

29.py

#!/usr/bin/env python
# -*- coding: latin-1 -*-

# Consider all integer combinations of ab for 2 ≤ a ≤ 5 and 2 ≤ b ≤ 5:
#
#     22=4, 23=8, 24=16, 25=32
#     32=9, 33=27, 34=81, 35=243
#     42=16, 43=64, 44=256, 45=1024
#     52=25, 53=125, 54=625, 55=3125
#
# If they are then placed in numerical order, with any repeats removed, we get the following sequence of 15 distinct terms:
#
# 4, 8, 9, 16, 25, 27, 32, 64, 81, 125, 243, 256, 625, 1024, 3125
#
# How many distinct terms are in the sequence generated by ab for 2 ≤ a ≤ 100 and 2 ≤ b ≤ 100?

from sets import Set

s = Set([])
for a in xrange(2, 101):
    for b in xrange(2, 101):
        s.add(a ** b)

print len(s)

b.py

import sys
import math

def zip_apply(fun, lists):
    return [fun(pair) for pair in zip(pos_vel, firefly_info)]

for case in xrange(int(sys.stdin.readline())):
    # Position and velocity values
    pos_vel = [0, 0, 0, 0, 0, 0]

    num_fireflies = float(sys.stdin.readline())
    for _ in xrange(int(num_fireflies)):
        firefly_info = [int(x) for x in sys.stdin.readline().split(' ')]
        pos_vel = zip_apply(sum, [pos_vel, firefly_info])

    x, y, z, vx, vy, vz = [a / num_fireflies for a in pos_vel]

    if vx == 0 and vy == 0 and vz == 0:
        tmin = 0.0
    else:
        tmin = (- (x * vx) - (y * vy) - (z * vz)) / (vx ** 2 + vy ** 2 + vz ** 2)
        tmin = max(0.0, tmin)

    dmin = math.sqrt(
        (x + tmin * vx) ** 2
        + (y + tmin * vy) ** 2
        + (z + tmin * vz) ** 2
    )

    print 'Case #%d: %.8f %.8f' % (case + 1, dmin, tmin)