NawXela

#Problem Set #2
#Name: Alex Wan
#Time: Far too long
#Collaborators: CuriousReef

#Problem 1
#McNuggets come in packs of 6, 9, and 20. Show that it is possible to buy 
#exactly 50, 51, 52, 53, 54, and 55 McNuggets using this Diophantine equation:
#6a + 9b + 15c = n, where n is the number of McNuggets.
#List all combinations.


#I tried finding it for any range, however I'm not sure how to fill the values
#between the first and last values. So I'll just go from 50 to 55.

nuggetrange = (50, 51, 52, 53, 54, 55)

for a in range (0, 20):
        for b in range (0, 20):
                for c in range (0, 20):
                        n = 6*a+9*b+20*c;
                        if n in nuggetrange:
                                print (a, b, c, n)

##(0, 6, 0, 54)
##(1, 1, 2, 55)
##(1, 3, 1, 53)
##(1, 5, 0, 51)
##(2, 0, 2, 52)
##(2, 2, 1, 50)
##(3, 4, 0, 54)
##(4, 1, 1, 53)
##(4, 3, 0, 51)
##(5, 0, 1, 50)
##(6, 2, 0, 54)
##(7, 1, 0, 51)
##(9, 0, 0, 54)

#Problem 2                           
#Theorem: If it is possible to buy x, x+1,...,x+5 sets of McNuggets for some x,
#then it is possible to buy any number of McNuggets greater than or equal to x,
#given that McNuggets come in sets of 6, 9, and 20.
#Explain why this is true.

#Um... because it is? Well, I know x must at least be bigger than 6, because that
#is the minimum amount you can buy. But 7 (6+1) and 8 (6+2) are impossible to buy.
#The reason lies in the fact that the smallest they come in is 6. If you can get
#a combination for any number from x to x+5, then x+6 would merely be another set
#of 6 McNuggets. For example, x+11 would be broken down into x+5 and 6. If you can
#get a combination for x+5 McNuggets, all you need is another set of 6. The theorem
#holds true for sets of 6 and 9, or 6 and 20, or 6 and any number.

#Problem 3:
#Find the largest amount of McNuggets that cannot be bought in exact quantity. 
#Print the following line at the end:
#"Largest number of McNuggets that cannot be bought in exact quantity: <n>"

#My idea is to start n at 1, and keep increasing n until we get six consecutive solutions.
#Of course, it's always harder than it sounds. I'm not sure how I can get Python to
#record six consecutive solutions, and tell the program to stop if I do. The main problem
#lies in the fact that the solution generator does not generate n in sequential order.
#I might get solutions for 54, then 53, and then 50, making increasing the number useless.

#My solution lies in the ability to remove the first element in a queue. With a brute forced list of possible answers,
#I checked if the first element was exactly five less than the sixth element. If not, the first element was removed, and
#the test was repeated until an answer was found.

from collections import deque

rightanswers = []
answer = False
count = 0

for a in range (0, 20):
        for b in range (0, 20):
                for c in range (0, 20):
                        n = 6*a+9*b+20*c;
                        #print (a, b, c, n)
                        rightanswers.append(n)
                        rightanswers.sort()
                        rightanswers = list(set(rightanswers))

print rightanswers
rightanswers = deque(set(rightanswers))
while answer == False:
        if rightanswers[0] + 5 == rightanswers[5]:
                answer = True
                print possibleanswer, 'is the largest number of McNuggets that cannot be bought in exact quantity.'
        else:
                possibleanswer = rightanswers[0]
                rightanswers.popleft()

#Problem 4:
#Assign a tuple to be the coefficents of the variables in the diophantine equation.
#Then, exhaustively search for the largest number less than 150 that cannot be bought in exact quantity.

#I used the same code as atop, but added the restrictive template and user friendlied the code.

from collections import deque

bestSoFar = 0     # variable that keeps track of largest number of McNuggets that cannot be bought in exact quantity
first = int(input('Enter the first package size:'))
second = int(input('Enter the second package size:'))
third = int(input('Enter the third package size:'))
packages = [first,second,third]   # variable that contains package sizes
packages.sort()
x = packages[0]
y = packages[1]
z = packages[2]
rightanswers = []
finalanswers = []
answer = False

for a in range (0, 20):
        for b in range (0, 20):
                for c in range (0, 20):
                        n = x*a+y*b+z*c;
                        #print (a, b, c, n)
                        rightanswers.append(n)
                        rightanswers.sort()
                        rightanswers = list(set(rightanswers))
print rightanswers
rightanswers = deque(set(rightanswers))
while answer == False:
        if rightanswers[0] + packages[0] == rightanswers[x]:
                answer = True
        else:
                possibleanswer = rightanswers[0]
                rightanswers.popleft()

for n in range(1, 150): # only search for solutions up to size 150
        if n in rightanswers:
                finalanswers.append(n)
        if possibleanswer in range (1, 150):
                finalanswers.append(possibleanswer)
print finalanswers
bestSoFar = finalanswers[0]
print 'Given package sizes', x, y, z, 'the largest number of McNuggets that cannot be bought in exact quantity is:', bestSoFar
        ## complete code here to find largest size that cannot be bought
        ## when done, your answer should be bound to bestSoFar
        ## SUCCESS!                        

#Problem Set #1
#Name: Alex Wan
#Collaborators: The Python tutorial on for statements, located here: http://docs.python.org/tutorial/controlflow.html#for-statements
#Time: 2:00

#Find the 1000th prime number. This looks like it'll be really hard.

primecandidate = 3
finalprime = int(input('Enter the Nth prime number you want to find:')) #Input 1000.
primecount = 1

while (primecount < finalprime):
    for divisor in range(2, primecandidate):
        if primecandidate % divisor == 0:
            primecandidate = primecandidate + 1
            break
    else:
        print primecandidate, 'is a prime number'
        primecandidate = primecandidate + 1
        primecount = primecount + 1

print primecandidate - 1, 'is the', finalprime, 'th prime number.'

#In addition, write a program that computes the sum of the logarithms of all the primes from 2 to N.
#Print out this sum, the number N, and the ratio between the sum and N (sum/N)

from math import *

primecandidate = 3
finalprime = int(input('Enter the Nth prime number you want to find:')) #This is N.
primecount = 1
logsum = log(2)

while (primecount < finalprime):
    for divisor in range(2, primecandidate):
        if primecandidate % divisor == 0:
            primecandidate = primecandidate + 1
            break
    else:
        print primecandidate, 'is a prime number'
        logsum = logsum + log(primecandidate)
        primecandidate = primecandidate + 1
        primecount = primecount + 1

print primecandidate - 1, 'is the', finalprime, 'th prime number.'
print 'The sum of all the logarithms of all the prime numbers between 2 and', primecandidate - 1, 'is', logsum
print 'The ratio between', logsum, 'and', primecandidate - 1, 'is', (logsum/(primecandidate - 1))

#Problem Set 0
#Name: Alex
#Collaborators: None
#Time: 0:20

#My first name program.
firstname=raw_input('Enter your first name:')
lastname=raw_input('Enter your last name:')
print "Thank you, " + firstname + " " + lastname