hobophobe

def diophantine(packages=(6,9,20), maxcheck=200):
  sortpack = list(packages)
  sortpack.sort()
  if sortpack[0] <= 1: # Considering a <2pack to mean you don't want an answer
    return None
  unavailable = [1]
  check = 2
  while check < maxcheck and check - unavailable[-1] <= sortpack[0]:
    if not diophantine_test(sortpack, check):
      unavailable.append(check)
    check += 1
  return unavailable


def diophantine_test(sortpack, value):
# Check for single pack size matches
  for pack in sortpack:
    if value % pack == 0:
      return True
  if sortpack[2] > value: # Discard unusable pack size
    if sortpack[1] > value:
      return False # Single packs already checked by modulus
    else:
      return diophantine_two(sortpack[0:2], value)
  else:
    return diophantine_three(sortpack, value)
  return False


def diophantine_two(sortpack, value):
  if value % sortpack[1] == 0:
    return True
  while value >= sortpack[0]:
    if value % sortpack[0] == 0:
      return True
    value -= sortpack[1]
  return False


def diophantine_three(sortpack, value):
  while value >= sortpack[0]:
    if diophantine_two(sortpack[0:2], value):
      return True
    value -= sortpack[2]
  return False


# Part 1
# t  | 20pc | 9pc | 6pc
# 50 | 1    | 2   | 2
# 51 | 0    | 5   | 1
# 52 | 2    | 0   | 2
# 53 | 1    | 1   | 4
# 54 | 0    | 6   | 0
# 55 | 2    | 1   | 1
#
# Given the solutions above the values for 56-65 can be achieved.
# For 56-61 simply take one of the above and add an extra six-pack.
# For 62-65 simply take 56-59 and add an extra six-pack.

# Part 2
# The theorem is true because once you have covered an entire "step" of the lowest size pack
# you can simply add another of the smallest pack to achieve the next number of your choosing.
#
# Note that the same will hold for a larger pack's step-size, if achieveable. However, that
# is not strictly necessary as you will have already met the requirement for the smaller pack.

# Part 3
standard_mcdiophantine = diophantine()
print("Part 3")
print("Largest number of McNuggets that cannot be bought in exact quantity: %d" % standard_mcdiophantine[-1])

# Part 4

def vary_mcdiophantine(x,y,z):
  varied_mcdiophantine = diophantine((x,y,z))
  
  print("Given package sizes %d, %d, and %d, the largest number of McNuggets that cannot be bought in exact quantity is: %d" % (x,y,z,varied_mcdiophantine[-1]))

print("\nPart 4")
vary_mcdiophantine(3,5,7)
vary_mcdiophantine(9,4,6)
vary_mcdiophantine(3,7,11)
vary_mcdiophantine(4,11,8)

# Edit: apparently the syntax highlighter doesn't like triple-quoted strings,
# as used for documentation; converted them to code comments.
from math import *

def is_prime(n):
  # Simple prime check with a few early checks to save from the full check.
  if n % 2 == 0:
    return False
  sqroot = sqrt(n)
  if int(sqroot) == sqroot: # Does the square root have a fractional part?
    return False
  test = 3
  while test <= sqroot:
    if n % test == 0:
      return False
    test += 2
  return True

def next_prime(n):
  # Find the next prime greater than n (n doesn't have to be prime!)
  check = n
  if n % 2 == 0: # Is n even?
    check += 1
  else:
    check += 2
  while not is_prime(check):
    check += 2
  return check

def thousandth_prime(n=1000):
  # Get the thousandth prime.
  count = 1 # 2 is prime
  last = 2
  while count < n:
    count += 1
    last = next_prime(last)
  return last

def sumlogs(n):
  # Sum of primes 2 through n; not ideal, always computes one unused prime.
  # One solution would be to use Eratosthenes' sieve to first compute all
  # needed primes. Tradeoff there is space versus CPU use.
  last = 1
  sumlg = log(2)
  while last <= n:
    sumlg += log(last)
    last = next_prime(last)
  return sumlg

# Part 1
print(thousandth_prime())

# Part 2
n = int(raw_input("Enter the upper limit for primes: "))
sumlg = sumlogs(n)

print(sumlg)
print(n)
print(sumlg/n)

# Lists for questions and answers.
quests = [ 'Last name:  ', 'First name: ', ]
answer = []

for q in quests:
  a = None
# Don't take 'no [input]' for an answer.
  while not a:
    a = raw_input(q)
  answer.append(a)

# For reuse this might not be appropriate.
answer.reverse()

for a in answer:
  print(a)