Skip to content

Instantly share code, notes, and snippets.

@huffman
Created August 13, 2012 04:08
Show Gist options
  • Save huffman/3336866 to your computer and use it in GitHub Desktop.
Save huffman/3336866 to your computer and use it in GitHub Desktop.
#!/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]
# 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)
#!/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)
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment